Why Trie Exists and What Hash Map Cannot Do for Strings in DSA C++ - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a character into the Trie node's children.

DSA C++

node->children[[1]] = new TrieNode();

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

Aword[i]

Bi

Cnode

Dchildren

Attempts:

3 left

💡 Hint

Common Mistakes

Using the index 'i' instead of the character.

Using the node pointer instead of a character key.

We use the current character of the word (word[i]) as the key to insert into the children map.

2fill in blank

medium

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

DSA C++

if (node->children.find([1]) == node->children.end()) return false;

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

Anode

Bprefix[i]

Ci

Dchildren

Attempts:

3 left

💡 Hint

Common Mistakes

Using the index 'i' instead of the character.

Using the node pointer or children map incorrectly.

We check if the current character of the prefix exists in the children map.

3fill in blank

hard

Fix the error in the code to mark the end of a word in the Trie.

DSA C++

node->[1] = true;

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

Aend

Bchildren

CisWord

DwordEnd

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'children' which is a map, not a boolean.

Using 'end' or 'wordEnd' which may not be defined.

The boolean flag 'isWord' marks the end of a valid word in the Trie.

4fill in blank

hard

Fill both blanks to complete the Trie search function for a word.

DSA C++

for (int i = 0; i < word.size(); i++) {
    if (node->children.find([1]) == node->children.end()) return false;
    node = node->children[[2]];
}

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

Aword[i]

Bi

Cnode

Dchildren

Attempts:

3 left

💡 Hint

Common Mistakes

Using different keys for find and indexing.

Using the index 'i' instead of the character.

Both blanks require the current character of the word to traverse the Trie correctly.

5fill in blank

hard

Fill all three blanks to complete the code that builds an unordered_map of words longer than 3 characters to their lengths.

DSA C++

std::unordered_map<std::string, int> lengths;
for (const auto& [3] : words) {
    if ([2] > 3) {
        lengths[[1]] = [2];
    }
}

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

Aword

Bword.length()

Cwords

Dw

Attempts:

3 left

💡 Hint

Common Mistakes

Using the collection name instead of the loop variable.

Using the wrong property for length.

We map each word to its length if the length is greater than 3. 'word' is the loop variable.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing a large set of strings?

easy

A. Because Trie is faster for all types of lookups compared to Hash Map

B. Because Trie uses less memory than Hash Map for all data types

C. Because Hash Map cannot store strings as keys

D. Because Trie supports efficient prefix search which Hash Map cannot do easily

Solution

1. Step 1: Understand Trie and Hash Map capabilities

   Trie stores strings in a tree form allowing prefix-based queries efficiently. Hash Map stores keys but does not support prefix queries efficiently.

2. Step 2: Compare prefix search ability

   Trie can quickly find all strings with a given prefix, while Hash Map requires checking each key individually.

3. Final Answer:

   Because Trie supports efficient prefix search which Hash Map cannot do easily -> Option D

4. Quick Check:

   Prefix search = Trie advantage [OK]

Hint: Trie excels at prefix search, Hash Map does not [OK]

Common Mistakes:

• Thinking Hash Map cannot store strings as keys
• Assuming Trie always uses less memory
• Believing Trie is faster for all lookups

2. Which of the following is the correct way to declare a Trie node in C++ for lowercase English letters?

easy

A. struct TrieNode { TrieNode* children[26]; bool isEnd; };

B. struct TrieNode { map children; bool isEnd; };

C. struct TrieNode { vector children(26); bool isEnd; };

D. struct TrieNode { TrieNode children[26]; bool isEnd; };

Solution

1. Step 1: Understand Trie node structure for fixed alphabet

   For lowercase English letters, an array of 26 pointers is common to represent children nodes.

2. Step 2: Check syntax correctness

   struct TrieNode { TrieNode* children[26]; bool isEnd; }; correctly declares an array of 26 TrieNode pointers and a boolean flag.

3. Final Answer:

   struct TrieNode { TrieNode* children[26]; bool isEnd; }; -> Option A

4. Quick Check:

   Array of pointers + bool flag = struct TrieNode { TrieNode* children[26]; bool isEnd; }; [OK]

Hint: Use array of pointers for fixed alphabets in Trie nodes [OK]

Common Mistakes:

• Using vector with parentheses instead of braces
• Declaring children as objects instead of pointers
• Using map when array is simpler for fixed alphabets

