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

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 do you get from a nightly batch rebuild to "trending within ten minutes"?

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.

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

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.

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

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.

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

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.

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, Amazon, Meta, Netflix, Airbnb, LinkedIn.

Sit this as an AI interview and be asked it one question at a time; Study shows every answer, and Practice hides them until you have produced your own.

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.
2. The edge serves it from cache if this prefix is popular, which it usually is.
3. On a miss, the API normalises the prefix and checks the prefix cache.
4. The API asks the shard that owns this prefix range.
5. Trending and personal results are fetched in parallel and merged.
6. The safety filter runs, the result is cached, and the response goes back.
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.
2. The aggregator maintains decayed counts over a rolling 30-day window.
3. The builder prunes the tail, filters, and builds the trie with top-10 lists at every node.
4. The artefact is published, versioned and immutable.
5. Shards download the new version and swap atomically.
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.
2. The aggregator computes short-window rates and flags terms rising sharply against their baseline.
3. Flagged terms go into the trending layer, keyed by their prefixes.
4. Queries merge trending candidates with a time-decaying boost.
5. Trending terms pass the safety filter like everything else — in fact more strictly.
6. The next hourly build absorbs the term and the boost is no longer needed.
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.
2. The API retries with an edit-distance-tolerant lookup, bounded tightly.
3. Fuzzy matches are scored down so an exact match always wins.
4. If fuzzy also finds nothing, fall back to the longest prefix that did match.
5. The selection, if any, is logged against the prefix that was actually typed.
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.
2. An operator adds a suppression for the term or the (prefix, term) pair.
3. The suppression list is pushed to every API instance within a minute.
4. Affected cache entries are invalidated.
5. The next build excludes it permanently and the suppression stays as a backstop.

Deep dives

The data structure behind the prefix lookup. Trie with precomputed top-k, a sorted array with binary search, or an inverted index? 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.
Keeping suggestions current. How do you get from a nightly batch rebuild to "trending within ten minutes"? 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.
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? 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.
Suggestions are speech. How do you stop the product putting harmful words in its own mouth? 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.
Personalising without a per-user index. How do you rank a user's own history above global results without building 500 million indexes? 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.