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

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.children:
            node.children[[1]] = TrieNode()
        node = node.children[char]
    node.is_end = True

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

Aword

Bchar

Cnode

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole word as key instead of single character.

Using the node or root as key.

We use the current character char as the key to check and add in the children dictionary.

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 [1] not in node.children:
            return False
        node = node.children[char]
    return True

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

Aprefix

Bnode

Cchar

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for the whole prefix instead of single character.

Using node or root as key.

We check if the current character char is in the children dictionary.

3fill in blank

hard

Fix the error in the code to search a word in the Trie.

DSA Python

def search_word(root, word):
    node = root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[[1]]
    return node.is_end

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

Achar

Bword

Cnode

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole word or node as key instead of character.

We must use the current character char to move to the next node in children.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps words to their lengths only if length is greater than 3.

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 length.

Using wrong comparison operator.

The dictionary maps each word to its length, and filters words with length greater than 3.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase words to their lengths only if length is greater than 2.

DSA Python

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

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

Aword.upper()

Blen(word)

C>

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using original word as key instead of uppercase.

Using wrong comparison operator.

The dictionary keys are uppercase words, values are their lengths, filtered by length greater than 2.

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 uses less memory than Hash Map always

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

C. Because Hash Map cannot store strings as keys

D. Because Trie is faster for all types of lookups

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 search directly.

2. Step 2: Compare prefix search ability

   Hash Map can check full keys but cannot find all keys with a given prefix efficiently. Trie can find all keys sharing a prefix quickly.

3. Final Answer:

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

4. Quick Check:

   Prefix search = Trie advantage [OK]

Hint: Trie is for prefix search; Hash Map is not [OK]

Common Mistakes:

• Thinking Hash Map can do prefix search efficiently
• Assuming Trie always uses less memory
• Believing Hash Map cannot store string keys

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

easy

A. node = set()

B. node = []

C. node = {'children': {}, 'is_end': False}

D. node = ''

Solution

1. Step 1: Identify Trie node structure

   A Trie node typically has a dictionary for children and a boolean to mark end of word.

2. Step 2: Match with options

   node = {'children': {}, 'is_end': False} correctly uses a dictionary for children and a boolean flag. Others do not represent Trie node structure.

3. Final Answer:

   node = {'children': {}, 'is_end': False} -> Option C

4. Quick Check:

   Trie node = dict + bool [OK]

Hint: Trie node needs children dict and end flag [OK]

Common Mistakes:

• Using list or set instead of dictionary for children
• Not including end-of-word marker
• Using empty string as node

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

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = 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.is_end = True
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

trie = Trie()
trie.insert('cat')
trie.insert('car')
print(trie.search('cat'))
print(trie.search('ca'))
print(trie.search('car'))

medium

A. True\nFalse\nTrue

B. True\nTrue\nTrue

C. False\nFalse\nFalse

D. True\nFalse\nFalse

Solution

1. Step 1: Insert words 'cat' and 'car'

   Both words are inserted character by character, marking end of word at last character.

2. Step 2: Search for 'cat', 'ca', and 'car'

   'cat' and 'car' exist fully with end marked True, so search returns True. 'ca' is prefix but not end of word, so returns False.

3. Final Answer:

   True\nFalse\nTrue -> Option A

4. Quick Check:

   Search full word only returns true [OK]

Hint: Search returns true only if full word inserted [OK]

Common Mistakes:

• Assuming prefix search returns true
• Confusing is_end flag usage
• Not updating node during insert

4. The following code tries to insert words into a Trie but has a bug. What is the bug?

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

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for char in word:
            if char in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

medium

A. It does not initialize the root node

B. It never marks the end of word

C. It uses list instead of dictionary for children

D. It overwrites existing child nodes instead of checking if they exist

Solution

1. Step 1: Analyze insert method condition

   The code checks if char is in children, then overwrites with new TrieNode, which erases existing nodes.

2. Step 2: Identify correct logic

   It should add new TrieNode only if char NOT in children, to avoid overwriting existing nodes.

3. Final Answer:

   It overwrites existing child nodes instead of checking if they exist -> Option D

4. Quick Check:

   Insert overwrites nodes = bug [OK]

Hint: Add node only if child missing, not if present [OK]

Common Mistakes:

• Confusing if condition logic
• Forgetting to mark end of word
• Not initializing root node

5. You want to find all words in a dictionary that start with the prefix 'pre'. 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 a tree allowing prefix traversal; implement by walking nodes for prefix then collecting all descendants

B. Hash Map stores keys with prefix indexing; implement by filtering keys starting with prefix

C. Trie hashes prefixes for quick lookup; implement by hashing prefix and returning matches

D. Hash Map stores words sorted; implement by binary search on keys

Solution

1. Step 1: Understand prefix search in Trie vs Hash Map

   Trie organizes words by characters in a tree, enabling direct traversal to prefix node. Hash Map keys are unordered, so prefix search requires scanning all keys.

2. Step 2: Describe prefix search implementation in Trie

   Traverse Trie nodes for each prefix character, then recursively collect all words from that node's descendants.

3. Final Answer:

   Trie stores words in a tree allowing prefix traversal; implement by walking nodes for prefix then collecting all descendants -> Option A

4. Quick Check:

   Prefix search = Trie traversal + collect descendants [OK]

Hint: Trie prefix search = walk prefix + gather words [OK]

Common Mistakes:

• Thinking Hash Map can do prefix search efficiently
• Confusing hashing with prefix traversal
• Assuming keys in Hash Map are sorted