Coding interviews
Reveal answer and reasoning
A trie represents shared prefixes with paths, but a path is not automatically a complete stored word. A terminal flag distinguishes car from its prefix ca. This implementation uses exact UTF-16 code units, permits an empty prefix and treats repeated insertion as idempotent. Inserting the empty word would mark the root terminal; no case folding, normalization or grapheme matching is implied.
Word membership and prefix membership are separate operations with separate expected answers. The root represents the empty prefix even in a trie that contains no words. A terminal bit records word completion independently of whether a node has children, so a word can also be the prefix of a longer word.
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. The alphabet and representation drive constants and space. A Dictionary per node supports sparse branching but adds object and hashing overhead.
A twenty-six-slot array would need an explicitly limited alphabet; using it for arbitrary UTF-16 input without validation would be both wasteful and incorrect.
What a strong answer covers
- A trie represents shared prefixes with paths, but a path is not automatically a complete stored word.
- After car and cart are inserted, the r node is terminal and has a t child.
- For m code units, insertion and lookup take expected O(m) dictionary work, with O(total distinct prefix nodes) retained space.
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.