Trie vs Hash Map for Prefix Matching in DSA Go - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Using Trie

What is the output of the following Go code that uses a Trie to find all words with prefix "app"?

DSA Go

package main
import "fmt"

// TrieNode represents a node in the trie
 type TrieNode struct {
    children map[rune]*TrieNode
    isEnd bool
}

func NewTrieNode() *TrieNode {
    return &TrieNode{children: make(map[rune]*TrieNode)}
}

func (t *TrieNode) Insert(word string) {
    node := t
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = NewTrieNode()
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *TrieNode) collectWords(prefix string, node *TrieNode, results *[]string) {
    if node.isEnd {
        *results = append(*results, prefix)
    }
    for ch, child := range node.children {
        t.collectWords(prefix+string(ch), child, results)
    }
}

func (t *TrieNode) SearchPrefix(prefix string) []string {
    node := t
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return []string{}
        }
        node = node.children[ch]
    }
    var results []string
    t.collectWords(prefix, node, &results)
    return results
}

func main() {
    trie := NewTrieNode()
    words := []string{"apple", "app", "application", "apt", "banana"}
    for _, w := range words {
        trie.Insert(w)
    }
    result := trie.SearchPrefix("app")
    fmt.Println(result)
}

A ["banana"]

B ["apple", "application"]

C ["app", "apt", "apple", "application"]

D ["app", "apple", "application"]

💡 Hint

Think about which words start exactly with the prefix "app" in the list.

The trie stores words and allows prefix search. The prefix "app" matches "app", "apple", and "application". "apt" and "banana" do not start with "app".

🧠 Conceptual

intermediate

Why Use Trie Over Hash Map for Prefix Matching?

Which of the following is the main advantage of using a Trie over a Hash Map for prefix matching?

A Trie allows efficient prefix search without checking every key individually.

B Trie uses less memory than a Hash Map for storing the same words.

C Hash Map can only store numeric keys, not strings.

D Trie automatically sorts keys in descending order.

💡 Hint

Think about how prefix search works in both data structures.

Trie stores characters in a tree structure, enabling quick prefix search by traversing nodes. Hash Map requires checking each key or storing all prefixes separately, which is less efficient.

🔧 Debug

advanced

Identify the Error in Hash Map Prefix Search Code

What error will this Go code produce when trying to find keys starting with prefix "pre" in a map?

DSA Go

package main
import "fmt"

func main() {
    m := map[string]int{"prefix": 1, "presto": 2, "press": 3, "post": 4}
    prefix := "pre"
    var results []string
    for k := range m {
        if len(k) >= len(prefix) && k[:len(prefix)] == prefix {
            results = append(results, k)
        }
    }
    fmt.Println(results)
}

A []

B ["prefix", "presto", "press"]

C runtime error: slice bounds out of range

D compile error: invalid slice index

💡 Hint

Check what happens if a key is shorter than the prefix length.

If a key is shorter than the prefix length, slicing k[:len(prefix)] causes a runtime error due to out of range slice bounds.

🚀 Application

advanced

Choosing Data Structure for Large Prefix Queries

You need to build a system that supports millions of words and frequent prefix queries. Which data structure is best for fast prefix matching and why?

A Hash Map, because it stores keys with their prefixes as separate entries for quick lookup.

B Trie, because it shares common prefixes and reduces search time for prefix queries.

C Array, because sorting words allows binary search for prefixes.

D Linked List, because it allows easy insertion and traversal.

💡 Hint

Consider how each structure handles prefix queries efficiently.

Trie stores words in a tree where common prefixes share nodes, making prefix queries fast and memory efficient compared to storing all prefixes separately in a hash map.

❓ Predict Output

expert

Output of Combined Trie and Hash Map Prefix Search

What is the output of this Go code that uses both Trie and Hash Map to find words starting with "go"?

DSA Go

package main
import "fmt"

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd bool
}

func NewTrieNode() *TrieNode {
    return &TrieNode{children: make(map[rune]*TrieNode)}
}

