System design interview question

Design Search Autocomplete

Suggest the top ten completions after every keystroke, in under fifty milliseconds, from what the world searched for in the last hour, without suggesting anything that gets you in the newspaper.

Last updated 2026-09-22. Difficulty: medium. Patterns: tries, ranking, caching, search, stream-processing. Reported at Google and 5 more with Pro.

Walk through a strong candidate's answer, turn by turn.

The interviewer asks, the candidate answers and draws, and you press Next. Pause to answer yourself at the key decisions, and ask the coach anything along the way.

Walk through it Take the mock interview

Functional requirements

Return the top ten completions for a prefix. Ranked by popularity, not alphabetically. The ordering is the product; the prefix match is the easy part.
Respond on every keystroke. Query volume is several times search volume, because a ten-character query produces up to ten requests.
Reflect what is trending. A breaking news term must appear within minutes. A suggestion index rebuilt nightly is a day behind the thing people are actually typing.
Personalise lightly. A user's own recent searches rank above global ones for the same prefix, without a per-user index.
Tolerate typos and prefix gaps. "recieve" should still suggest "receive"; "new yor" should suggest "new york".
Filter unsafe and abusive suggestions. Autocomplete puts words in the product's mouth. Blocklists, category suppression and a kill switch for a specific suggestion are requirements, not extras.
Out of scope. The search results themselves, spelling correction of the submitted query, and multilingual transliteration beyond per-language indexes.

Non-functional requirements

Latency (p99 < 50 ms end to end). A suggestion that arrives after the next keystroke is wasted work. This budget is the design constraint that decides everything else.
Query rate (500 k/s peak). Roughly five keystroke requests per search, against 100 k searches/s. Reads dominate by orders of magnitude.
Freshness (trending terms within 10 minutes). Slower than a news site, far faster than a nightly batch. The gap between those two is where the design lives.
Availability (99.99 %). Degrades gracefully: no suggestions is an acceptable search box, an error is not.
Index size (fits in memory per shard). Disk seeks do not fit a 50 ms budget with a keystroke rate this high. If it does not fit in RAM, prune it until it does.
Cache hit rate (> 90 %). Prefix popularity is extremely skewed, so short prefixes are served almost entirely from cache. Everything after that is a rounding error on capacity.
Safety (blocked terms never served). A false negative here is a public incident, so filtering is applied at build time and again at serve time.

Back-of-envelope estimates

Requests per second: ~500 k/s. 100 k searches/s × ~5 keystroke requests each after debouncing a 10-character query = ~500 k/s. Without debouncing it would be twice that, which is why the client debounces.
Distinct queries worth indexing: ~100 M. Billions of distinct queries are seen, but the tail is seen once and helps nobody. Keeping terms with at least ~50 occurrences in 30 days leaves ~100 M: two orders of magnitude smaller and almost all of the value.
Index size in memory: ~30 GB. 100 M terms × ~30 B average, plus the top-10 list cached at each of ~50 M internal nodes at ~80 B = ~25–35 GB. Shards by prefix so each holds a few GB.
Cache hit rate and size: > 90 % from ~1 GB. Prefix frequency follows a steep power law: the top 1 M prefixes cover the great majority of requests. 1 M entries × ~1 KB of serialised suggestions = ~1 GB and > 90 % hits.
Log volume for ranking: ~10 B events/day. 100 k searches/s × 86 400 = ~9 B searches/day, plus selection events. At ~100 B each that is ~1 TB/day feeding the popularity counts.
Index build time: ~20 min. Aggregate a 30-day window with a recency weighting, prune, build the trie, serialise, distribute: ~20 minutes end to end on a batch cluster. That sets the floor on full-rebuild freshness and is why a separate trending layer exists.
Bandwidth per response: ~500 B. Ten suggestions × ~30 characters plus scores and JSON overhead ≈ 500 B compressed. At 500 k/s that is ~250 MB/s of egress: small, and worth keeping small because mobile users pay for it.

