The whole thing is decided before the request ever reaches your server. Someone types “new y” and expects a list with “new york times” and “new york weather” already sitting there in maybe 60 to 100 milliseconds, less time than the gap between two of their keystrokes. That budget rules out running an actual search. Whatever you show has to be looked up, not computed, which is why autocomplete is a precomputed-prefix problem wearing a search costume.
Interviewers open this one loosely on purpose. “Design the suggestions under Google’s search bar,” or “build typeahead for our product catalog.” The first move worth making is pinning down what the suggestions are. Are you completing past search queries the way Google and YouTube do, product names in a catalog like Amazon, or usernames in a mention box? Query completion draws from a ranked corpus of billions of historical searches. A product catalog is a few million entities that change slowly. A mention box is scoped to one person’s connections. Those have very different index sizes and update rhythms, and naming one early keeps the rest of the conversation concrete instead of hand-wavy.
Assume the query-completion version at roughly Google scale for the rest of this. Round numbers: a few billion searches a day, call it 60,000 per second at peak. Each search fires about one autocomplete request per character typed, so a 20-character query means 15 to 20 lookups. That pushes read traffic past a million requests per second, nearly all reads, nearly all answerable from memory. The write side, recording which queries people ran so you can suggest them later, is tiny by comparison and can lag by minutes or hours without a single user noticing.
Autocomplete is a lookup table you build offline
For the prefix “new y” the answer is a short ordered list: the top five or ten completions ranked by how likely someone is to want each one. There is no reason to compute that ranking at query time. Rank once, store the top-K list keyed by prefix, and the request collapses into a single map lookup. Every strong answer converges on this: precompute the top-K for every prefix, hold it in memory, and pay for a cache hit instead of a calculation.
The classic structure for holding it is a trie. Each node is one character, the path from the root spells a prefix, and at every node you stash that prefix’s precomputed top-K suggestions. Walking “n” to “e” to “w” to space to “y” is five pointer hops, O(k) in the length of what was typed and independent of how many queries exist in total. Elasticsearch’s completion suggester does the same job with a different structure, a finite state transducer, and shifts the heavy work to index time so query latency stays flat and small.
Which index, and the real tradeoffs
The choice of index is where an interviewer finds out whether you have shipped one of these or only read about it. Four options come up, and the interesting answer usually mixes two of them.
| Autocomplete index approach | How it serves a prefix | Typical per-lookup latency | Fits best when | Where it hurts |
|---|---|---|---|---|
| In-memory trie, top-K stored per node | Walk the characters, read the precomputed list at the node | Around 1 ms, no network hop | A bounded, memory-resident set of popular prefixes | Rebuild and update are awkward; memory grows with the vocabulary |
| Elasticsearch completion suggester (FST) | Suggestions compiled into a finite state transducer at index time | Roughly 10 to 30 ms including network | Millions of documents refreshed by periodic reindex | Weak at real-time trending and per-user ranking |
| Inverted index with edge n-grams | Prefixes indexed as tokens, results ranked at read time | Roughly 20 to 50 ms | Full-text plus fuzzy and long-tail coverage | Ranking cost paid on every request |
| Database column with LIKE ‘foo%’ | B-tree range scan on an indexed text column | Tens of ms at low scale, degrades fast | A catalog of a few thousand rows, an internal tool | No built-in ranking; collapses under real load |
| Hybrid: trie for the head, search backend for the tail | Trie answers popular prefixes, backend handles the rest | About 1 ms hot, about 30 ms cold | A large corpus with a heavy popularity head | Two systems to keep in sync |
The hybrid row is where most real systems land. A trie holding the top ten million or so queries covers something like 90 percent of traffic at memory speed, and the long tail falls through to a search backend that can afford a slower path because it is hit far less often. You get the fast common case without pretending the tail does not exist.
Ranking is the actual product
Prefix matching is the easy fifth of the problem. The reason Google’s suggestions feel like they read your mind is the ranking sitting behind each prefix, and this is where interviewers push, because it separates people who memorized a trie diagram from people who have thought about what the feature is for. Search volume is the dominant signal, since a query more people have run is a safer guess. Layered on top is a freshness component that can surface a query trending in the last few hours before it has piled up the historical count to earn a spot on volume alone, which is how a breaking news term shows up the same afternoon it breaks.
Personalization and location come next. The prefix “gi” from a developer might resolve to “github”; the same two letters in a recipe app resolve to “ginger”. You usually cannot bake per-user ranking into one shared trie, so the common split is a global top-K from the precomputed index blended at query time with a small per-user or per-context list. Keep the global lookup fast, do a cheap merge on the way out, and accept that the personalized slice is best-effort.
The follow-ups are where the round is won or lost. Expect some version of these:
- “How does a query that started trending an hour ago get into the suggestions?”
- “One prefix suddenly gets a hundred times the traffic of its neighbors. What happens to your trie?”
- “The user types faster than your round trip. What are you actually sending on each keystroke?”
- “How do you keep offensive or personal queries out of what you suggest?”
Getting new and trending queries in
The write path runs on its own clock. Every executed search lands in a log. A streaming job, usually Kafka feeding a Flink or Spark aggregation, rolls those into counts per query over sliding windows: all-time, last week, last hour. A periodic job rebuilds the trie or reindexes the completion suggester from the fresh counts and swaps it in behind the read path. The trending slice might refresh every few minutes while the bulk of the structure rebuilds hourly or daily. Because a suggestion is a hint and not a source of truth, that lag costs nothing, and treating the read index as immutable and rebuilding it rather than mutating in place sidesteps a whole category of concurrency bugs.
Two filters belong in that build step. You do not want to suggest queries that ran only a handful of times, partly because they are noise and partly because a rare query can carry someone’s private information, so a frequency floor drops the thin long tail out of what gets surfaced. And a blocklist for slurs and illegal content gets applied at build time, so nothing offensive ever reaches a node in the first place rather than being filtered on the way out.
Sharding, hot prefixes, and the parts that break
A single trie for a billion queries will not fit on one box, so you shard, and the obvious sharding key is the wrong one. Splitting by first letter, everything under “a” on one node group, “b” on another, breaks the moment you look at real data, because far more queries begin with “how” than with “xz”, and the shard that owns a viral prefix melts while its neighbor sits idle. Sharding on a hash of the full prefix string spreads load evenly and gives up range locality, which does not matter here because you always look up one complete prefix and never scan a range. The genuinely hot prefixes get the simplest fix there is: a cache in front, since the top few thousand prefixes serve a large share of all traffic and their answers barely move within a minute.
On the client, debouncing earns its place. Firing a request on every keystroke throws most of them away, since the person is still mid-word. Waiting 100 to 300 milliseconds after the last keystroke, and cancelling the in-flight request when a new character lands, cuts backend load by a large factor and stops out-of-order responses from painting stale suggestions over fresh ones. Send back results the client can render as-is, and let it discard any response that arrives for a prefix the user has already typed past.
Typos are the last thing interviewers like to throw in. A bare trie has nothing to say about “goggle” when the person meant “google”, because that path simply does not exist in the tree. Fuzzy matching within an edit distance of one or two catches most real typos, and it is expensive enough that you run it as a fallback only when the exact-prefix lookup comes back thin, not on every request. Edge n-grams or a dedicated fuzzy layer in the search backend handle this far better than a plain trie, which is one more reason the hybrid design keeps surfacing in good answers.
Almost everyone draws the trie. What sets an answer apart is noticing that the latency budget forces every hard decision downstream of it, that ranking and freshness are where the product actually lives, and that the write path is a separate system running on a slower clock than the reads. Say that early, and most of the rest of the design falls out of it on its own.
Keep sharpening your system design:
