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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Using Trie

What is the output of the following Python code that uses a Trie to find words with a given prefix?

DSA Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.end_of_word = True

    def _dfs(self, node, prefix, results):
        if node.end_of_word:
            results.append(prefix)
        for char, child_node in node.children.items():
            self._dfs(child_node, prefix + char, results)

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        results = []
        self._dfs(node, prefix, results)
        return results

trie = Trie()
words = ["apple", "app", "application", "bat", "batch", "batman"]
for w in words:
    trie.insert(w)

print(trie.starts_with("app"))

A ["app"]

B ["apple", "application"]

C ["app", "apple", "application"]

D []

💡 Hint

Think about all words inserted that start with 'app'.

The Trie stores all words. The starts_with method finds the node matching the prefix and collects all words below it. Words starting with 'app' are 'app', 'apple', and 'application'.

🧠 Conceptual

intermediate

Why Use Trie Over Hash Map for Prefix Matching?

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

A Trie allows efficient prefix search by traversing nodes character by character.

B Hash Map uses less memory than Trie for storing prefixes.

C Hash Map can directly store all prefixes without extra processing.

D Trie requires hashing each prefix which is faster than direct lookup.

💡 Hint

Consider how prefix search works in both data structures.

Trie stores characters in a tree structure allowing prefix search by following nodes. Hash Map stores keys but does not support efficient prefix queries without extra processing.

❓ Predict Output

advanced

Output of Prefix Search Using Hash Map with All Prefixes

What is the output of the following Python code that uses a Hash Map to store all prefixes of words and then finds words with a given prefix?

DSA Python

words = ["dog", "deer", "deal"]
prefix_map = {}
for word in words:
    for i in range(1, len(word)+1):
        prefix = word[:i]
        if prefix not in prefix_map:
            prefix_map[prefix] = []
        prefix_map[prefix].append(word)

print(prefix_map.get("de", []))

A []

B ["dog", "deer", "deal"]

C ["deal"]

D ["deer", "deal"]

💡 Hint

Look at which words have the prefix 'de'.

The code stores all prefixes as keys and lists of words as values. The prefix 'de' matches 'deer' and 'deal'.

🔧 Debug

advanced

Identify the Error in Trie Prefix Search

What error will the following code produce when calling starts_with('ca')?

DSA Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.children.setdefault(char, TrieNode())
        node.end_of_word = True

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        return [prefix]

trie = Trie()
trie.insert("cat")
trie.insert("car")
print(trie.starts_with("ca"))

A AttributeError: 'NoneType' object has no attribute 'children'

B TypeError: 'TrieNode' object is not iterable

C KeyError: 'c'

D ['ca']

💡 Hint

Check the insert method and how node is updated inside the loop.

The insert method updates node incorrectly because setdefault returns the child node but the loop does not assign it properly, causing node to become None after first iteration.

🧠 Conceptual

expert

Memory Usage Comparison Between Trie and Hash Map for Prefix Matching

Which statement best describes the memory usage difference between a Trie and a Hash Map storing prefixes for prefix matching?

A Trie uses more memory because it stores all possible substrings, while Hash Map stores only prefixes.

B Trie uses less memory because it shares common prefixes in nodes, while Hash Map stores each prefix separately.

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

D Both use the same memory because they store the same number of keys.

💡 Hint

Think about how common prefixes are stored in Trie vs Hash Map.

Trie nodes share common prefixes, reducing memory by avoiding duplicate storage. Hash Map stores each prefix as a separate key, increasing memory usage.

Practice

1. Which data structure is generally more efficient for checking if a prefix exists in a large set of strings?

easy

A. Trie, because it stores prefixes explicitly for fast lookup

B. Hash Map, because it stores all strings as keys for quick access

C. Array, because it allows sequential search of prefixes

D. Linked List, because it maintains order of insertion

Solution

1. Step 1: Understand prefix matching requirement

   Prefix matching means checking if any string starts with a given prefix efficiently.

2. Step 2: Compare Trie and Hash Map for prefix search

   Trie stores prefixes explicitly in its nodes, allowing quick traversal to check prefixes. Hash Map stores full strings as keys, so prefix search requires checking multiple keys or extra processing.

3. Final Answer:

   Trie, because it stores prefixes explicitly for fast lookup -> Option A

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Trie stores prefixes explicitly, ideal for prefix search [OK]