func (t *TrieNode) Insert(word string) {
    node := t
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = NewTrieNode()
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *TrieNode) SearchPrefix(prefix string) []string {
    node := t
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return []string{}
        }
        node = node.children[ch]
    }
    var results []string
    var dfs func(n *TrieNode, path string)
    dfs = func(n *TrieNode, path string) {
        if n.isEnd {
            results = append(results, path)
        }
        for ch, child := range n.children {
            dfs(child, path+string(ch))
        }
    }
    dfs(node, prefix)
    return results
}

func main() {
    words := []string{"go", "gone", "gopher", "goal", "game"}
    trie := NewTrieNode()
    m := make(map[string]bool)
    for _, w := range words {
        trie.Insert(w)
        m[w] = true
    }
    prefix := "go"
    trieResults := trie.SearchPrefix(prefix)
    var mapResults []string
    for k := range m {
        if len(k) >= len(prefix) && k[:len(prefix)] == prefix {
            mapResults = append(mapResults, k)
        }
    }
    fmt.Println("Trie results:", trieResults)
    fmt.Println("Map results:", mapResults)
}

A

Trie results: ["go", "goal", "gone", "gopher"]
Map results: ["go", "goal", "gone", "gopher"]

B

Trie results: ["go", "goal", "gone", "gopher"]
Map results: ["game"]

C

Trie results: ["go", "gone", "gopher"]
Map results: ["go", "goal", "gone", "gopher"]

D

Trie results: []
Map results: []

💡 Hint

Both Trie and Map contain the same words; check which start with "go".

Both Trie and Map contain words starting with "go": "go", "goal", "gone", "gopher". "game" does not start with "go". So both results match these four words.

Practice

1. Which data structure is generally more efficient for checking if a prefix exists in a large set of strings?

easy

A. Linked List, because it allows sequential access to elements

B. Hash Map, because it stores keys and values with constant time lookup

C. Array, because it stores elements in order and allows binary search

D. Trie, because it stores prefixes explicitly and allows fast prefix search

Solution

1. Step 1: Understand prefix search requirements

   Prefix search needs to quickly find if any string starts with a given prefix.

2. Step 2: Compare Trie and Hash Map for prefix search

   Trie stores prefixes explicitly, allowing fast traversal to check prefixes. Hash Map is good for exact key lookup but not for prefix matching.

3. Final Answer:

   Trie, because it stores prefixes explicitly and allows fast prefix search -> Option D

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Trie stores prefixes explicitly, ideal for prefix search [OK]

Common Mistakes:

• Thinking hash map supports prefix search efficiently
• Confusing prefix search with exact key lookup
• Assuming arrays or lists are efficient for prefix matching

2. Which of the following is the correct way to declare a Trie node struct in Go for prefix matching?

easy

A. type TrieNode struct { next map[string]int; end bool }

B. type TrieNode struct { children map[rune]*TrieNode; isEnd bool }

C. type TrieNode struct { children []int; isEnd string }

D. type TrieNode struct { children map[int]string; isEnd int }

Solution

1. Step 1: Identify correct field types for TrieNode

   Children should map characters (rune) to TrieNode pointers; isEnd is a boolean indicating word end.

2. Step 2: Check each option's correctness

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } uses map[rune]*TrieNode and bool for isEnd, which is correct. Others have wrong types or field names.

3. Final Answer:

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } -> Option B

4. Quick Check:

   TrieNode struct with map[rune]*TrieNode and bool isEnd = type TrieNode struct { children map[rune]*TrieNode; isEnd bool } [OK]

Hint: Trie children map keys are runes, isEnd is bool [OK]

Common Mistakes:

• Using incorrect types for children map keys or values
• Using string instead of bool for isEnd
• Confusing field names or types

3. Given the following Go code snippet using a Trie for prefix matching, what will be the output?

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

func (t *TrieNode) Insert(word string) {
    node := t
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *TrieNode) StartsWith(prefix string) bool {
    node := t
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return true
}