Components

Search box: Debounces keystrokes to about 100 ms, cancels in-flight requests when the user types again, and caches locally so backspacing costs nothing. Roughly half the total load is removed here before a request is ever sent.
Edge / CDN: Caches responses for short, popular prefixes at the edge with a short TTL. Because those prefixes are an enormous share of traffic, this is the single largest latency and capacity win in the design.
Suggest API: Normalises the prefix (lowercase, trim, collapse whitespace, strip accents) then checks the cache, queries the right shard, merges in trending and personal terms, filters, and returns. Stateless.
Prefix cache (Redis · prefix → top 10): The merged, filtered, ready-to-serve answer for a prefix, with a TTL of a minute or two. Short TTLs rather than invalidation: suggestions are a ranking, and a ranking that is ninety seconds old is indistinguishable from a fresh one.
Suggestion shards (in-memory trie, by prefix range): Each holds a slice of the trie with the top ten precomputed at every node, so a lookup is a walk down the prefix and a read: no traversal of the subtree at query time. Replicated for read throughput.
Trending layer (stream counts, 10-minute windows): Terms whose rate has risen sharply in the last few minutes, held separately from the main index and merged at query time with a boost. This is how the system is minutes fresh without rebuilding a 30 GB trie every few minutes.
Personal history (key-value, user → recent queries): A user's last few dozen searches, read in parallel with the shard query and merged above global results for the same prefix. Small, per-user, and never mixed into the shared index or the shared cache.
Safety filter: Blocklists, category classifiers and manual suppressions, applied when the index is built and again on the way out. Applied twice on purpose: a build-time-only filter means a bad suggestion is live until the next build.
Query log stream (Kafka): Every search and every suggestion the user selected. Selections matter more than searches for ranking: they say which suggestion was the one people wanted.
Count aggregator (stream + batch): Maintains 30-day decayed counts per term and the short-window rates that feed trending. One pipeline, two outputs on different cadences.
Index builder: Prunes the tail, applies safety filters, builds the trie with top-10 lists at every node, serialises it, and publishes a versioned artefact. Runs hourly.
Index artefacts (object store, versioned): Immutable built indexes. Shards download and swap atomically, and a bad build is rolled back by pointing at the previous version rather than by rebuilding under pressure.

User flows

