Trie vs Hash Map for Prefix Matching in DSA C - Key Differences

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure that stores strings by sharing common prefixes. Each node represents a character, and paths from root to nodes form words or prefixes.

beginner

How does a Hash Map handle prefix matching?

A Hash Map stores complete keys and values. For prefix matching, it requires checking all keys to find those starting with the prefix, which can be slow for large data.

intermediate

Why is Trie more efficient than Hash Map for prefix matching?

Trie allows direct traversal along the prefix characters, quickly reaching all words with that prefix without scanning all keys, making prefix queries faster.

intermediate

What is a downside of using Trie compared to Hash Map?

Trie can use more memory because it stores nodes for each character, even if some prefixes are rare, while Hash Map stores only full keys.

beginner

In what scenario is Hash Map preferred over Trie for prefix matching?

When the dataset is small or prefix queries are rare, Hash Map is simpler and uses less memory, making it a better choice than Trie.

Which data structure allows fast prefix matching by traversing characters?

A Array

B Hash Map

C Trie

D Stack

Trie stores characters in nodes allowing direct prefix traversal.

What is a main disadvantage of using Hash Map for prefix matching?

A Uses too much memory

B Needs to scan all keys for prefix

C Cannot store strings

D Slow insertion

Hash Map requires checking all keys to find prefix matches.

Which data structure typically uses more memory for prefix matching?

A Trie

B Hash Map

C Linked List

D Queue

Trie stores nodes for each character, increasing memory use.

When is Hash Map preferred over Trie for prefix matching?

A Small dataset or rare prefix queries

B Large dataset with many prefixes

C When memory is unlimited

D When keys are numeric

Hash Map is simpler and efficient for small or infrequent prefix queries.

What does each node in a Trie represent?

A A hash value

B A full word

C A number

D A character

Each Trie node represents a single character.

Explain how Trie and Hash Map differ in handling prefix matching.

Think about how each structure stores and searches strings.

Describe scenarios where Trie is better than Hash Map and vice versa for prefix matching.

Consider dataset size, query frequency, and memory.

Practice

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

easy

A. Trie, because it stores characters in a tree structure allowing fast prefix search

B. Hash Map, because it stores keys with direct access for any substring

C. Array, because it stores elements sequentially for quick prefix lookup

D. Stack, because it allows last-in-first-out access which helps prefix matching

Solution

1. Step 1: Understand prefix matching requirement

   Prefix matching means finding all strings starting with a given prefix quickly.

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

   Trie stores characters in nodes along paths, enabling fast prefix traversal. Hash Map is good for exact key lookup but not efficient for prefix search.

3. Final Answer:

   Trie, because it stores characters in a tree structure allowing fast prefix search -> Option A

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Trie is best for prefix search, Hash Map for exact keys [OK]

Common Mistakes:

• Thinking Hash Map supports prefix search efficiently
• Confusing array or stack with prefix matching
• Assuming Hash Map stores substrings as keys

2. Which of the following is the correct way to insert a word into a Trie node in C?

easy

A. node->children[word[i] - 'a'] = createNode();

B. node[word[i]] = createNode();

C. node->children[word[i]] = createNode();

D. node.children[word[i] - 'a'] = createNode();

Solution

1. Step 1: Understand Trie node children indexing

   Children array is indexed by character offset from 'a', so use word[i] - 'a'.

2. Step 2: Use correct pointer syntax in C

   Since node is a pointer, use '->' to access children array.

3. Final Answer:

   node->children[word[i] - 'a'] = createNode(); -> Option A

4. Quick Check:

   Pointer access + char offset = node->children[word[i] - 'a'] = createNode(); [OK]

Hint: Use '->' for pointer and subtract 'a' for index [OK]

Common Mistakes:

• Using dot instead of arrow for pointer
• Not subtracting 'a' from character
• Using character directly as index

3. Given the following C code snippet for prefix search using a Trie, what will be the output?

TrieNode* root = createNode();
insert(root, "apple");
insert(root, "app");
insert(root, "bat");

printf("%d", startsWith(root, "app"));
printf("%d", startsWith(root, "bat"));
printf("%d", startsWith(root, "cat"));

Assume startsWith returns 1 if prefix exists, else 0.

medium

A. 111

B. 110

C. 101

D. 100

Solution

1. Step 1: Analyze inserted words and prefixes

   Words inserted: "apple", "app", "bat". Prefixes checked: "app", "bat", "cat".

2. Step 2: Check prefix existence

   "app" is prefix of "apple" and "app" -> returns 1. "bat" is inserted word -> returns 1. "cat" not inserted -> returns 0.

3. Final Answer:

   110 -> Option B

4. Quick Check:

   Prefix found = 1,1,0 [OK]

Hint: Check if prefix matches any inserted word start [OK]

Common Mistakes:

• Assuming startsWith returns count instead of boolean
• Confusing prefix with exact match
• Ignoring that 'cat' was not inserted

4. The following C code attempts to check if a prefix exists in a Trie but always returns 0. What is the bug?

int startsWith(TrieNode* root, char* prefix) {
    TrieNode* node = root;
    for (int i = 0; prefix[i]; i++) {
        if (node->children[prefix[i]] == NULL) {
            return 0;
        }
        node = node->children[prefix[i]];
    }
    return 1;
}

medium

A. Returning 1 instead of 0 when prefix is empty

B. Not checking if root is NULL before loop

C. Indexing children array without subtracting 'a' from prefix[i]

D. Using prefix[i] instead of prefix[i] - 'a' in loop condition

Solution

1. Step 1: Identify children array indexing

   Children array is indexed by character offset from 'a', so must use prefix[i] - 'a'.

2. Step 2: Explain impact of wrong indexing

   Using prefix[i] directly accesses out-of-bound indices, causing NULL always and returning 0.

3. Final Answer:

   Indexing children array without subtracting 'a' from prefix[i] -> Option C

4. Quick Check:

   Correct indexing = prefix[i] - 'a' [OK]

Hint: Always subtract 'a' when indexing children array [OK]

Common Mistakes:

• Forgetting to subtract 'a' from character
• Not checking for NULL root
• Confusing loop condition with indexing

5. You want to implement a prefix search system for millions of English words. Which approach is better and why?

1. Use a Trie to store all words and traverse nodes for prefix queries.
2. Use a Hash Map storing all prefixes as keys with lists of words as values.

Choose the best option.

hard

A. Hash Map, because it uses less memory than Trie

B. Hash Map, because it stores all prefixes explicitly for instant lookup

C. Trie, because it requires storing all prefixes as keys explicitly

D. Trie, because it uses less memory and supports fast prefix traversal

Solution

1. Step 1: Compare memory usage of Trie vs Hash Map for prefixes

   Trie stores characters in shared nodes, avoiding duplicate prefix storage. Hash Map stores every prefix explicitly, causing large memory use.

2. Step 2: Compare prefix query speed and scalability

   Trie allows fast traversal by characters without storing all prefixes. Hash Map lookup is fast but building and storing all prefixes is expensive and slow.

3. Final Answer:

   Trie, because it uses less memory and supports fast prefix traversal -> Option D

4. Quick Check:

   Memory efficient prefix search = Trie [OK]

Hint: Trie shares prefix nodes, Hash Map stores all prefixes explicitly [OK]

Common Mistakes:

• Assuming Hash Map uses less memory for prefixes
• Thinking Trie stores all prefixes as separate keys
• Ignoring scalability for millions of words