Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Go - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

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] = &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 a single character as key.

Using the wrong variable like node or t instead of ch.

The loop iterates over each character ch in the word. We use ch as the key to access or create the child node in the Trie.

2fill in blank

medium

Complete the code to check if a word exists in the Trie.

DSA Go

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

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

Aword

Bnode

Cch

Dt

Attempts:

3 left

💡 Hint

Common Mistakes

Checking with the whole word instead of character.

Using wrong variable as key.

We check if the child node for the current character ch exists. If not, the word is not in the Trie.

3fill in blank

hard

Fix the error in the code to find if any word starts with the given prefix.

DSA Go

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

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

Ach

Bnode

Cprefix

Dt

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole prefix string instead of character.

Using wrong variable like node or t.

We must use the current character ch to move to the next child node while checking the prefix.

4fill in blank

hard

Fill both blanks to create a map comprehension that counts characters in a string.

DSA Go

counts := map[rune]int{}
for _, ch := range word {
    counts[ch] [1] 1
}
result := map[rune]int{ch: counts[ch] [2] 0 for ch := range counts}

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

A+=

B-=

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using -= instead of += for counting.

Using - instead of + when copying counts.

We increment the count for each character using += 1. Then we create a new map with counts added to zero using + 0 to copy values.

5fill in blank

hard

Fill all three blanks to create a filtered map of characters with counts greater than zero.

DSA Go

filtered := map[rune]int{ch: counts[ch] for ch := range counts if counts[ch] [1] 0 && ch [2] 'a' && ch [3] '{' }

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

A>

B==

C<

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using == instead of > for counts.

Using wrong comparison operators for character range.

We filter characters with counts greater than zero (>), and characters between 'a' and 'z' inclusive using >= and <.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing many strings?

easy

A. Because Trie can efficiently find all strings with a common prefix

B. Because Hash Map uses less memory than Trie

C. Because Trie stores strings as keys directly without nodes

D. Because Hash Map automatically sorts strings alphabetically

Solution

1. Step 1: Understand Trie prefix search

   Trie stores strings in a tree form where each node represents a character, allowing quick prefix searches.

2. Step 2: Compare with Hash Map capabilities

   Hash Map stores full strings as keys but cannot efficiently find all strings sharing a prefix without checking all keys.

3. Final Answer:

   Because Trie can efficiently find all strings with a common prefix -> Option A

4. Quick Check:

   Trie = Efficient prefix search [OK]

Hint: Trie excels at prefix search, Hash Map does not [OK]

Common Mistakes:

• Thinking Hash Map sorts keys automatically
• Believing Trie uses less memory always
• Confusing Trie nodes with full string keys

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

easy

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

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

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

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

Solution

1. Step 1: Identify correct children type for TrieNode

   Children should map characters (rune) to child nodes (pointer to TrieNode).

2. Step 2: Check isEnd field type

   isEnd should be a boolean indicating if node marks end of a word.

3. Final Answer:

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

4. Quick Check:

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

Hint: Children map keys are runes, isEnd is bool [OK]

Common Mistakes:

• Using wrong map key or value types
• Setting isEnd as string or int instead of bool
• Using slice instead of map for children

3. What will be the output of the following Go code snippet?

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

func main() {
  root := &TrieNode{children: make(map[rune]*TrieNode)}
  word := "cat"
  node := root
  for _, ch := range word {
    if node.children[ch] == nil {
      node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
    }
    node = node.children[ch]
  }
  node.isEnd = true
  
  // Check if 'car' is in Trie
  node = root
  checkWord := "car"
  found := true
  for _, ch := range checkWord {
    if node.children[ch] == nil {
      found = false
      break
    }
    node = node.children[ch]
  }
  if found && node.isEnd {
    println("Found")
  } else {
    println("Not Found")
  }
}

medium

A. Found

B. Not Found

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Insert 'cat' into Trie

   The code adds nodes for 'c', 'a', 't' and marks 't' node as end of word.

2. Step 2: Search for 'car' in Trie

   Traversal finds 'c' and 'a' nodes but no child for 'r', so found becomes false.

3. Final Answer:

   Not Found -> Option B

4. Quick Check:

   Only 'cat' inserted, 'car' missing last node [OK]

Hint: Check each character node; missing means Not Found [OK]

Common Mistakes:

• Assuming partial prefix means found
• Confusing isEnd flag usage
• Expecting runtime errors from nil map access

4. The following Go code tries to insert a word into a Trie but causes a runtime panic. What is the error?

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

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

func main() {
  root := &TrieNode{}
  insert(root, "dog")
}

medium

A. children map is not initialized before use

B. isEnd should be an int, not bool

C. Function insert missing return type

D. root pointer is nil

Solution

1. Step 1: Check initialization of children map

   Root node's children map is nil because it was not created with make(), causing panic on access.

2. Step 2: Understand panic cause

   Accessing or assigning to nil map causes runtime panic in Go.

3. Final Answer:

   children map is not initialized before use -> Option A

4. Quick Check:

   Nil map access causes panic [OK]

Hint: Always initialize maps with make() before use [OK]

Common Mistakes:

• Ignoring map initialization
• Thinking isEnd type causes panic
• Assuming nil pointer for root

5. You want to find all words in a large dictionary that start with the prefix "pre". Why is a Trie better than a Hash Map for this task, and how would you implement the search?

hard

A. Trie uses hashing internally to speed up prefix search

B. Hash Map sorts keys internally, so prefix search is a simple range query

C. Hash Map stores words as linked lists, making prefix search faster

D. Trie stores words by prefix nodes, allowing direct traversal to prefix end; then collect all descendant words

Solution

1. Step 1: Understand Trie prefix traversal

   In Trie, each character is a node; to find prefix "pre", traverse nodes 'p' -> 'r' -> 'e'.

2. Step 2: Collect all words under prefix node

   From the 'e' node, recursively collect all words by exploring child nodes marking word ends.

3. Final Answer:

   Trie stores words by prefix nodes, allowing direct traversal to prefix end; then collect all descendant words -> Option D

4. Quick Check:

   Trie = Direct prefix traversal + collect descendants [OK]

Hint: Traverse prefix nodes, then gather all child words [OK]

Common Mistakes:

• Assuming Hash Map sorts keys automatically
• Thinking Trie uses hashing internally
• Confusing linked list with Hash Map storage