Autocomplete System with Trie in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Insertion and Search

What will be the output of the following Go code that inserts words into a Trie and searches for a prefix?

DSA Go

package main
import "fmt"

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

// Trie structure
type Trie struct {
    root *TrieNode
}

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

// Initialize a new Trie
func NewTrie() *Trie {
    return &Trie{root: NewTrieNode()}
}

// Insert a word into the Trie
func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if _, ok := node.children[ch]; !ok {
            node.children[ch] = NewTrieNode()
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

// Search for a prefix in the Trie
func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for _, ch := range prefix {
        if _, ok := node.children[ch]; !ok {
            return false
        }
        node = node.children[ch]
    }
    return true
}

func main() {
    trie := NewTrie()
    trie.Insert("dog")
    trie.Insert("deer")
    trie.Insert("deal")
    fmt.Println(trie.StartsWith("de"))
    fmt.Println(trie.StartsWith("do"))
    fmt.Println(trie.StartsWith("cat"))
}

A

false
true
false

B

true
false
false

C

true
true
false

D

false
false
true

💡 Hint

Think about how the Insert method builds the Trie and how StartsWith checks prefixes.

The words "dog", "deer", and "deal" are inserted. The prefixes "de" and "do" exist in the Trie, so StartsWith returns true for them. "cat" is not inserted, so it returns false.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the role of the 'isEnd' boolean in a Trie node?

A It marks the node as the end of a complete word stored in the Trie.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It points to the parent node in the Trie.

💡 Hint

Think about how the Trie distinguishes between prefixes and complete words.

The 'isEnd' boolean indicates that the path from root to this node forms a complete word in the Trie.

🔧 Debug

advanced

Find the Bug in Trie Search Method

What error will the following Go code produce when searching for a prefix in a Trie?

DSA Go

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

A It returns false for prefixes that are valid but not complete words.

B It returns true only if the prefix is a complete word, not just a prefix.

C It always returns true regardless of prefix existence.

D It causes a runtime panic due to nil map access.

💡 Hint

Check the return condition and what the method is supposed to do.

The method returns node.isEnd, which means it only returns true if the prefix is a complete word, not just a prefix. This is incorrect for a StartsWith method.

🚀 Application

advanced

Autocomplete Suggestions Using Trie

Given a Trie with words inserted, which approach correctly collects all words starting with a given prefix?

A Only return the prefix itself if it is a complete word.

B Traverse the entire Trie and collect words containing the prefix anywhere.

C Return all words inserted without filtering by prefix.

D Traverse to the prefix node, then perform DFS collecting words where isEnd is true.

💡 Hint

Think about how to efficiently find all words starting with a prefix in a Trie.

The correct method is to find the node representing the prefix, then explore all descendant nodes to collect complete words.

❓ Predict Output

expert

Output of Trie Autocomplete Function

What is the output of the following Go code that performs autocomplete suggestions for prefix "ca"?

DSA Go

package main
import "fmt"

// TrieNode and Trie definitions omitted for brevity
// Assume Insert and StartsWith methods exist as before

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

func (t *Trie) Autocomplete(prefix string) []string {
    node := t.root
    for _, ch := range prefix {
        if _, ok := node.children[ch]; !ok {
            return []string{}
        }
        node = node.children[ch]
    }
    var results []string
    t.collectWords(node, prefix, &results)
    return results
}

func main() {
    trie := NewTrie()
    trie.Insert("cat")
    trie.Insert("car")
    trie.Insert("cart")
    trie.Insert("dog")
    trie.Insert("dove")
    suggestions := trie.Autocomplete("ca")
    fmt.Println(suggestions)
}

A ["cat", "car", "cart"]

B ["cat", "car"]

C ["car", "cart"]

D ["dog", "dove"]

💡 Hint

Check which words start with "ca" and how collectWords gathers them.

Words starting with "ca" are "cat", "car", and "cart". The function collects all these words correctly.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To encrypt the stored words

B. To sort words alphabetically

C. To efficiently store and search prefixes of words

D. To count the total number of words

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie is a tree-like data structure that stores characters of words in a way that common prefixes share nodes.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires quick lookup of words starting with a given prefix, which Trie supports efficiently.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option C

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie stores prefixes for fast autocomplete lookup [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with encryption methods
• Assuming Trie counts total words only

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

easy

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

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

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

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

Solution

1. Step 1: Identify correct data types for TrieNode fields

   Children should map characters (rune) to child nodes (pointer to TrieNode). isEnd should be a boolean indicating word end.

2. Step 2: Match with given options

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } uses map[rune]*TrieNode and bool for isEnd, which is correct for Trie implementation in Go.

3. Final Answer:

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

4. Quick Check:

   Children map[rune]*TrieNode and bool isEnd [OK]

Hint: Children map keys are runes, values are pointers to TrieNode [OK]

Common Mistakes:

• Using slices instead of maps for children
• Using incorrect types like int or string for isEnd
• Mapping children with wrong key or value types

3. What will be the output of the following Go code snippet that inserts words into a Trie and searches for prefix "app"?

trie := NewTrie()
trie.Insert("apple")
trie.Insert("app")
trie.Insert("application")
results := trie.SearchPrefix("app")
fmt.Println(results)

Assuming SearchPrefix returns all words starting with the prefix.

medium

A. []

B. ["apple", "application"]

C. ["app"]

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

Solution

1. Step 1: Insert words into Trie

   Words "apple", "app", and "application" are inserted, all sharing prefix "app".

2. Step 2: Search for prefix "app"

   SearchPrefix returns all words starting with "app", so it returns all three inserted words.

3. Final Answer:

   ["app", "apple", "application"] -> Option D

4. Quick Check:

   All words with prefix "app" returned [OK]

Hint: SearchPrefix returns all words starting with given prefix [OK]

Common Mistakes:

• Returning only exact prefix word
• Missing some words sharing prefix
• Returning empty list incorrectly

4. Identify the bug in this Go code snippet for inserting a word into a Trie:

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

medium

A. isEnd should be set to true after insertion

B. children map is not initialized

C. Loop variable ch should be int, not rune

D. Function should return a value

Solution

1. Step 1: Review isEnd assignment after insertion

   After inserting a word, isEnd should mark the node as end of a word, so it must be set to true.

2. Step 2: Check other parts of code

   children map initialization and loop variable type are correct; function does not need to return a value.

3. Final Answer:

   isEnd should be set to true after insertion -> Option A

4. Quick Check:

   isEnd = true after insert [OK]

Hint: Set isEnd true to mark word end [OK]

Common Mistakes:

• Setting isEnd to false instead of true
• Not initializing children map before use
• Expecting Insert to return a value

5. Given a Trie storing words, how can you modify the autocomplete system to return suggestions sorted by frequency of word usage?

hard

A. Store a frequency count at each end node and sort results by this count

B. Sort all words alphabetically before insertion

C. Use a separate array to store frequencies unrelated to Trie

D. Ignore frequency and return words in insertion order

Solution

1. Step 1: Add frequency tracking in Trie nodes

   Modify Trie nodes to store frequency count at nodes marking word ends to track usage.

2. Step 2: Sort autocomplete results by frequency

   When returning suggestions, sort collected words by their stored frequency counts to prioritize popular words.

3. Final Answer:

   Store a frequency count at each end node and sort results by this count -> Option A

4. Quick Check:

   Frequency count in Trie nodes enables sorted suggestions [OK]

Hint: Track frequency in nodes, sort suggestions by count [OK]

Common Mistakes:

• Sorting words before insertion does not help frequency
• Using unrelated arrays breaks Trie efficiency
• Ignoring frequency loses popular word priority