Prefix Search Using Trie in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the trie.

DSA Go

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

Drag options to blanks, or click blank then click option'

Ach

Bword

Cnode

Dt

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole word instead of the current character.

Using the node variable incorrectly.

We use the current character 'ch' to move to the child node in the trie during insertion.

2fill in blank

medium

Complete the code to check if a prefix exists in the trie.

DSA Go

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

Drag options to blanks, or click blank then click option'

Aprefix

Bch

Cnode

Dt

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole prefix string instead of the current character.

Checking the wrong variable for children.

We check if the current character 'ch' exists in the children map to verify the prefix.

3fill in blank

hard

Fix the error in the search function to correctly find a word in the trie.

DSA Go

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

Drag options to blanks, or click blank then click option'

Aword

Bchildren

Croot

DisEnd

Attempts:

3 left

💡 Hint

Common Mistakes

Returning the children map instead of the end flag.

Returning the root or word variable incorrectly.

To confirm the word exists, we check if the last node marks the end of a word using 'isEnd'.

4fill in blank

hard

Fill both blanks to implement a function that returns all words with a given prefix.

DSA Go

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

Drag options to blanks, or click blank then click option'

AisEnd

Bchildren

Croot

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong field names like 'root' or 'word' instead of 'children' or 'isEnd'.

Not appending words when 'isEnd' is true.

We check 'isEnd' to add words to results and iterate over 'children' to continue DFS.

5fill in blank

hard

Fill all three blanks to implement a function that deletes a word from the trie.

DSA Go

func (t *Trie) Delete(word string) bool {
    var deleteHelper func(node *TrieNode, word string, depth int) bool
    deleteHelper = func(node *TrieNode, word string, depth int) bool {
        if node == nil {
            return false
        }
        if depth == len(word) {
            if !node.[1] {
                return false
            }
            node.[2] = false
            return len(node.[3]) == 0
        }
        ch := rune(word[depth])
        if deleteHelper(node.children[ch], word, depth+1) {
            delete(node.children, ch)
            return !node.[1] && len(node.children) == 0
        }
        return false
    }
    return deleteHelper(t.root, word, 0)
}

Drag options to blanks, or click blank then click option'

AisEnd

Cchildren

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing 'root' with 'children' or 'isEnd'.

Not unsetting the 'isEnd' flag when deleting.

We check and unset 'isEnd' to mark deletion, and check 'children' map length to remove nodes.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To sort words alphabetically

B. To efficiently find all words that start with a given prefix

C. To store numbers in sorted order

D. To perform arithmetic operations quickly

Solution

1. Step 1: Understand what prefix search means

   Prefix search means finding all words that begin with a certain starting sequence of letters.

2. Step 2: Understand Trie's role in prefix search

   A Trie stores words in a tree-like structure where each node represents a character, making it fast to find all words sharing a prefix.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option B

4. Quick Check:

   Prefix search = efficient word lookup [OK]

Hint: Trie nodes represent characters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting data structures
• Thinking Trie is for arithmetic operations
• Assuming Trie stores numbers only

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

easy

A. type TrieNode struct { value int; left *TrieNode; right *TrieNode }

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

C. type TrieNode struct { data string; next *TrieNode }

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

Solution

1. Step 1: Identify the Trie node components

   A Trie node should have a map from characters (rune) to child nodes and a boolean to mark word end.

2. Step 2: Match the correct Go struct syntax

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } uses a map[rune]*TrieNode and a bool isEnd, which fits the Trie node definition.

3. Final Answer:

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

4. Quick Check:

   Trie node = map + bool [OK]

Hint: Trie nodes use map[rune]*TrieNode and bool isEnd [OK]

Common Mistakes:

• Using slice of int instead of map for children
• Confusing linked list node with Trie node
• Using int instead of bool for isEnd

3. Given the following Go code snippet for inserting words into a Trie and searching for prefix "app":

trie := NewTrie()
trie.Insert("apple")
trie.Insert("app")
trie.Insert("application")
result := trie.StartsWith("app")
fmt.Println(result)

What will be the output of fmt.Println(result)?

medium

A. [app]

B. [apple application]

C. [apple app application]

D. []

Solution

1. Step 1: Insert words into the Trie

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

2. Step 2: Search for prefix "app"

   The StartsWith method returns all words starting with "app", which includes all three inserted words.

3. Final Answer:

   [apple app application] -> Option C

4. Quick Check:

   All words with prefix "app" = [apple app application] [OK]

Hint: StartsWith returns all words sharing the prefix [OK]

Common Mistakes:

• Missing the exact prefix word "app" in results
• Returning only one matching word
• Returning empty list if prefix matches

4. Consider this buggy Go code snippet for searching a prefix in a Trie:

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

What is the main bug causing incorrect prefix search results?

medium

A. The code does not collect all words under the prefix node

B. The code does not check if node.words is initialized

C. The code returns nil instead of empty slice when prefix not found

D. The code uses wrong variable name for children map

Solution

1. Step 1: Analyze the prefix traversal loop

   The loop correctly moves node down the Trie for each character in prefix.

2. Step 2: Check the return statement after traversal

   Returning node.words assumes all words under prefix are stored there, but usually words are stored in leaf nodes, so it misses collecting all words under subtree.

3. Final Answer:

   The code does not collect all words under the prefix node -> Option A

4. Quick Check:

   Prefix search must gather all subtree words [OK]

Hint: Collect all subtree words after prefix node for correct results [OK]

Common Mistakes:

• Returning nil instead of empty slice is minor, not main bug
• Assuming words stored only at prefix node
• Ignoring recursive collection of words

5. You want to implement a prefix search that returns only words starting with a prefix but excludes words that are exactly the prefix itself. Which modification to the Trie search logic achieves this?

hard

A. After finding prefix node, return all words except the one equal to prefix

B. Return only words that have prefix length or fewer characters

C. Skip marking isEnd for prefix nodes during insertion

D. Return all words including prefix itself

Solution

1. Step 1: Understand the requirement

   We want all words starting with prefix but exclude the word exactly equal to prefix.

2. Step 2: Modify search result filtering

   After collecting all words under prefix node, filter out the word that matches prefix exactly before returning.

3. Final Answer:

   After finding prefix node, return all words except the one equal to prefix -> Option A

4. Quick Check:

   Filter out exact prefix word from results [OK]

Hint: Filter out exact prefix word after collecting all matches [OK]

Common Mistakes:

• Removing isEnd flag breaks normal word insertion
• Returning only longer words by length may miss valid words
• Returning prefix itself defeats the requirement