Prefix matching with tries in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

How does a trie store prefixes?

Which statement best describes how a trie stores prefixes of words?

A A trie stores prefixes by hashing each prefix into a table.

B Each node stores a whole word, and prefixes are stored as separate nodes.

C Prefixes are stored only at leaf nodes, not internal nodes.

D Each node represents a character, and paths from the root to nodes represent prefixes.

💡 Hint

Think about how characters connect in a trie to form words and prefixes.

In a trie, each node represents a character. The path from the root to any node forms a prefix of some word(s). This structure allows efficient prefix matching.

📋 Factual

intermediate

Trie node children count

What is the maximum number of children a single node in a trie can have when storing English lowercase words?

A 26

B 52

C 10

D 128

💡 Hint

Consider the English alphabet letters used in the words.

Each node can have up to 26 children, one for each lowercase English letter from 'a' to 'z'.

🚀 Application

advanced

Finding all words with a given prefix

Given a trie storing words, which step is necessary to find all words starting with a prefix "pre"?

A Traverse the trie following characters 'p', 'r', 'e' then collect all descendant words.

B Traverse the trie and collect words that end exactly at the node for 'p'.

C Search the trie for the word "pre" only and return it if found.

D Hash the prefix "pre" and look up in a hash table for matching words.

💡 Hint

Think about how to reach the prefix node and then find all words below it.

To find all words with a prefix, first follow the prefix characters in the trie to reach the node representing the prefix. Then collect all words in the subtree rooted at that node.

🔍 Analysis

advanced

Time complexity of prefix search in a trie

What is the time complexity to check if a prefix of length k exists in a trie storing n words?

A O(log n), because tries use binary search internally.

B O(n), because you must check all words in the trie.

C O(k), because you traverse one node per character in the prefix.

D O(k * n), because each character requires scanning all words.

💡 Hint

Consider how many nodes you visit when searching for a prefix.

Checking a prefix requires traversing nodes equal to the prefix length k. This is independent of the total number of words n.

❓ Reasoning

expert

Memory trade-offs in trie implementations

Which statement best explains a common memory trade-off when implementing tries for prefix matching?

A Tries always use less memory than hash tables regardless of implementation.

B Using arrays for children pointers uses more memory but allows faster access than linked lists.

C Storing full words at each node reduces memory usage compared to storing characters.

D Using linked lists for children pointers uses less memory and is always faster than arrays.

💡 Hint

Think about how children nodes are stored and accessed in tries.

Arrays allocate fixed space for all possible children, using more memory but enabling quick direct access. Linked lists save memory by storing only existing children but require slower traversal.

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