A user types "new y". The hot path, and it has to fit in 50 ms. Almost every request should end at the first or second box.
1. The client debounces and cancels the previous in-flight request. About 100 ms of debounce and an abort on the superseded request. A fast typist generates three requests for a ten-character query instead of ten, and none of the wasted ones occupy a connection.
2. The edge serves it from cache if this prefix is popular, which it usually is. Short prefixes are a huge share of traffic and identical for everyone who is not personalised, so they never reach the origin. A five-second TTL at the edge is invisible to users and removes most of the load.
3. On a miss, the API normalises the prefix and checks the prefix cache. Normalisation is where correctness quietly lives: "New Y", "new y" and "nèw y" must hit the same cache entry, or the hit rate collapses and the rankings look inconsistent.
4. The API asks the shard that owns this prefix range. Walk five characters down the trie and read the precomputed top-10 at that node. No subtree traversal, no sorting: the work was done at build time, which is the whole reason the budget is achievable.
5. Trending and personal results are fetched in parallel and merged. Both calls run concurrently with the shard call and both have a hard deadline of a few milliseconds. If either is slow it is dropped from the merge: a slightly worse ranking is always better than a missed budget.
6. The safety filter runs, the result is cached, and the response goes back. Filtering after the merge, not before, so a trending or personal term cannot slip past a filter that only ran at build time. The cache stores the post-filter list, so the filter runs once per prefix per TTL rather than once per request.
How a suggestion earns its place. The background loop that makes the top ten good. Selections, not searches, are the signal that matters.
1. The client logs the search and, crucially, which suggestion was selected. A suggestion that is shown a million times and selected twice is a bad suggestion, and only the selection event reveals that. Logging searches alone creates a feedback loop where whatever is shown becomes popular because it is shown.
2. The aggregator maintains decayed counts over a rolling 30-day window. Exponential decay with a half-life of about a week: recent behaviour dominates without last month vanishing. A plain 30-day count makes the index feel a month stale; no window at all makes it feel like 2019.
3. The builder prunes the tail, filters, and builds the trie with top-10 lists at every node. Precomputing the top-10 at each node is the key move: it trades a few GB of memory for turning every query from a subtree scan into a pointer read. Building bottom-up, each node merges its children's lists, so the whole thing is one pass.
4. The artefact is published, versioned and immutable. Immutable versions make rollback a configuration change. A bad build (a filter regression, a corrupt shard) is reverted in seconds rather than rebuilt in twenty minutes.
5. Shards download the new version and swap atomically. Load beside the live index, warm it, then flip a pointer; free the old one after in-flight requests drain. Briefly double memory, never a cold shard. Replicas swap in a staggered order so a bad build shows up on one replica before all of them.
A term starts trending at 14:03. Hourly rebuilds cannot cover breaking news. A small, fast, separate layer does, merged at query time.
1. Searches for a new term jump from near zero to thousands a minute. The main index has never seen the term, so no rebuild schedule short of continuous would help. The property that matters is the rate of change, not the count.
2. The aggregator computes short-window rates and flags terms rising sharply against their baseline. Rate over a ten-minute window against the trailing baseline for the same term. Comparing against its own baseline rather than a global threshold is what stops "weather" trending every single morning.
3. Flagged terms go into the trending layer, keyed by their prefixes. Only the first few prefixes of each term are indexed (enough to catch the user early in typing) so the structure stays a few thousand entries and fits comfortably in memory everywhere.
4. Queries merge trending candidates with a time-decaying boost. The boost decays over hours, so a term either earns its place in the next hourly rebuild or fades out. Without the decay, yesterday's news sits at the top of the box for a week.
5. Trending terms pass the safety filter like everything else, in fact more strictly. This is the path that surfaces suggestions nobody reviewed, attached to whatever is happening in the world right now. Trending candidates go through tighter classifiers and a category blocklist, and a human kill switch exists for a specific term.
6. The next hourly build absorbs the term and the boost is no longer needed. The two layers hand over cleanly: trending covers minutes, the index covers everything older. Neither has to do the other's job, which is why both stay simple.
The user types "new yorl". A strict prefix match returns nothing and the box goes empty: the most common way autocomplete feels broken.
1. The exact prefix lookup finds no node in the trie. An empty result is the worst possible response: the user assumes the feature is broken rather than that they mistyped. Every real implementation has a fallback, and the question is how expensive it is allowed to be.
2. The API retries with an edit-distance-tolerant lookup, bounded tightly. A single edit on the last few characters only, because errors cluster at the end of what has just been typed. Full fuzzy matching over a 100 M-term trie does not fit the latency budget, and this covers most real typos.
3. Fuzzy matches are scored down so an exact match always wins. A fixed penalty per edit. Otherwise a popular near-miss outranks the exact thing the user typed, which is far more annoying than an empty box.
4. If fuzzy also finds nothing, fall back to the longest prefix that did match. Back off to "new yor", then "new yo". Something plausible beats nothing, and the shorter prefix is almost certainly a cache hit, so the fallback is nearly free.
5. The selection, if any, is logged against the prefix that was actually typed. This is how the system learns the misspelling. Over time "new yorl" accumulates selections of "new york" and becomes an exact, cheap mapping rather than a fuzzy search.
A suggestion has to be removed now. The path that matters when something goes wrong in public. Minutes, not the next build.
1. A harmful suggestion is reported for a particular prefix. Usually a combination the classifiers did not anticipate: a person's name with a defamatory completion. The response time is a reputational metric, not an engineering one.
2. An operator adds a suppression for the term or the (prefix, term) pair. Two granularities on purpose: suppress a term everywhere, or only under the prefix where it is harmful. Blanket suppression of a common word does collateral damage.
3. The suppression list is pushed to every API instance within a minute. Small enough to hold in memory everywhere and refresh on a short interval. It is applied at serve time precisely so removal does not wait for a rebuild.
4. Affected cache entries are invalidated. Otherwise the suppressed suggestion keeps being served from cache for the TTL, which, during an incident, is exactly long enough for a screenshot. Suppression writes bump a global cache generation for the affected prefixes.
5. The next build excludes it permanently and the suppression stays as a backstop. Belt and braces: build-time exclusion keeps it out of the index, and the serve-time list catches it if a future build regresses. Suppressions are reviewed periodically but expire only deliberately.

