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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the root node of a Trie.

DSA C

struct TrieNode* root = malloc(sizeof(struct TrieNode));
root->isEndOfWord = [1];

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

ANULL

B1

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting isEndOfWord to 1 by mistake.

Using NULL instead of 0 for boolean flags.

The root node's isEndOfWord should be set to 0 because it does not represent the end of any word initially.

2fill in blank

medium

Complete the code to check if a character exists as a child in the Trie node.

DSA C

if (node->children[[1]] != NULL) {
    // character exists
}

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

Ac - 'a'

B'a' - 'a'

Cc + 'a'

D'c' - 'a'

Attempts:

3 left

💡 Hint

Common Mistakes

Using character literals instead of variables.

Adding 'a' instead of subtracting.

We use c - 'a' to convert the character c to an index between 0 and 25 for the children array.

3fill in blank

hard

Fix the error in the function that inserts a word into the Trie by completing the blank.

DSA C

void insert(struct TrieNode* root, const char* word) {
    struct TrieNode* node = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (node->children[index] == NULL) {
            node->children[index] = malloc(sizeof(struct TrieNode));
            memset(node->children[index], 0, sizeof(struct TrieNode));
        }
        node = node->children[[1]];
    }
    node->isEndOfWord = 1;
}

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

Aindex

Bword[i]

Ci

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using the loop variable i as index.

Using the character directly as index.

The variable index holds the correct child index for the current character, so we use it to move to the next node.

4fill in blank

hard

Fill in the blank to create a hash map lookup for prefix matching.

DSA C

int prefix_exists(const char* prefix, HashMap* map) {
    int length = strlen(prefix);
    for (int i = 0; i < length; i++) {
        if (hash_map_get(map, prefix[[1]]) == NULL) {
            return 0;
        }
    }
    return 1;
}

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

A0

Bi

Cprefix[i]

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as index inside the loop instead of i.

Using length as index which is out of bounds.

The loop variable i is used to access each character in the prefix. The hash map key is the character at prefix[i].

5fill in blank

hard

Fill all three blanks to build a Trie node and insert a word.

DSA C

struct TrieNode* create_node() {
    struct TrieNode* node = malloc(sizeof(struct TrieNode));
    for (int i = 0; i < [1]; i++) {
        node->children[i] = [2];
    }
    node->isEndOfWord = [3];
    return node;
}

void insert_word(struct TrieNode* root, const char* word) {
    struct TrieNode* node = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (node->children[index] == NULL) {
            node->children[index] = create_node();
        }
        node = node->children[index];
    }
    node->isEndOfWord = 1;
}

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

A26

BNULL

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong size for children array.

Setting isEndOfWord to 1 when creating a node.

We initialize 26 children for each letter of the alphabet, set each child pointer to NULL, and mark isEndOfWord as 0 initially.

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