Prefix matching with tries in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into a trie node.

Data Structures Theory

node.children[[1]] = TrieNode()

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

Achar

Bindex

Cword

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole word instead of a single character as the key.

Using an index number instead of the character.

The variable char represents the current character in the word being inserted into the trie. We use it as the key to add a new child node.

2fill in blank

medium

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

Data Structures Theory

if [1] not in node.children:
    return False

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

Aprefix

Bword

Cchar

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for the whole prefix string instead of one character.

Using the node variable instead of the character.

We check if the current character char of the prefix exists among the children of the current node.

3fill in blank

hard

Fix the error in the code to move to the next node during prefix search.

Data Structures Theory

node = node.children[[1]]

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

Achar

Bprefix

Cword

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using the entire prefix string as a key.

Using an index number instead of the character.

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

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each word to its length if the word starts with 'pre'.

Data Structures Theory

{word: [1] for word in words if word.[2]('pre')}

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

Alen(word)

Bstartswith

C==

Din

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' instead of 'startswith' to check prefix.

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

The dictionary comprehension maps each word to its length using len(word). The condition uses word.startswith('pre') to filter words starting with 'pre'.

5fill in blank

hard

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

Data Structures Theory

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

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

Aword.upper()

Blen(word)

Cword

Dword.lower()

Attempts:

3 left

💡 Hint

Common Mistakes

Using word.lower() instead of uppercase.

Using the wrong variable name in the comprehension.

The comprehension maps the uppercase version of each word to its length using len(word). The variable word iterates over the list words. The condition filters words longer than 3 characters.

Practice

1. What is the main advantage of using a trie for prefix matching?

easy

A. It stores words in reverse order

B. It uses less memory than arrays

C. It sorts words alphabetically automatically

D. It allows fast lookup of words sharing common prefixes

Solution

1. Step 1: Understand trie structure

   A trie stores words by sharing nodes for common prefixes, reducing repeated storage.

2. Step 2: Identify prefix matching benefit

   This structure allows quick traversal to find all words starting with a given prefix.

3. Final Answer:

   It allows fast lookup of words sharing common prefixes -> Option D

4. Quick Check:

   Prefix matching speed = Fast lookup [OK]

Hint: Tries speed up prefix search by sharing nodes [OK]

Common Mistakes:

• Confusing tries with hash tables
• Thinking tries sort words automatically
• Assuming tries store words backwards

2. Which of the following is the correct way to check if a prefix exists in a trie?

easy

A. Search the entire trie for the full word

B. Traverse nodes matching each prefix character until end or mismatch

C. Count all leaf nodes in the trie

D. Sort all words and do binary search

Solution

1. Step 1: Understand prefix search in tries

   To check a prefix, we walk down the trie nodes matching each character in order.

2. Step 2: Identify correct method

   If traversal completes without mismatch, prefix exists; otherwise, it does not.

3. Final Answer:

   Traverse nodes matching each prefix character until end or mismatch -> Option B

4. Quick Check:

   Prefix check = Node traversal [OK]

Hint: Walk trie nodes character by character for prefix [OK]

Common Mistakes:

• Searching entire trie instead of prefix path
• Counting leaf nodes unrelated to prefix
• Using sorting instead of trie traversal

3. Given a trie containing words: ['cat', 'car', 'cart', 'dog'], which words match the prefix 'car'?

medium

A. ['car', 'cart']

B. ['dog']

C. ['cat', 'car']

D. ['cat', 'dog']

Solution

1. Step 1: Identify words starting with 'car'

   From the list, 'car' and 'cart' start with the prefix 'car'.

2. Step 2: Exclude words not matching prefix

   'cat' starts with 'cat', not 'car'; 'dog' does not match prefix.

3. Final Answer:

   ['car', 'cart'] -> Option A

4. Quick Check:

   Words with prefix 'car' = ['car', 'cart'] [OK]

Hint: Match prefix exactly to filter words [OK]

Common Mistakes:

• Including words with similar but different prefixes
• Confusing 'cat' with 'car'
• Selecting unrelated words

4. A trie implementation returns false when checking prefix 'app' even though words ['apple', 'application'] exist. What is the most likely error?

medium

A. The trie nodes for 'app' were not linked correctly

B. The words were inserted backwards

C. The prefix check is case-insensitive

D. The trie only stores full words, not prefixes

Solution

1. Step 1: Analyze prefix check failure

   If words with prefix 'app' exist but check fails, likely the path for 'app' nodes is broken.

2. Step 2: Exclude other causes

   Words inserted backwards or case issues would cause different errors; tries store prefixes inherently.

3. Final Answer:

   The trie nodes for 'app' were not linked correctly -> Option A

4. Quick Check:

   Broken node links = prefix check fail [OK]

Hint: Check node links for prefix path [OK]

Common Mistakes:

• Assuming tries don't store prefixes
• Ignoring node linkage errors
• Confusing case sensitivity issues

5. You want to build an autocomplete feature using a trie. Which approach best improves performance when many words share prefixes?

hard

A. Use a linked list instead of trie nodes for each character

B. Store full words only at leaf nodes without intermediate nodes

C. Store a count of words passing through each node to quickly find popular prefixes

D. Sort all words and do linear search for each prefix

Solution

1. Step 1: Understand autocomplete with tries

   Autocomplete benefits from knowing how many words share a prefix to prioritize suggestions.

2. Step 2: Identify performance improvement

   Storing counts at each node helps quickly find popular prefixes without full traversal.

3. Final Answer:

   Store a count of words passing through each node to quickly find popular prefixes -> Option C

4. Quick Check:

   Node counts = faster autocomplete [OK]

Hint: Count words at nodes to speed autocomplete [OK]

Common Mistakes:

• Storing words only at leaves slows prefix search
• Using linked lists reduces trie efficiency
• Linear search ignores trie benefits