Micro-questions over the tries module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The object
1. What is a trie?
Answer
A tree where the path you walk spells out a word, rather than any single node holding one. Also called a prefix tree.
2. Where does the name come from, and how is it pronounced?
Answer
From “retrieval”, and usually pronounced “try”.
3. What does the root node represent?
Answer
The empty string. Every word’s path begins there.
4. What is a character edge?
Answer
A link from one node to the next, labelled with a single character. Walking a then p puts you at the node for the prefix "ap".
5. State the trie’s defining feature.
Answer
Every prefix is an actual place in the structure — which is exactly why prefix questions are cheap.
6. Draw the trie for app, apple, apt, cat.
Answer
( Root )
/ \
'a' 'c'
/ \
'p' 'a'
/ \ \
'p'* 't'* 't'*
/
'l'
/
'e'* (* = is_end)
B. is_end
7. What is the is_end flag?
Answer
A true/false marker saying “a complete word ends here”.
8. Why is it necessary?
Answer
Because a node can be passed through on the way to a longer word without being a word itself. The flag separates "app", which is a word, from "appl", which is only a stop on the way to "apple".
9. What breaks if you forget it?
Answer
The trie cannot distinguish an actual word from a prefix of a longer one — search("appl") returns true.
C. Alphabet size and memory
10. What is , and what are typical values?
Answer
The alphabet size — how many characters can follow any node. 26 for lowercase English, 128 for ASCII, over a million for full Unicode.
11. Why does matter so much?
Answer
It decides how much memory a trie costs, which is its main drawback. Every node may hold up to child pointers, and most sit empty.
12. What should children be in practice, and why?
Answer
A dictionary, not a fixed array of size 26. A fixed array over Unicode or multilingual input wastes enormous memory on empty slots.
D. The ADT
13. What does mean in every trie cost, and why is that unusual?
Answer
The length of the word being handled — not the number of words stored. Searching a trie of ten words and a trie of ten million costs the same for a five-letter word.
14. List the trie ADT with costs.
Answer
insert(word) ; search(word) ; starts_with(prefix) ; delete(word) ; words_with_prefix(prefix) plus the time to collect what hangs below.
15. Which operation is the reason tries exist?
Answer
starts_with(prefix) — the operation a hash set cannot do at all.
16. Why can a hash set not do it?
Answer
Hashing destroys the relationship between "app" and "apple". A hash set would have to check every stored word.
17. What is words_with_prefix in product terms?
Answer
Autocomplete.
18. How does search differ from starts_with in code?
Answer
Both walk the same path. search additionally requires node.is_end; starts_with only requires that the node exists.
E. The trade
19. What does a trie gain over a hash set?
Answer
Prefix search; ordered iteration (walking children alphabetically yields sorted words); and a lookup cost that does not grow with the number of stored words.
20. What does it cost?
Answer
Far more memory — in the worst case. A trie over full Unicode is impractical without a compressed variant.
21. Where does a trie actually lose?
Answer
Plain exact-match lookup in practice. A hash set is against the trie’s , with much better cache behaviour — trie nodes are scattered like linked list nodes.
22. Give the decision rule.
Answer
Use a trie when the question is about prefixes. If you only ever ask “is this exact word present?”, use a hash set.
23. Compare sorted traversal cost in each.
Answer
Hash set: — you must sort. Trie: for free, by pre-order traversal visiting children alphabetically.
F. Wildcard search
24. What happens to the lookup when the query contains .?
Answer
The single-path lookup becomes a depth-first search over all child branches.
25. Write the recursive rule.
Answer
At index : if the char is ., recurse into every child; otherwise recurse into that one child if it exists. At len(word), return node.is_end.
26. What is the cost of a wildcard search?
Answer
Up to where is the number of wildcards — each . multiplies the branching. A query of all dots scans the whole trie.
G. Deletion and traps
27. Why is deletion the fiddliest operation?
Answer
Clearing is_end is easy; pruning is not. You may only remove a node if it has no other children and is not the end of another word — so you prune recursively back up the path.
28. What is the memory-overuse trap?
Answer
Fixed arrays of size 26 (or 128, or Unicode-sized) at every node. Use a dynamic dictionary instead.
29. Summarise the trie in one sentence.
Answer
Store words as paths so that every prefix becomes an address — costs regardless of how many words there are, buys prefix queries and sorted order, and pays in memory.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Tries / Prefix Trees — the module
- Hash Maps — Question Bank — the structure this one is measured against
- Trees — Question Bank — the shape underneath
Software engineering
Infrastructure & security
Computer science
Hardware & engineering