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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a character into the Trie node's children dictionary.

DSA C#

node.Children[[1]] = new TrieNode();

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

Anode

Bi

Cword[i]

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using the index i instead of the character.

Using the whole word instead of a single character.

We use the current character word[i] as the key to insert into the children dictionary.

2fill in blank

medium

Complete the code to check if the Trie node has a child for the current character.

DSA C#

if (!node.Children.ContainsKey([1]))

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

Aword

Bi

Cnode

Dword[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for the whole word instead of a single character.

Using the index i instead of the character.

We check if the children dictionary contains the current character word[i] as a key.

3fill in blank

hard

Fix the error in the code to mark the end of a word in the Trie.

DSA C#

node.IsEndOfWord = [1];

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

Afalse

Btrue

Cnull

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting IsEndOfWord to false or null.

Using numeric values instead of boolean.

We set IsEndOfWord to true to mark that the current node represents the end of a valid word.

4fill in blank

hard

Fill both blanks to complete the code that searches for a word in the Trie.

DSA C#

for (int i = 0; i < word.Length; i++) {
    if (!node.Children.ContainsKey([1])) {
        return false;
    }
    node = node.Children[[2]];
}

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

Aword[i]

Bword

Ci

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole word or index instead of the character.

Using different keys for check and access.

We use word[i] to check and access the child node for each character in the word.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps words to their lengths only if length is greater than 3.

DSA C#

var result = words.Where([3] => [2] > 3).ToDictionary([3] => [1], [3] => [2]);

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

Aword

Bword.Length

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Using length as a variable without defining it.

Mixing key and value positions.

We map each word (key) to its length (value) for words longer than 3 characters.

Practice

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

easy

A. Because Trie efficiently supports prefix-based searches and auto-completion

B. Because Trie uses less memory than a Hash Map in all cases

C. Because Hash Maps cannot store strings as keys

D. Because Trie is faster for exact string lookups than Hash Map

Solution

1. Step 1: Understand Trie and Hash Map capabilities

   Trie stores strings in a tree form, allowing quick prefix searches. Hash Map stores keys but does not support prefix queries efficiently.

2. Step 2: Compare prefix search support

   Trie can find all strings with a given prefix quickly, which Hash Map cannot do without checking all keys.

3. Final Answer:

   Because Trie efficiently supports prefix-based searches and auto-completion -> Option A

4. Quick Check:

   Prefix search = Trie advantage [OK]

Hint: Trie = prefix search; Hash Map = exact key only [OK]

Common Mistakes:

• Thinking Hash Map cannot store strings as keys
• Believing Trie always uses less memory
• Assuming Trie is faster for exact lookups

2. Which of the following is the correct way to declare a Trie node class in C#?

easy

A. public class TrieNode { public string Children; public bool IsEnd; }

B. public class TrieNode { public List<int> Children; public bool IsWord; }

C. public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord; }

D. public class TrieNode { public int[] Children = new int[26]; public bool End; }

Solution

1. Step 1: Identify correct data type for children

   Trie children should map characters to TrieNode objects, so Dictionary is correct.

2. Step 2: Check boolean flag for word end

   Boolean IsEndOfWord indicates if node marks end of a word, which is standard.

3. Final Answer:

   public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord; } -> Option C

4. Quick Check:

   Children map chars to nodes + end flag = public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord; } [OK]

Hint: Trie children map chars to nodes using Dictionary [OK]

Common Mistakes:

• Using List<int> instead of Dictionary for children
• Using int array without node references
• Using string type for children

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

var trie = new Trie();
trie.Insert("cat");
trie.Insert("car");
trie.Insert("dog");
var result = trie.StartsWith("ca");
Console.WriteLine(string.Join(",", result));

Assuming StartsWith returns all words starting with the prefix.

medium

A. "dog"

B. "cat,car"

C. "cat"

D. "car,dog"

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted. Trie stores them by characters.

2. Step 2: Call StartsWith("ca")

   StartsWith returns all words starting with "ca", which are "cat" and "car".

3. Final Answer:

   "cat,car" -> Option B

4. Quick Check:

   Prefix "ca" matches "cat" and "car" [OK]

Hint: StartsWith("ca") returns all words beginning with "ca" [OK]

Common Mistakes:

• Returning only one word instead of all matches
• Including words without the prefix
• Confusing output order

4. Identify the bug in this Trie insertion method in C#:

public void Insert(string word) {
  var node = root;
  foreach (var ch in word) {
    if (!node.Children.ContainsKey(ch)) {
      node.Children[ch] = new TrieNode();
    }
    node = node.Children[ch];
  }
}

medium

A. Should use node.Children.Add(ch) instead of assignment

B. Children dictionary should be List<char> instead of Dictionary

C. The foreach loop should iterate backwards

D. Missing setting IsEndOfWord = true after insertion

Solution

1. Step 1: Review insertion logic

   Code correctly creates nodes for each character if missing and moves node pointer.

2. Step 2: Check for marking word end

   Code does not mark the last node as end of a word, so search may fail to recognize complete words.

3. Final Answer:

   Missing setting IsEndOfWord = true after insertion -> Option D

4. Quick Check:

   Mark word end after insertion = Missing setting IsEndOfWord = true after insertion [OK]

Hint: Always mark last node as word end after insertion [OK]

Common Mistakes:

• Not marking end of word
• Using wrong data structure for children
• Incorrect loop direction

5. You want to store a large dictionary of English words and quickly find all words starting with a given prefix. Why is a Trie better than a Hash Map for this task, and what limitation of Hash Map does Trie overcome?

hard

A. Trie stores words in a prefix tree allowing fast prefix queries; Hash Map can't efficiently find keys by prefix

B. Trie uses less memory than Hash Map for all datasets; Hash Map is always slower for lookups

C. Hash Map cannot store string keys longer than 10 characters; Trie has no such limit

D. Trie automatically sorts words alphabetically; Hash Map stores keys unordered

Solution

1. Step 1: Understand Trie structure for prefix queries

   Trie organizes words by shared prefixes, enabling quick retrieval of all words starting with a prefix.

2. Step 2: Identify Hash Map limitation

   Hash Map stores keys but cannot efficiently retrieve all keys sharing a prefix without scanning all keys.

3. Final Answer:

   Trie stores words in a prefix tree allowing fast prefix queries; Hash Map can't efficiently find keys by prefix -> Option A

4. Quick Check:

   Prefix search efficiency = Trie advantage [OK]

Hint: Trie = prefix queries; Hash Map = exact key only, no prefix search [OK]

Common Mistakes:

• Thinking Hash Map can't store long strings
• Assuming Trie always uses less memory
• Believing Hash Map is slower for exact lookups