Trie vs Hash Map for Prefix Matching in DSA C - Build Both Approaches

Trie vs Hash Map for Prefix Matching

📖 Scenario: You are building a simple search feature for a phone contact list app. Users want to find contacts quickly by typing the first few letters of a name.Two common ways to do this are using a Trie or a Hash Map. This project will help you understand how to store and find names by their prefixes using these two methods.

🎯 Goal: Build a small program in C that stores a list of contact names and then finds all contacts starting with a given prefix using a simple array loop approach.You will create the data, set up a prefix to search, write the logic to find matching names, and print the results.

📋 What You'll Learn

Create an array of strings with exact contact names

Create a prefix string variable to search

Write a function to find and print all names starting with the prefix using a simple loop

Print the matching names exactly as found

💡 Why This Matters

🌍 Real World

Searching contacts quickly by prefix is common in phone apps, messaging apps, and search engines.

💼 Career

Understanding prefix matching helps in building efficient search features and autocomplete systems used in many software products.

1

Create the contact list

Create an array of strings called contacts with these exact names: "Alice", "Bob", "Charlie", "David", "Eve".

DSA C

# Create the contacts array with the given names
// Your code here

Hint

Use char *contacts[] = {"Alice", "Bob", "Charlie", "David", "Eve"}; to create the array.

2

Set the prefix to search

Create a string variable called prefix and set it to the exact value "Da".

DSA C

#include 

char *contacts[] = {"Alice", "Bob", "Charlie", "David", "Eve"};
int contacts_count = 5;

// Create the prefix string
// Your code here

Hint

Use char prefix[] = "Da"; to create the prefix string.

3

Write the prefix matching function

Write a function called print_matches that takes char *contacts[], int contacts_count, and char prefix[] as parameters. Inside it, use a for loop with variable i from 0 to contacts_count - 1. For each contact, use strncmp to compare the start of the contact with prefix. If they match, print the contact followed by a newline.

DSA C

#include 
#include 

char *contacts[] = {"Alice", "Bob", "Charlie", "David", "Eve"};
int contacts_count = 5;

char prefix[] = "Da";

// Write the print_matches function
// Your code here

Hint

Use strncmp to compare the prefix with the start of each contact.

4

Print the matching contacts

Call the function print_matches with contacts, contacts_count, and prefix. This will print all contacts starting with the prefix.

DSA C

#include 
#include 

char *contacts[] = {"Alice", "Bob", "Charlie", "David", "Eve"};
int contacts_count = 5;

char prefix[] = "Da";

void print_matches(char *contacts[], int contacts_count, char prefix[]) {
    int prefix_len = strlen(prefix);
    for (int i = 0; i < contacts_count; i++) {
        if (strncmp(contacts[i], prefix, prefix_len) == 0) {
            printf("%s\n", contacts[i]);
        }
    }
}

int main() {
    // Call print_matches here
    // Your code here
    return 0;
}

Hint

Call print_matches(contacts, contacts_count, prefix); inside main.

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