Trie vs Hash Map for Prefix Matching in DSA C# - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Using Trie

Given the following C# code that inserts words into a Trie and searches for a prefix, what is the output printed?

DSA C#

using System;
using System.Collections.Generic;

class TrieNode {
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsWordEnd = false;
}

class Trie {
    private TrieNode root = new TrieNode();

    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];
        }
        node.IsWordEnd = true;
    }

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

class Program {
    static void Main() {
        var trie = new Trie();
        trie.Insert("apple");
        trie.Insert("app");
        trie.Insert("application");
        Console.WriteLine(trie.StartsWith("app"));
        Console.WriteLine(trie.StartsWith("appl"));
        Console.WriteLine(trie.StartsWith("banana"));
    }
}

A

False
False
True

B

True
False
False

C

False
True
False

D

True
True
False

💡 Hint

Think about whether the prefix exists in the inserted words.

The method StartsWith returns true if the prefix exists in the Trie. Since "app", "apple", and "application" are inserted, prefixes "app" and "appl" exist, but "banana" does not.

🧠 Conceptual

intermediate

Time Complexity Comparison for Prefix Search

Which statement correctly compares the time complexity of prefix search in a Trie versus using a Hash Map of all words for prefix matching?

A Trie prefix search is O(k) where k is prefix length; Hash Map prefix search is O(n) where n is number of words

B Trie prefix search is O(n) where n is number of words; Hash Map prefix search is O(k) where k is prefix length

C Both Trie and Hash Map prefix search are O(n) where n is number of words

D Both Trie and Hash Map prefix search are O(k) where k is prefix length

💡 Hint

Consider how each data structure stores and searches prefixes.

A Trie allows prefix search in time proportional to the prefix length (k), because it traverses nodes for each character. A Hash Map storing full words requires checking all words (n) to find matches, so prefix search is O(n).

🔧 Debug

advanced

Identify the Bug in Hash Map Prefix Search

This C# code attempts to find all words starting with a prefix using a Hash Map. What error or issue will occur when running it?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        var words = new Dictionary<string, int> {
            {"apple", 1}, {"app", 2}, {"application", 3}, {"banana", 4}
        };
        string prefix = "app";
        foreach (var word in words.Keys) {
            if (word.StartsWith(prefix))
                Console.WriteLine(word);
        }
    }
}

A SyntaxError due to missing semicolon after dictionary initialization

B No error; prints words starting with 'app'

C Runtime error because Dictionary.Keys cannot be iterated

D No output because StartsWith method is not valid on string

💡 Hint

Check punctuation in dictionary initialization.

The dictionary initialization is missing a semicolon after the closing brace, causing a syntax error.

🚀 Application

advanced

Choosing Data Structure for Large Prefix Queries

You need to build a system that supports millions of words and frequent prefix queries. Which data structure is best and why?

A Use a List of words and scan all for each prefix query for simplicity

B Use a Hash Map storing all words because it uses less memory and prefix search is faster

C Use a Trie because it provides fast prefix search in O(k) time and uses shared prefixes to save space

D Use a Stack to store words and pop words matching prefix

💡 Hint

Think about time efficiency and memory usage for prefix queries.

Trie is best for large datasets with prefix queries because it allows fast prefix search in time proportional to prefix length and saves space by sharing prefixes.

❓ Predict Output

expert

Output of Mixed Trie and Hash Map Operations

What is the output of the following C# code that uses both a Trie and a Hash Map for prefix matching?

DSA C#

using System;
using System.Collections.Generic;

class TrieNode {
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsWordEnd = false;
}

class Trie {
    private TrieNode root = new TrieNode();

    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];
        }
        node.IsWordEnd = true;
    }

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

class Program {
    static void Main() {
        var trie = new Trie();
        var map = new Dictionary<string, int>();
        string[] words = {"cat", "car", "cart", "dog", "dove"};
        foreach (var w in words) {
            trie.Insert(w);
            map[w] = w.Length;
        }
        Console.WriteLine(trie.StartsWith("ca"));
        Console.WriteLine(map.ContainsKey("car"));
        Console.WriteLine(trie.StartsWith("do"));
        Console.WriteLine(map.ContainsKey("cow"));
    }
}

A

False
True
True
False

B

True
True
True
False

C

True
False
True
False

D

True
True
False
True

💡 Hint

Check which words are inserted and keys present in the map.

The Trie contains prefixes "ca" and "do" from inserted words. The map contains keys "car" but not "cow".

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