If you were building the autocomplete for a search box, how would you use a trie to return suggestions for what the user has typed so far?

technical-conceptual · Junior level · software-engineering

What the interviewer is really asking

Assesses whether the candidate can apply a trie to the autocomplete problem — navigate to the prefix node, traverse the subtree to collect completions, and reason about ranking and scale.

What to say

• Describe the two phases: walk the trie character by character down to the node for the typed prefix (O(L)), and if that path exists, traverse the subtree below it to collect every word that completes the prefix.
• Handle ranking and the result limit: you usually don't want all completions but the top few, so either do a bounded traversal or store a popularity/frequency score so you can return the most relevant suggestions rather than arbitrary ones — often by caching the top-k completions at each node.
• Reason about scale and edge cases: if the prefix node doesn't exist, return no suggestions; the subtree traversal can be expensive for a short prefix with many completions, so precomputing top-k per node or capping the traversal keeps the response fast enough for keystroke latency.

What to avoid

• Describe finding the prefix node but forget the second phase of traversing the subtree to actually collect the completions.
• Ignore ranking and just return matches in arbitrary trie order, which gives irrelevant suggestions for a real search box.
• Hand-wave the latency: a short, popular prefix can have an enormous subtree, so returning all of it per keystroke without a top-k cap or precomputation would be too slow.

Example answers

Strong: Two steps. First I walk the trie from the root following each character the user has typed; that lands me at the node representing the prefix in O(L), or tells me no word has that prefix so I return nothing. Second, I traverse the subtree under that node — a DFS collecting every marked word-end below it — and those are the completions. For a real search box I wouldn't return all of them: I'd store a frequency or popularity score at each word and return the top few, so 'app' suggests the most-searched terms, not a random subtree order.

Weak: I'd store all the words in a trie and then search for the prefix the user typed; if it's in the trie I show it. I think that gives the suggestions.