Deep dives

The data structure behind the prefix lookup

Trie with precomputed top-k, a sorted array with binary search, or an inverted index?

The operation is: given a prefix, return the ten highest-scoring terms that start with it, in a few milliseconds. The naive trie answer (walk to the node, traverse the subtree, sort) is far too slow for a short prefix, where the subtree is most of the index.

The fix is to move the work to build time. Storing the top ten at every node turns the query into a walk plus a read, at the cost of memory and of rebuilding when scores change.

Trie with the top-k precomputed at every node chosen
Sorted array of terms with binary search for the prefix range situational: a small catalogue (product names in one store) where ranges are short
Inverted index / search engine with edge n-grams situational: suggestion quality needs real relevance scoring over structured documents rather than popularity over strings
Precomputed key-value: every prefix → its top 10 situational: a bounded domain (airport codes, city names) where the prefix set is small

The answer: A compressed trie (radix tree) per language with the top ten precomputed and stored at every node, held entirely in memory, sharded by prefix range and replicated for read throughput. Built hourly as an immutable artefact and swapped in atomically. Fuzzy matching is a bounded extension over the same structure rather than a second index.

How much memory do the top-k lists actually add?

Storing the ten terms as pointers or ids rather than strings (roughly 4 bytes each plus a score) is about 80 bytes a node. With tens of millions of internal nodes that is a few gigabytes on top of the terms themselves. Storing the strings inline would be several times worse, which is why the lists hold ids into a term dictionary.

Where do you shard, and what breaks at the boundary?

By first two or three characters, with ranges balanced by traffic rather than by term count, because prefix popularity is wildly uneven. Nothing breaks at a boundary because a query only ever needs one shard: every term matching a prefix shares that prefix by definition. That is the property that makes this shard beautifully, unlike a general search index.

A single shard gets hot: everything starting with "a".

Split that range further and add replicas. Because shards are read-only artefacts, adding replicas is just copying a file and updating routing; there is no rebalancing of live data. The edge cache absorbs most of the imbalance before it reaches a shard anyway.

Why one index per language rather than one big one?

Ranking and normalisation are language-specific (accent folding, tokenisation, what counts as a prefix in a script without spaces) and mixing languages puts irrelevant terms in everyone's top ten. Separate indexes also mean a language can be rebuilt or rolled back on its own.

Keeping suggestions current

How do you get from a nightly batch rebuild to "trending within ten minutes"?

A full rebuild takes about twenty minutes and produces a 30 GB artefact that has to be distributed and swapped. Running it every ten minutes would mean the cluster is permanently building and swapping indexes, for a benefit confined to a handful of terms.

The asymmetry is the key: almost nothing changes rank quickly, and the few things that do change a lot. That argues for a small fast layer beside a large slow one rather than making the large one fast.

Hourly full rebuild plus a small real-time trending layer merged at query time chosen
Continuous incremental updates to the live trie situational: a small index (a site search over ten thousand products) where propagation is cheap
Nightly rebuild only rejected
Rebuild every ten minutes situational: a much smaller index where a rebuild is seconds rather than twenty minutes

