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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to add a word to the Trie.

DSA C#

public void Insert(string word) {
    TrieNode node = root;
    foreach (char c in word) {
        if (!node.Children.ContainsKey(c)) {
            node.Children.Add(c, new TrieNode());
        }
        node = node.Children[1];
    }
    node.IsWord = true;
}

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

A.c

B(c)

C{c}

D[c]

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses instead of square brackets to access dictionary elements.

Trying to access a property or method that does not exist on the dictionary.

In C#, to access a value in a dictionary by key, use square brackets [key]. Here, node.Children is a dictionary, so node.Children[c] accesses the child node for character c.

2fill in blank

medium

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

DSA C#

public bool StartsWith(string prefix) {
    TrieNode node = root;
    foreach (char c in prefix) {
        if (!node.Children.ContainsKey(c)) {
            return false;
        }
        node = node.Children[1];
    }
    return true;
}

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

A(c)

B{c}

C[c]

D.c

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses or braces instead of square brackets.

Trying to access a property directly on the dictionary.

To get the child node for character c from the dictionary, use square brackets [c]. This lets us move down the Trie nodes following the prefix characters.

3fill in blank

hard

Fix the error in the HashMap prefix check method.

DSA C#

public bool HasPrefix(string prefix) {
    foreach (string word in words) {
        if (word.[1]) {
            return true;
        }
    }
    return false;
}

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

AStartsWith(prefix)

BContains(prefix)

CEquals(prefix)

DEndsWith(prefix)

Attempts:

3 left

💡 Hint

Common Mistakes

Using Contains which matches anywhere in the word, not just prefix.

Using Equals which requires exact match.

Using EndsWith which checks suffix, not prefix.

To check if a word starts with a prefix, use the StartsWith method. Contains checks for substring anywhere, which is not the same as prefix matching.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps words to their lengths for words starting with 'a'.

DSA C#

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

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

AStartsWith

BLength

CCount

DContains

Attempts:

3 left

💡 Hint

Common Mistakes

Using Contains instead of StartsWith for filtering.

Using Count which is a method for collections, not strings.

Using wrong property for length.

We filter words starting with 'a' using StartsWith, then map each word to its Length property in the dictionary.

5fill in blank

hard

Fill all three blanks to build a dictionary of uppercase words with their lengths for words containing 'e'.

DSA C#

var dict = words.Where(word => word.[1]("e")).ToDictionary(word => word.[2], word => word.[3]);

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

AContains

BToUpper()

CLength

DStartsWith

Attempts:

3 left

💡 Hint

Common Mistakes

Using StartsWith instead of Contains for filtering.

Not converting the word to uppercase for the key.

Using wrong property for length.

We filter words containing 'e' using Contains, then use ToUpper() for keys and Length for values in the dictionary.

Practice

1. Which data structure is generally more efficient for prefix matching when dealing with a large set of strings?

easy

A. Array, because it stores elements in contiguous memory

B. Hash Map, because it stores keys and values with constant time lookup

C. Trie, because it stores prefixes explicitly and allows fast prefix searches

D. Linked List, because it allows sequential access

Solution

1. Step 1: Understand prefix matching requirements

   Prefix matching requires checking if a string starts with a given prefix efficiently.

2. Step 2: Compare Trie and Hash Map for prefix matching

   Trie stores prefixes explicitly, enabling fast prefix search. Hash Map is good for exact key lookup but not efficient for prefix queries.

3. Final Answer:

   Trie, because it stores prefixes explicitly and allows fast prefix searches -> Option C

4. Quick Check:

   Prefix matching = Trie [OK]

Hint: Trie stores prefixes explicitly, ideal for prefix search [OK]

Common Mistakes:

• Thinking hash map supports prefix search efficiently
• Confusing array or linked list with prefix matching
• Ignoring the need for prefix traversal

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

easy

A. public class TrieNode { public int[] Children = new int[26]; public bool IsEndOfWord; }

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

C. public class TrieNode { public List<int> Children; public bool IsEndOfWord; }

