Trie vs Hash Map for Prefix Matching in DSA Go - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize a new Trie node in Go.

DSA Go

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

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

Afalse

Btrue

Cnil

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting isEnd to true initially, which incorrectly marks the node as end of a word.

The isEnd field should be initialized to false when creating a new Trie node because initially it does not mark the end of a word.

2fill in blank

medium

Complete the code to insert a word into the Trie.

DSA Go

func (t *TrieNode) Insert(word string) {
    node := t
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = NewTrieNode()
        }
        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 'word' or 'node' instead of 'ch' to index children.

We use the current character 'ch' to move to the child node in the Trie.

3fill in blank

hard

Fix the error in the prefix search function to correctly check if a prefix exists in the Trie.

DSA Go

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

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

Anode.isEnd

Btrue

Cnil

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true when a character is missing, which incorrectly says prefix exists.

If a character in the prefix is missing in the Trie, the prefix does not exist, so return false.

4fill in blank

hard

Fill both blanks to create a Hash Map based prefix search function.

DSA Go

func PrefixExists(words []string, prefix string) bool {
    wordMap := make(map[string]bool)
    for _, word := range words {
        wordMap[word] = true
    }
    for w := range wordMap {
        if len(w) >= len(prefix) && w[:[1]] == prefix {
            return [2]
        }
    }
    return false
}

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

Alen(prefix)

Btrue

Cfalse

Dlen(w)

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(w) instead of len(prefix) for slicing.

Returning false inside the loop instead of true.

We compare the first len(prefix) characters of each word to the prefix. If matched, return true.

5fill in blank

hard

Fill all three blanks to implement a Trie prefix search that returns true if any word starts with the prefix.

DSA Go

func (t *TrieNode) SearchPrefix(prefix string) bool {
    node := t
    for _, ch := range prefix {
        if node.children[[1]] == nil {
            return [2]
        }
        node = node.children[ch]
    }
    return [3]
}

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

Ach

Bfalse

Ctrue

Dprefix

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prefix' instead of 'ch' to index children.

Returning true too early or false after successful match.

Use 'ch' to check children. Return false if missing. Return true if prefix fully matched.