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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Using Trie

What is the output of the following C++ code that inserts words into a Trie and checks if a prefix exists?

DSA C++

#include <iostream>
#include <unordered_map>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c))
                node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->isEnd = true;
    }

    bool startsWith(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (!node->children.count(c))
                return false;
            node = node->children[c];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    cout << (trie.startsWith("app") ? "Yes" : "No") << endl;
    cout << (trie.startsWith("apl") ? "Yes" : "No") << endl;
    return 0;
}

A

Yes
Yes

B

No
Yes

C

Yes
No

D

No
No

💡 Hint

Think about whether the prefix exists in the inserted words.

The prefix "app" exists because both "apple" and "app" start with it, so output is "Yes". The prefix "apl" does not exist in any inserted word, so output is "No".

🧠 Conceptual

intermediate

Why Use Trie Over Hash Map for Prefix Matching?

Which of the following is the main advantage of using a Trie over a Hash Map for prefix matching?

A Hash Map uses less memory than Trie for prefix matching.

B Trie allows efficient prefix search without storing all prefixes explicitly.

C Trie requires less code to implement than Hash Map.

D Hash Map can store prefixes faster than Trie.

💡 Hint

Think about how prefix search works in both data structures.

Trie stores characters in a tree structure allowing prefix search by traversing nodes, without storing all prefixes explicitly. Hash Map requires storing all prefixes as keys, which is less efficient.

❓ Predict Output

advanced

Output of Prefix Count Using Hash Map

What is the output of this C++ code that counts how many words start with a prefix using a Hash Map?

DSA C++

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    vector<string> words = {"cat", "car", "cart", "dog"};
    unordered_map<string, int> prefixCount;

    for (const string& word : words) {
        for (int i = 1; i <= word.size(); ++i) {
            prefixCount[word.substr(0, i)]++;
        }
    }

    cout << prefixCount["car"] << endl;
    cout << prefixCount["ca"] << endl;
    cout << prefixCount["do"] << endl;
    cout << prefixCount["c"] << endl;
    return 0;
}

A

1
2
1
2

B

2
2
1
2

C

3
3
1
3

D

2
3
1
3

💡 Hint

Count how many words start with each prefix.

"car" is prefix of "car" and "cart" → 2
"ca" is prefix of "cat", "car", "cart" → 3
"do" is prefix of "dog" → 1
"c" is prefix of "cat", "car", "cart" → 3

🔧 Debug

advanced

Identify the Error in Trie Prefix Search

What error will this C++ code produce when checking prefix existence in a Trie?

DSA C++

#include <iostream>
#include <unordered_map>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children[c])
                node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->isEnd = true;
    }

    bool startsWith(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.count(c) == 0)
                return false;
            node = node->children[c];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("hello");
    cout << (trie.startsWith("hel") ? "Yes" : "No") << endl;
    return 0;
}

A Runtime error due to accessing map with operator[] on missing key

B No error, outputs Yes

C Always returns false for any prefix

D Compilation error due to missing semicolon

💡 Hint

Check how operator[] behaves on unordered_map when key is missing.

Using operator[] on unordered_map with a missing key inserts a new entry with default value (nullptr here), so the check 'node->children[c] == nullptr' is true only after insertion, but operator[] itself modifies the map unexpectedly, which can cause logic errors or unexpected behavior.

🧠 Conceptual

expert

Memory Efficiency Comparison Between Trie and Hash Map for Prefix Matching

Which statement best describes memory usage when storing a large dictionary for prefix matching using Trie vs Hash Map?

A Trie uses less memory because it shares common prefixes, while Hash Map stores all prefixes separately.

B Hash Map uses less memory because it stores only full words as keys, not prefixes.

C Trie and Hash Map use about the same memory for prefix matching.

D Hash Map uses less memory because it compresses prefixes automatically.

💡 Hint

Think about how prefixes are stored and shared in each data structure.

Trie stores prefixes in shared nodes, so common prefixes are stored once, saving memory. Hash Map stores each prefix as a separate key, leading to higher memory usage.