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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie.

DSA C++

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

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

Achildren[c]

Bchild[c]

Cchildren.get(c)

Dchild.get(c)

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'child' instead of 'children'.

Trying to call get() which is not a C++ map method.

In a Trie, each node has a map called 'children' that stores the next nodes for each character. We access the child node for character c using children[c].

2fill in blank

medium

Complete the code to check if a prefix exists in the Trie.

DSA C++

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

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

Achildren.get(c)

Bchild[c]

Cchild.get(c)

Dchildren[c]

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong map name 'child'.

Trying to use get() method which is not valid in C++ map.

To check if a prefix exists, we move down the Trie nodes using children[c] for each character c in the prefix.

3fill in blank

hard

Fix the error in the Hash Map prefix search function.

DSA C++

bool hasPrefix(unordered_map<string, bool>& map, string prefix) {
    for (auto& pair : map) {
        if (pair.first.[1](0, prefix.size()) == prefix) {
            return true;
        }
    }
    return false;
}

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

Asubstr

Bsubstring

Cslice

Dsub

Attempts:

3 left

💡 Hint

Common Mistakes

Using substring() which is a JavaScript or Java method.

Using slice() which is not a C++ string method.

In C++, the method to get a substring is substr(start_index, length). substring() or slice() are not valid methods.

4fill in blank

hard

Fill both blanks to create a Trie search function that returns true if a word exists.

DSA C++

bool search(string word) {
    TrieNode* node = root;
    for (char c : word) {
        if (!node->[1].count(c)) {
            return false;
        }
        node = node->[2];
    }
    return node->isEnd;
}

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

Achildren

Bchild

Cchildren[c]

Dchild[c]

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'child' instead of 'children'.

Trying to access child node without indexing by c.

We check if the current node's children map contains the character c using children.count(c). Then we move to the child node using children[c].

5fill in blank

hard

Fill all three blanks to build a Hash Map prefix search that returns true if any key starts with the prefix.

DSA C++

bool hasPrefix(unordered_map<string, bool>& map, string prefix) {
    for (auto& [1] : map) {
        if ([1].first.[2](0, prefix.size()) == prefix) {
            return [3];
        }
    }
    return false;
}

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

Apair

Bsubstr

Ctrue

Dkey

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'key' as loop variable which is not valid for map iteration.

Using substring or slice instead of substr.

Returning false instead of true when prefix matches.

We iterate over the map with 'pair'. Use substr to get the prefix of the key string. Return true if prefix matches.