D. public class TrieNode { public string Children; public bool IsEndOfWord; }

Solution

1. Step 1: Identify the correct data type for children in TrieNode

   Children should map characters to TrieNode references, so Dictionary is appropriate.

2. Step 2: Check other options for correctness

   List<int> or int[] do not map characters to nodes directly; string is incorrect for children representation.

3. Final Answer:

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

4. Quick Check:

   TrieNode children = Dictionary [OK]

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

Common Mistakes:

• Using List<int> or int[] instead of Dictionary
• Using string type for children
• Not initializing the dictionary

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

var trie = new Trie();
trie.Insert("apple");
trie.Insert("app");
Console.WriteLine(trie.StartsWith("app"));
Console.WriteLine(trie.StartsWith("apl"));

Assuming Trie class has Insert and StartsWith methods implemented correctly.

medium

A. True
False

B. False
True

C. True
True

D. False
False

Solution

1. Step 1: Insert words "apple" and "app" into the Trie

   Both words share prefix "app", so Trie stores nodes for 'a', 'p', 'p', and further for 'l', 'e'.

2. Step 2: Check StartsWith("app") and StartsWith("apl")

   "app" is a prefix present in Trie, so returns True. "apl" is not a prefix of any inserted word, so returns False.

3. Final Answer:

   True False -> Option A

4. Quick Check:

   StartsWith("app")=True, StartsWith("apl")=False [OK]

Hint: Check if prefix exists exactly in Trie nodes [OK]

Common Mistakes:

• Assuming "apl" prefix exists
• Confusing Insert with StartsWith
• Mixing up True/False outputs

4. The following code tries to use a HashMap to check if any word starts with a given prefix. What is the main issue?

var map = new Dictionary();
map["apple"] = true;
map["app"] = true;

bool StartsWith(string prefix) {
    return map.ContainsKey(prefix);
}

Console.WriteLine(StartsWith("app"));
Console.WriteLine(StartsWith("apl"));

medium

A. HashMap does not support prefix search; ContainsKey checks exact keys only

B. The dictionary keys are not initialized properly

C. The StartsWith method should use map.Values instead of map.Keys

D. The code will throw a runtime exception

Solution

1. Step 1: Understand what ContainsKey does in Dictionary

   ContainsKey checks if the exact key exists, not if any key starts with the prefix.

2. Step 2: Identify why prefix search fails

   Since map only stores full words as keys, ContainsKey("app") returns true only if "app" is a full key, not if any key starts with "app".

3. Final Answer:

   HashMap does not support prefix search; ContainsKey checks exact keys only -> Option A

4. Quick Check:

   HashMap prefix search = no [OK]

Hint: ContainsKey checks exact keys, not prefixes [OK]

Common Mistakes:

• Thinking ContainsKey supports prefix matching
• Assuming dictionary keys are incomplete
• Expecting runtime errors

5. You need to implement a system that supports fast prefix queries and also stores frequency counts of words. Which approach is best and why?

hard

A. Hash Map storing only full word frequencies, no prefix support

B. Hash Map with prefix keys, but inefficient for large prefix sets

C. Trie with frequencies only at leaf nodes, no prefix counts

D. Trie with frequency counts at each node for prefix frequency queries

Solution

1. Step 1: Analyze prefix query and frequency requirements

   We want to query frequencies of prefixes, not just full words.

2. Step 2: Evaluate each approach

   A Trie with frequency counts at each node allows quick prefix frequency queries. Hash Map with full words only cannot query prefixes efficiently. Trie with frequencies only at leaves misses prefix counts. Hash Map with prefix keys is inefficient for many prefixes.

3. Final Answer:

   Trie with frequency counts at each node for prefix frequency queries -> Option D

4. Quick Check:

   Prefix frequency queries = Trie with node counts [OK]

Hint: Store counts at each Trie node for prefix frequency queries [OK]

Common Mistakes:

• Using Hash Map only for prefix queries
• Storing frequencies only at leaf nodes
• Assuming prefix keys in Hash Map scale well