The answer: Immutable hourly rebuilds of the main trie, plus a trending layer computed from ten-minute windows and replicated to every API instance, merged at query time with a decaying boost. Personalisation is merged the same way, from a per-user store. The merge is the only place ranking signals combine, which keeps calibration in one function rather than three.

How do you calibrate the trending boost against index scores?

Put both on a comparable scale (log of the decayed count) and express the boost as a multiplier on the trending term's current rate relative to its baseline, capped. Then check it empirically: the fraction of sessions where a trending suggestion was shown and selected. Set by feel, it either does nothing or floods the box.

A term appears in both the index and the trending layer. What happens?

Deduplicate on the normalised term and keep the higher score. Simple, but it must be done after normalisation, or "New York" and "new york" both appear: one of the most common visible bugs in this kind of system.

The trending layer is down. What does the user see?

Slightly stale suggestions and nothing else. It is on a short deadline in the parallel fetch and is dropped from the merge if it misses. That is the point of keeping it separate: the fresh layer is the one allowed to fail.

How do you stop the index reinforcing itself?

Rank on selections rather than impressions, and normalise by how often a suggestion was shown. A term shown a million times and selected twice should fall, even though a naive count says it is popular. Without that correction, whatever reaches the top ten stays there forever regardless of quality.

Meeting a 50 ms budget at 500 k/s

Where does the budget go, and what do you do when part of it is missed?

Fifty milliseconds end to end includes the network. For a mobile user on a distant network, the round trip alone can be thirty, which leaves almost nothing for the server. That single fact pushes the design towards the edge before anything else.

The second lever is that suggestion traffic is enormously skewed: a small number of prefixes are a large majority of requests, and they are identical for every non-personalised user.

Client debounce, edge cache for short prefixes, in-memory shards, deadline-bounded parallel merges chosen
Origin-only, no edge cache rejected
Ship the index to the client situational: a bounded domain (the contacts list, a product catalogue of a few thousand items) where a small index can be pushed down
Persistent connection streaming suggestions as the user types situational: a desktop app with a long-lived session where the search box is central

The answer: Debounce at about 100 ms in the client with cancellation of superseded requests and a local cache for backspacing; cache short non-personalised prefixes at the edge with a five-second TTL and stale-while-revalidate; serve everything else from in-memory shards with trending and personal lookups issued in parallel under a hard few-millisecond deadline, dropped from the merge if they miss. No component on the path touches disk.

Personalisation and edge caching conflict. How do you resolve it?

Serve the global response from the edge and merge personal terms in the client from its own recent-search store. The user's own history is already on their device, so the merge needs no server round trip and no per-user cache key: the edge stays shared and the response is still personalised.

What happens if a shard is slow?

The request has a deadline. If the shard misses it, return whatever the cache and trending gave, or an empty list. An empty suggestion box is a mildly worse search experience; a search box that hangs is a broken product. Fixed deadlines with partial results is the right default for anything on a typing path.

Does debouncing hurt the experience?

Barely, and it must be tuned rather than guessed. Around 100 ms is below the threshold where typists notice, and it removes half the traffic. Too long (300 ms) and the box visibly lags behind fast typists, who are exactly the users most likely to be irritated.

How do you measure the 50 ms if most requests are cached?

Measure at the client, from keystroke to render, and report percentiles by cache outcome and by region. Server-side timing flatters you: it excludes the network, which for this feature is most of the budget. A p99 measured at the origin can look fine while the product feels slow everywhere outside its home region.

Suggestions are speech

How do you stop the product putting harmful words in its own mouth?

Autocomplete is generated from what people type, which means it will eventually suggest something defamatory, obscene or dangerous next to a real person's name. Several companies have been sued over exactly this.

