mediumDesignCodingMidSeniorStaff
Design the data structure behind a search box's autocomplete. Why a trie, and when would you not use one?
6 min readUpdated 2026-08-15
Answer
Short answer
A trie stores one node per character, so finding a prefix is a walk of length k and its completions are the subtree below it.It costs far more memory than the strings themselves, so a hash map still wins for exact lookup and a sorted array with binary search wins for a static dictionary.
Mention prefix search where it changes the risk, the owner, or the next check. A useful prefix search point should make the answer more testable, not merely longer. Tie prefix search back to the scenario so the interviewer can see why it matters here.
Was this answer helpful?
Likely follow-ups
- How would you return the ten most popular completions rather than ten arbitrary ones?
- What does a radix tree change about the node count, and what does it complicate?
- How would you support a typo in the prefix without abandoning the structure?
- Where would this live if the dictionary is fifty million terms and no single machine holds it?
Related questions
- Count the subarrays whose elements sum to k, where the values may be negative.mediumAlso on space-time-tradeoff4 min
- Find the length of the longest substring without repeating characters.mediumAlso on strings2 min
- Build an in-memory key-value store with per-key TTL, plus a snapshot operation that gives a consistent copy while writes keep coming in.hardSame kind of round: coding6 min
- One global lock makes your reservation system correct and slow. How do you split it without deadlocking?hardSame kind of round: design5 min