func main() {
    root := &TrieNode{children: make(map[rune]*TrieNode)}
    root.Insert("cat")
    root.Insert("car")
    root.Insert("dog")
    fmt.Println(root.StartsWith("ca"))
    fmt.Println(root.StartsWith("do"))
    fmt.Println(root.StartsWith("bat"))
}

medium

A. true
true
false

B. false
true
false

C. true
false
false

D. false
false
true

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted, building paths for 'c'->'a'->'t', 'c'->'a'->'r', and 'd'->'o'->'g'.

2. Step 2: Check StartsWith calls

   StartsWith("ca") returns true because 'c'->'a' path exists. StartsWith("do") returns true because 'd'->'o' path exists. StartsWith("bat") returns false because 'b' path does not exist.

3. Final Answer:

   true true false -> Option A

4. Quick Check:

   Prefix "ca" and "do" found, "bat" not found = true true false [OK]

Hint: Check if prefix path exists in Trie for true/false [OK]

Common Mistakes:

• Assuming StartsWith returns true only if full word exists
• Confusing Insert with StartsWith behavior
• Ignoring that 'bat' prefix is missing

4. The following Go code attempts to check if a prefix exists using a Hash Map of strings to booleans. What is the main issue?

func PrefixExists(words map[string]bool, prefix string) bool {
    for word := range words {
        if strings.HasPrefix(word, prefix) {
            return true
        }
    }
    return false
}

func main() {
    words := map[string]bool{"apple": true, "app": true, "banana": true}
    fmt.Println(PrefixExists(words, "ap"))
}

medium

A. Inefficient for large datasets due to linear scan over all keys

B. Syntax error: strings.HasPrefix is not a valid function

C. Incorrect return type: should return string instead of bool

D. Map keys cannot be iterated in Go

Solution

1. Step 1: Analyze PrefixExists function logic

   The function iterates over all keys in the map and checks prefix using strings.HasPrefix.

2. Step 2: Identify performance issue

   Iterating all keys causes linear time complexity, which is inefficient for large datasets compared to Trie prefix search.

3. Final Answer:

   Inefficient for large datasets due to linear scan over all keys -> Option A

4. Quick Check:

   Linear scan in map for prefix = inefficient [OK]

Hint: Hash map prefix check needs full scan, slow for many keys [OK]

Common Mistakes:

• Thinking strings.HasPrefix is invalid
• Assuming map iteration is not allowed
• Confusing return types

5. You need to design a system to quickly find all words starting with a given prefix from a dictionary of 1 million words. Which approach is best and why? A) Use a Hash Map storing all words as keys and scan keys for prefix matches. B) Use a Trie to store all words and traverse nodes to find prefix matches. C) Store words in a sorted array and use binary search to find prefix range. D) Use a Linked List to store words and iterate to find prefix matches.

hard

A. Sorted array with binary search finds prefix range efficiently

B. Hash Map with linear scan is fast due to constant lookup

C. Trie allows efficient prefix traversal without scanning all words

D. Linked List is best for sequential prefix matching

Solution

1. Step 1: Evaluate each data structure for prefix search on large data

   Hash Map requires scanning all keys for prefix, inefficient. Trie is efficient and allows prefix traversal without scanning all words. Sorted array allows binary search to find prefix range quickly but requires additional steps to find all matches.

2. Step 2: Compare Trie and sorted array for large datasets

   Trie uses more memory but provides direct prefix traversal and efficient prefix queries. Sorted array with binary search is efficient for prefix range queries but retrieving all matches requires scanning the range.

3. Final Answer:

   Trie allows efficient prefix traversal without scanning all words -> Option C

4. Quick Check:

   Trie prefix traversal = efficient prefix search [OK]

Hint: Trie allows direct prefix traversal for fast prefix search [OK]

Common Mistakes:

• Choosing sorted array without considering retrieval cost
• Assuming hash map supports fast prefix search
• Ignoring Trie advantages for prefix queries