Common Mistakes:

• Thinking hash map keys support prefix search directly
• Confusing prefix search with exact match
• Assuming arrays or linked lists are efficient for prefix search

2. Which of the following is the correct way to insert a word into a Trie node in Python?

easy

A. node[word] = True

B. node.add(word)

C. node[word[i]] = TrieNode()

D. node.children[word[i]] = TrieNode()

Solution

1. Step 1: Understand Trie node structure

   Each Trie node typically has a dictionary called children to store next characters as keys.

2. Step 2: Insert character at position i

   To insert a character, assign a new TrieNode to node.children[word[i]].

3. Final Answer:

   node.children[word[i]] = TrieNode() -> Option D

4. Quick Check:

   Insert char = node.children[word[i]] = TrieNode() [OK]

Hint: Insert chars by assigning new TrieNode to node.children[word[i]] [OK]

Common Mistakes:

• Using node[word] = True for whole word
• Using node[word[i]] = TrieNode() without .children
• Calling non-existent add() method

3. What will be the output of the following Python code snippet?

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.end = True
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

trie = Trie()
trie.insert('apple')
print(trie.starts_with('app'))
print(trie.starts_with('apl'))

medium

A. False\nFalse

B. True\nFalse

C. True\nTrue

D. False\nTrue

Solution

1. Step 1: Insert 'apple' into Trie

   Each character 'a', 'p', 'p', 'l', 'e' is added as nodes. The end flag is set at 'e'.

2. Step 2: Check starts_with for 'app' and 'apl'

   'app' exists as prefix nodes, so returns True. 'apl' fails at 'l' because 'l' is child of 'p' only after 'pp', so returns False.

3. Final Answer:

   True False -> Option B

4. Quick Check:

   Prefix 'app' found = True, 'apl' not found = False [OK]

Hint: Check prefix nodes exist step-by-step for True/False [OK]

Common Mistakes:

• Assuming 'apl' is prefix of 'apple'
• Confusing end flag with prefix existence
• Mixing up True/False order in output

4. The following code attempts to check if a prefix exists in a hash map of words. What is the main issue?

words = {'apple': 1, 'app': 2, 'banana': 3}
prefix = 'ap'
if prefix in words:
    print('Prefix found')
else:
    print('Prefix not found')

medium

A. The prefix variable is not defined

B. Syntax error in if condition

C. Hash map keys do not support prefix matching directly

D. The print statements are incorrect

Solution

1. Step 1: Understand hash map key lookup

   Checking 'prefix in words' looks for exact key match, not prefix match.

2. Step 2: Identify prefix matching limitation

   Hash maps do not support partial key matching; prefix must be checked by iterating keys or using a Trie.

3. Final Answer:

   Hash map keys do not support prefix matching directly -> Option C

4. Quick Check:

   Prefix search in hash map = no direct support [OK]

Hint: Hash maps need full key match; prefix needs iteration or Trie [OK]

Common Mistakes:

• Thinking 'prefix in dict' checks partial keys
• Assuming syntax error causes failure
• Ignoring need for iteration or Trie for prefix

5. You have a list of 1 million words and want to quickly find all words starting with a given prefix. Which approach is best and why? A) Store all words in a hash map and check each key for prefix match. B) Build a Trie from all words and traverse nodes for the prefix. C) Store words in a list and use list comprehension to filter prefixes. D) Use a linked list to store words and traverse to find prefix matches.

hard

A. Trie allows direct traversal to prefix node, fast for large data

B. Hash map with prefix check on all keys is efficient for large data

C. List comprehension is fastest for prefix search in large data

D. Linked list traversal is best for prefix matching in large data

Solution

1. Step 1: Analyze each data structure for prefix search

   Hash map requires checking all keys for prefix, which is slow for 1 million words. List and linked list require scanning all words, also slow.

2. Step 2: Understand Trie advantage

   Trie stores prefixes as nodes, so traversing to prefix node is fast and does not require scanning all words.

3. Final Answer:

   Trie allows direct traversal to prefix node, fast for large data -> Option A

4. Quick Check:

   Large prefix search = Trie traversal [OK]

Hint: Trie traversal beats scanning all keys for large prefix search [OK]

Common Mistakes:

• Choosing hash map or list for large prefix search
• Ignoring Trie prefix traversal speed
• Assuming linked list is efficient for prefix search