It is not a pure classification problem: the same term is fine in one prefix and harmful in another, and a blanket blocklist damages legitimate queries, including the ones people most need answered.

Layered filtering: build-time exclusion, serve-time suppression, and per-pair rules chosen
Build-time filtering only rejected
Classifier at query time only situational: as an offline process that proposes suppressions for human review
Suppress suggestions entirely for sensitive categories situational: named individuals, elections, and self-harm, where most large products do restrict suggestions

The answer: Filtering at both ends: the builder excludes blocklisted terms and anything a classifier flags above a threshold, and the API applies a small, frequently refreshed suppression list at serve time, after the merge, with both term-level and (prefix, term)-level rules. Suppressing invalidates the affected cache entries immediately. Suggestions against what look like named individuals are restricted by category rather than left to per-term rules.

Why filter after the merge rather than before?

Because trending and personal terms never went through the build-time filter. Filtering only the index leaves the two freshest, least reviewed sources unchecked, which are precisely the ones that will surface something about a breaking news event. The last thing before the response is the only place that sees everything.

A legitimate query is caught by a blocklist. How is that found?

Log suppressions as events with the prefix and the rule that fired, and review the high-volume ones. A rule suppressing something people are typing thousands of times a day is either doing exactly its job or is badly wrong, and only a human can tell which. Silent filtering with no telemetry is how blocklists rot.

Does the cache undermine suppression?

It would, so suppression writes bump a cache generation for the affected prefixes and the entries are dropped. Without that, a suppressed suggestion keeps serving for the TTL, which is fine in the abstract and unacceptable during an incident with a journalist watching.

How do you handle this across languages and regions?

Blocklists are per language and per region, because harm is contextual and a word that is innocuous in one language is a slur in another. It also means a suppression in one market does not silently apply worldwide, which matters both legally and for trust.

Personalising without a per-user index

How do you rank a user's own history above global results without building 500 million indexes?

Users strongly expect their own recent searches to come first. Building a per-user suggestion index is out of the question at this scale, and it would also destroy the cache hit rate that makes the whole design affordable.

The saving grace is that personal history is tiny (a few dozen terms) and prefix-matching a few dozen strings is trivial wherever it happens.

Global index plus a small per-user recent list, merged at the edge of the request chosen
Per-user index rejected
Cohort indexes: by language, region or interest segment situational: strong regional variation, where a per-country index is genuinely different, and that is really localisation rather than personalisation
Client-side merge only situational: privacy-first products, and as the implementation of the merge even when history is also stored server-side

The answer: A per-user list of recent searches and selections (a few dozen terms) prefix-matched and merged above global results for the same prefix, with a decay so a search from three months ago does not outrank what is relevant now. The merge happens in the client where possible, so the shared edge cache keeps working; the server-side store exists for cross-device continuity and is fetched in parallel under the same deadline as everything else.

How far should a personal term outrank a global one?

Far enough to be visibly first when it genuinely matches, but not so far that a single mistyped search haunts the box for weeks. A large boost with a decay of days, plus a cap on how many personal suggestions can occupy the top ten (typically two or three) so the list does not become a history viewer.

What about privacy and deletion?

It is the user's search history, which is about as sensitive as data gets. It lives in its own store, keyed by user, with a short retention, an in-product control to clear it, and exclusion from the global counts when the user is in a private mode. Deletion has to actually remove it from the store rather than only hiding it, and that has to be true of the client copy too.

Does personalisation break the edge cache?

It would if the merge happened server-side for every request, which is why the client does it whenever it can: the edge serves the shared global response, and the client merges from local storage. Server-side personalisation is reserved for a signed-in user on a new device, where a cache miss is acceptable because it happens rarely.

A user searches for something embarrassing once. How long does it follow them?

Until the decay makes it uncompetitive, or until they clear it, and the in-product control has to be genuinely easy to find, because this is the single most common complaint about personalised suggestions. It is also an argument for a shorter retention than the ranking would ideally want.