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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the trie.

DSA Python

def insert_word(root, word):
    node = root
    for char in word:
        if char not in node:
            node[char] = [1]
        node = node[char]
    node['#'] = True

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

Aset()

B[]

CNone

D{}

Attempts:

3 left

💡 Hint

Common Mistakes

Using a list or set instead of a dictionary for child nodes.

Assigning None which does not allow further insertions.

We use an empty dictionary {} to represent the next level nodes in the trie.

2fill in blank

medium

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

DSA Python

def starts_with(root, prefix):
    node = root
    for char in prefix:
        if char not in node:
            return False
        node = node[[1]]
    return True

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

Achar

Bprefix

Cnode

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole prefix instead of the current character.

Using the wrong variable like 'node' or 'root' as key.

We move to the child node corresponding to the current character 'char' in the prefix.

3fill in blank

hard

Fix the error in the code to count words with a given prefix using a hash map.

DSA Python

def count_prefix(words_map, prefix):
    count = 0
    for word in words_map:
        if word.[1](prefix):
            count += words_map[word]
    return count

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

Astartswith

Bendswith

C==

Din

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' which checks for exact match, not prefix.

Using 'in' which checks substring anywhere, not just prefix.

Use the string method 'startswith' to check if 'word' begins with 'prefix'.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps words to their lengths for words longer than 3 characters.

DSA Python

{word: [1] for word in words if len(word) [2] 3}

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

Alen(word)

B>

C<

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using the word itself as value instead of its length.

Using '<' instead of '>' causing wrong filtering.

We map each word to its length using len(word) and filter words longer than 3 using >.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase words to their counts for words with count > 1.

DSA Python

{ [1]: [2] for word, count in word_counts.items() if count [3] 1 }

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

Aword.upper()

Bcount

C>

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using word as key without uppercase conversion.

Using count <= 1 which filters out desired words.

Keys are uppercase words using word.upper(), values are counts, filtered by count > 1.

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