3. Consider the following C++ code snippet using a Trie to insert and search strings. What will be the output?

struct TrieNode {
  TrieNode* children[26] = {nullptr};
  bool isEnd = false;
};

class Trie {
  TrieNode* root;
public:
  Trie() { root = new TrieNode(); }
  void insert(string word) {
    TrieNode* node = root;
    for (char c : word) {
      int idx = c - 'a';
      if (!node->children[idx])
        node->children[idx] = new TrieNode();
      node = node->children[idx];
    }
    node->isEnd = true;
  }
  bool search(string word) {
    TrieNode* node = root;
    for (char c : word) {
      int idx = c - 'a';
      if (!node->children[idx]) return false;
      node = node->children[idx];
    }
    return node->isEnd;
  }
};

int main() {
  Trie trie;
  trie.insert("apple");
  cout << trie.search("app") << " ";
  cout << trie.search("apple") << " ";
  trie.insert("app");
  cout << trie.search("app") << endl;
  return 0;
}

medium

A. 1 0 0

B. 0 1 1

C. 0 0 1

D. 1 1 1

Solution

1. Step 1: Trace insertions and searches

   After inserting "apple", searching "app" returns false because "app" is not marked as end. Searching "apple" returns true. After inserting "app", searching "app" returns true.

2. Step 2: Match outputs with options

   Outputs are: 0 (false), 1 (true), 1 (true) matching 0 1 1.

3. Final Answer:

   0 1 1 -> Option B

4. Quick Check:

   Search "app" before insert = 0, after insert = 1 [OK]

Hint: Check isEnd flag for exact word match in Trie search [OK]

Common Mistakes:

• Assuming prefix search returns true without isEnd
• Confusing insert order effects
• Ignoring isEnd flag in search

4. The following Trie insertion code has a bug. What is the error?

void insert(string word) {
  TrieNode* node = root;
  for (int i = 0; i <= word.size(); i++) {
    int idx = word[i] - 'a';
    if (!node->children[idx])
      node->children[idx] = new TrieNode();
    node = node->children[idx];
  }
  node->isEnd = true;
}

medium

A. Loop runs one extra iteration causing out-of-bounds access

B. Children array is not initialized to nullptr

C. isEnd flag is set before last character insertion

D. Index calculation should be 'a' - word[i] instead of word[i] - 'a'

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= word.size(), which means it accesses word[word.size()] causing out-of-bounds error.

2. Step 2: Identify correct loop condition

   The loop should run i < word.size() to avoid invalid access.

3. Final Answer:

   Loop runs one extra iteration causing out-of-bounds access -> Option A

4. Quick Check:

   Loop boundary off by one = Loop runs one extra iteration causing out-of-bounds access [OK]

Hint: Use i < size(), not i <= size() for string indexing [OK]

Common Mistakes:

• Ignoring off-by-one errors in loops
• Confusing index calculation signs
• Assuming children array auto-initializes

5. You want to find all words in a dictionary that start with a given prefix efficiently. Why is a Trie better than a Hash Map for this task, and how would you implement the prefix search?

hard

A. Trie stores words in sorted order; implement prefix search by binary search on keys

B. Hash Map stores keys with prefix hashing; implement prefix search by hashing prefix and returning all keys

C. Trie stores words in a tree allowing prefix traversal; implement prefix search by traversing nodes for prefix then DFS for all descendants

D. Hash Map supports prefix search natively; implement prefix search by direct lookup

Solution

1. Step 1: Understand Trie prefix storage

   Trie nodes represent characters; prefix corresponds to a path in the Trie. This allows direct traversal to prefix node.

2. Step 2: Implement prefix search

   Traverse Trie nodes for prefix characters, then perform DFS from that node to collect all words starting with prefix.

3. Step 3: Compare with Hash Map

   Hash Map keys are unordered; no direct way to find all keys with a prefix without checking all keys.

4. Final Answer:

   Trie stores words in a tree allowing prefix traversal; implement prefix search by traversing nodes for prefix then DFS for all descendants -> Option C

5. Quick Check:

   Prefix traversal + DFS = Trie advantage [OK]

Hint: Use Trie traversal + DFS for prefix search, Hash Map can't do this fast [OK]

Common Mistakes:

• Assuming Hash Map supports prefix search directly
• Confusing Trie with sorted array binary search
• Ignoring need to explore descendants after prefix