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.