How to run the autocomplete design in a 45-minute interview: the precomputed top-K trie, offline index builds, edge caching, and the follow-ups to expect.
Published September 21, 2026
This lesson is the interview version: the order to present the design, the numbers to state, and the trade-offs to defend. The full reference design is the case study Design a Search Autocomplete System in this chapter.
Autocomplete (typeahead) shows the most likely completions while a user types: "how to" → "how to tie a tie", "how to screenshot on mac". The defining constraint is latency: suggestions must appear in well under 100 ms, on every keystroke, for millions of users. That single constraint drives almost every decision.
The key realization to say aloud: this is overwhelmingly read-heavy, and suggestions don't need to be real-time exact. That lets you precompute almost everything.
There are two separate paths, and separating them is the core idea:
QUERY PATH (fast, read-only) DATA PATH (offline, batch)
user types "app" search logs
│ │
▼ ▼
CDN / edge cache ── hit ──▶ suggestions stream/batch aggregation
│ miss (count queries per time window)
▼ │
Autocomplete service ▼
(in-memory prefix index, top-K per prefix) ◀── index builder: build trie with
top-K precomputed per prefix,
publish a new version every N minutes
A trie (prefix tree) stores strings character by character, so all queries starting with "app" live under one node. Finding that node takes O(length of prefix) steps.
The naive approach finds the node and then walks its entire subtree to rank completions, which is far too slow for popular short prefixes like "a". The standard fix is to store the top-K completions directly on every node during the offline build. A lookup then becomes: walk ~3–10 nodes, return a stored list. That's constant-ish time at query time, paid for with extra memory and a slower build.
Memory estimate: with ~100 million distinct popular queries, the trie plus top-K lists fits in tens of GB. That's feasible on large-memory servers, or you can shard by prefix range (a–f, g–m, …) with a thin router in front. Sharding by first letter is uneven ("s" is far busier than "x"), so shard by measured traffic.
Updating the trie on every search would mean constant writes to a structure being read at hundreds of thousands of requests per second. Instead:
Base ranking is popularity, weighted toward recent activity (for example exponential decay). Personalization (your own recent searches, your location, your language) is blended in at query time from a small per-user store. Keep it lightweight so latency doesn't suffer.
LIKE 'app%' on every keystroke. Even with an index it won't hit the latency target at this scale, and ranking needs aggregation.Q: How big can the top-K lists make the trie? A: Each node stores K references (for example 10 query IDs, not full strings), so memory grows with nodes × K. You bound it by only including queries above a popularity threshold, storing IDs into a shared string table, and pruning deep, rare branches. If it still doesn't fit on one machine, shard by prefix range.
Q: How do you remove an offensive suggestion immediately? A: Apply a blocklist filter at query time in the service (and at the edge cache by purging affected prefixes), so removal doesn't wait for the next index build. The next build then drops it from the data too.
Q: Why not use Elasticsearch's completion suggester? A: For moderate scale it's a perfectly good choice and much less custom code. At very large scale and very strict latency, a purpose-built in-memory index gives more control over memory layout, ranking and update strategy. In an interview, mention it as the pragmatic option, then explain what the custom design buys.
Q: How would you handle typos? A: Add a fuzzy-matching step for prefixes that return few results: an edit-distance search over a limited neighbourhood, or a separate "did you mean" index built from common misspellings in the logs. Keep it off the fast path for normal prefixes.