Design Typeahead for Search Box
In this mock interview video, Andreas (Modern Health SWE), answers the interview question, "Design a typeahead box for a search engine."
You're asked to design typeahead search: the list of suggestions that appears beneath a search box as the user types. It should return a handful of relevant suggestions per keystroke, ranked by popularity, in well under 100 milliseconds, drawn from a corpus of search terms that changes constantly.
Every keystroke is a request, so one search session produces ten or twenty of them. That volume combined with the latency budget rules out querying a database at read time, so the suggestions have to be computed ahead of time and served from memory.
Clarifying the requirements
- What are we suggesting? Search queries other people have typed, product names, or usernames? A query-log corpus is fed by user behavior and changes constantly; a product catalog is curated and changes rarely.
- How are suggestions ranked? Raw popularity is the baseline. Personalization and recency are common follow-ups, and they change the architecture significantly.
- How fresh must new terms be? A breaking-news term appearing within minutes is a much harder requirement than a nightly rebuild.
- Personalized or global? Global suggestions can be cached once and served to everyone. Personalized ones can't, which is the single biggest fork in this design.
Assume: query suggestions ranked by popularity, global rather than personalized, with new terms appearing within minutes.
Back-of-envelope numbers
- Requests: , with peaks well above
- Latency budget: under 100 ms end to end, so essentially all of it is network
- Corpus: , which fits in memory
This is the number that shapes the design. If the entire suggestion structure fits in memory on one machine, you can replicate it widely instead of sharding it, and every read becomes a local memory lookup.
High-level architecture
- Edge cache. Popular prefixes like "a" or "we" are requested constantly and identically by everyone, so they never need to reach your servers.
- Suggestion service. Stateless request handling over an in-memory structure. Each instance holds a full copy.
- Query logs. Every search a user actually submits, streamed to storage.
- Aggregation job. Counts query frequency over a rolling window.
- Trie builder. Turns those counts into the serving structure and publishes it as a versioned snapshot.
Deep dive 1: the data structure
A trie (prefix tree) is the canonical answer, and knowing why is most of the signal. Each node is a character, each path from the root is a prefix, and the subtree below a node contains every completion of it.
A plain trie still forces you to walk an entire subtree to find the top suggestions, which is too slow for a hot prefix with millions of descendants. The fix is to precompute the top-k at every node: each node stores its five best completions with their scores, so a lookup is "walk down at most len(prefix) nodes, return the list you find." That's O(length of prefix) with a tiny constant, independent of corpus size.
The cost is memory and build time. Storing five suggestions at every node inflates the structure substantially, which is a trade worth naming out loud. If the interviewer pushes on memory, compress the trie by collapsing single-child chains into one node.
Deep dive 2: keeping it fresh
The corpus changes constantly, but you cannot mutate a trie in place while thousands of requests per second are reading it, and you don't want to.
The standard answer is build offline, swap atomically. An aggregation job counts query frequencies over a rolling window, a builder constructs a fresh trie from those counts, and the result is published as an immutable, versioned snapshot. Serving instances download the new snapshot, build it in memory alongside the current one, and flip a pointer. No locking, no partial states, and an instant rollback if the new snapshot is bad.
How often you rebuild is a cost-versus-freshness dial, exactly like the freshness budgets in the read-heavy pattern. Hourly is cheap and usually fine. If minutes matter, keep a small in-memory delta of very recent terms that the service merges into results at query time, and fold it into the next full build.
Deep dive 3: scaling the read path
Three layers, in order of how much traffic they absorb:
- The client. Debounce keystrokes by 50 milliseconds or so, and don't fire a request for a prefix whose results are a subset of one you already have. This alone removes a large fraction of requests, and mentioning it shows you're thinking about the whole system rather than just the server.
- The edge. Short prefixes are requested identically by everyone and change slowly, so they cache extremely well with a short TTL. Long prefixes are rare and cache poorly, and that's fine, because there aren't many of them.
- Replication over sharding. Since the structure fits in memory, every instance can hold the whole trie, which means any instance can serve any request and scaling is pure replication. Only shard by prefix range if the corpus genuinely outgrows one machine, and say why you're not sharding by default.
Deep dive 4: ranking, personalization, and abuse
Ranking starts with frequency but rarely stays there. Recency weighting keeps a term that spiked this morning above one popular last year. Adding a time-decayed score to each node is a small change to the aggregation job and a large change to result quality.
Personalization breaks the cacheable-global-structure assumption, so the usual approach is a hybrid: serve global suggestions from the shared trie, then blend in a small per-user list of that user's recent searches at request time. The expensive shared structure stays shared.
Abuse is a real concern in this design, because the corpus is user-generated. A coordinated group can push an offensive term into suggestions by searching it repeatedly. Filter against a blocklist at build time, require a minimum number of distinct users before a term is eligible, and keep a manual removal path.
Common pitfalls
- Querying a database per keystroke. Even an indexed prefix query is too slow at this rate, and it puts your busiest path on your least scalable component.
- Walking the subtree at query time. Correct but too slow for hot prefixes; precompute the top-k at each node.
- Mutating the trie in place. Concurrent reads and writes on a shared structure invites locking or inconsistent results. Build offline and swap.
- Sharding before checking whether it fits in memory. The corpus size is the first number to compute.
- Forgetting client-side debouncing. The cheapest request is the one never sent.
Leveling the answer
Related lessons
Map long URLs to short codes and redirect users, at very high read volume.
Build a photo feed that assembles each user's timeline from the accounts they follow.