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.