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 Trie insertion and prefix search code, what is the output of searching for prefix "app"?

DSA C

typedef struct TrieNode {
    struct TrieNode* children[26];
    int isEndOfWord;
} TrieNode;

TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = 0;
    for (int i = 0; i < 26; i++) node->children[i] = NULL;
    return node;
}

void insert(TrieNode* root, const char* key) {
    TrieNode* pCrawl = root;
    for (int i = 0; key[i] != '\0'; i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = 1;
}

int startsWith(TrieNode* root, const char* prefix) {
    TrieNode* pCrawl = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';
        if (!pCrawl->children[index])
            return 0;
        pCrawl = pCrawl->children[index];
    }
    return 1;
}

int main() {
    TrieNode* root = getNode();
    insert(root, "apple");
    insert(root, "app");
    insert(root, "application");
    printf("%d\n", startsWith(root, "app"));
    return 0;
}

A Compilation error

B 0

C 3

D 1

💡 Hint

Check if the prefix "app" exists in the Trie after insertions.

The prefix "app" is present because words "app", "apple", and "application" were inserted. The function returns 1 if prefix exists.

❓ Predict Output

intermediate

Output of prefix search using Hash Map

Given the following code using a hash map to store words and check prefix existence, what is the output of searching for prefix "ban"?

DSA C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_WORDS 5

int startsWith(char* words[], int n, const char* prefix) {
    int len = strlen(prefix);
    for (int i = 0; i < n; i++) {
        if (strncmp(words[i], prefix, len) == 0) {
            return 1;
        }
    }
    return 0;
}

int main() {
    char* words[MAX_WORDS] = {"banana", "band", "bandana", "apple", "application"};
    printf("%d\n", startsWith(words, MAX_WORDS, "ban"));
    return 0;
}

A 1

B Compilation error

C 0

D Runtime error

💡 Hint

Check if any word starts with "ban" in the array.

Words "banana", "band", and "bandana" start with "ban", so the function returns 1.

🧠 Conceptual

advanced

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

Which of the following best explains why a Trie is more efficient than a Hash Map for prefix matching in large datasets?

A Trie stores characters in a tree structure allowing prefix search in O(k) time where k is prefix length, while Hash Map requires checking all keys.

B Trie sorts all words alphabetically, which Hash Map cannot do.

C Hash Map cannot store strings as keys, so Trie is the only option.

D Trie uses less memory than Hash Map because it stores only unique words.

💡 Hint

Think about how prefix search works in both data structures.

Trie allows direct traversal by characters of the prefix, making search time proportional to prefix length. Hash Map requires checking all keys or additional indexing.

🔧 Debug

advanced

Identify the bug in Trie prefix search

What error will the following Trie prefix search code produce when searching for prefix "cat" if the Trie is empty?

DSA C

int startsWith(TrieNode* root, const char* prefix) {
    TrieNode* pCrawl = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';
        if (!pCrawl->children[index])
            return 0;
        pCrawl = pCrawl->children[index];
    }
    return 1;
}

int main() {
    TrieNode* root = NULL;
    printf("%d\n", startsWith(root, "cat"));
    return 0;
}

A Returns 1 incorrectly

B Returns 0 without error

C Segmentation fault (accessing NULL pointer)

D Compilation error due to missing TrieNode definition

💡 Hint

Check what happens if root is NULL before accessing children.

The code does not check if root is NULL before accessing children, causing a segmentation fault when dereferencing NULL pointer.

🚀 Application

expert

Choosing data structure for autocomplete system

You are designing an autocomplete system for a search engine with millions of queries. Which data structure is best suited for fast prefix matching and why?

A Hash Map, because it stores all queries as keys and allows O(1) lookup for any prefix.

B Trie, because it provides fast prefix search in O(k) time and efficient memory usage with shared prefixes.

C Array of strings sorted alphabetically, because binary search can find prefixes quickly.

D Linked list of queries, because it is simple to implement and traverse.

💡 Hint

Consider time complexity and memory efficiency for prefix search in large datasets.

Trie is ideal for autocomplete because it allows fast prefix search by traversing nodes per character, sharing common prefixes to save memory. Hash Map cannot do prefix search efficiently. Sorted arrays require O(log n) binary search but less efficient for prefix enumeration. Linked lists are slow for search.

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