Coding interviews
Reveal answer and reasoning
A bounded suggestion API should first choose lexical or popularity order and define how ties are resolved. For lexical order, traversal must visit children in a specified order rather than relying on dictionary enumeration. A result cap bounds returned suggestions but not necessarily the number of visited nodes unless the traversal policy supports early stopping.
For m code units, insertion and lookup take expected O(m) dictionary work, with O(total distinct prefix nodes) retained space. A node can allocate a child dictionary even before many children exist. A fixed alphabet array trades lookup characteristics for potentially much larger sparse storage. Assuming every reached node is a word makes prefix queries accidentally satisfy exact-word checks. Treating char as a user-perceived character changes Unicode semantics.
Suggestions also require a separate ordering and result-limit contract; this trie intentionally exposes only existence checks, not a ranked autocomplete system.
The core proof is path correspondence: following each code unit reaches exactly the node for that prefix, and the terminal flag determines whether the complete word was inserted. The sample exercises a shared prefix, a branching prefix and an idempotent insertion. An effective interview explanation separates that membership problem from autocomplete ranking, normalization and deletion. It also accounts for retained node and dictionary allocations, rather than describing a trie only by the length of one query.
This makes the proposed extension measurable instead of quietly changing the meaning of a character or a result order.
What a strong answer covers
- A bounded suggestion API should first choose lexical or popularity order and define how ties are resolved.
- For m code units, insertion and lookup take expected O(m) dictionary work, with O(total distinct prefix nodes) retained space.
- Assuming every reached node is a word makes prefix queries accidentally satisfy exact-word checks.
Common pitfall
Assuming every reached node is a word makes prefix queries accidentally satisfy exact-word checks. Treating char as a user-perceived character changes Unicode semantics. Suggestions also require a separate ordering and result-limit contract; this trie intentionally exposes only existence checks, not a ranked autocomplete system.
Follow-up questions
- Insert the empty word and verify that Contains empty changes while Prefix empty remains true. Hint: there is no character edge to create, so the operation modifies the root. Add a mixed-case word to verify exact matching.
- When deleting car, which nodes must remain to preserve cart and cat?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.