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.