Search Autocomplete (Typeahead) System Design Interview
Google handles on the order of 8.5 billion searches per day, and it starts suggesting completions the moment you type the first letter, usually returning fresh suggestions in a few tens of milliseconds. The per-keystroke read volume is several times the search volume because most searches involve typing many characters (search count is public, the per-keystroke multiplier is estimated).
A typeahead system suggests the most likely completions for whatever prefix a user has typed so far, and it does this on every keystroke. The read path must be extremely fast because a suggestion has to come back before the user types the next character. The core trick is a trie (prefix tree) where each node stores the precomputed top-k completions for that prefix, so a lookup is O(length of the prefix) instead of a scan. Popularity comes from an offline pipeline that mines historical query logs and rebuilds the trie on a schedule. A separate fast path layers recent trends on top so spikes show up without waiting for the next full rebuild.
Asked at: Asked at Google, Amazon, Meta, LinkedIn, Microsoft, and most companies that run a search box. It is one of the most common system design interview questions because almost every product has a search or lookup field.
Why this question is asked
Interviewers like typeahead because it forces a candidate to reason about an extreme read-latency budget. Every keystroke is a query, so the system sees several reads per search and each read must return in the low tens of milliseconds. On top of that you have to rank: returning any matching prefix is easy, but returning the best top-k completions ordered by popularity and recency is the real problem. The candidate has to separate the read path (serve precomputed answers fast) from the write path (aggregate query logs, compute popularity, and rebuild the index) and then explain how the two stay in sync. It also opens up prefix matching at scale, sharding a large term set, caching hot prefixes, and keeping trending queries fresh, which gives an interviewer many directions to probe.
Requirements
Always clarify these in the first 5 minutes of the interview. Do not start drawing boxes until both lists are agreed.
Functional requirements
- Given a prefix the user has typed, return the top-k most likely full completions, typically k between 5 and 10.
- Update suggestions on every keystroke as the prefix grows or shrinks.
- Rank completions by a blend of historical popularity and recency rather than alphabetical order.
- Reflect newly trending queries so a query that spikes today can appear the same day, not only after a full rebuild.
- Filter out offensive, unsafe, or policy-violating suggestions before they are shown.
- Optionally personalize suggestions using the user's own recent history or location.
- Optionally tolerate small typos so a prefix with a single wrong character still returns useful completions.
- Support multiple languages and locales with separate ranking per market.
- Return an empty or fallback response gracefully when no suggestion clears the quality threshold.
Non-functional requirements
- p99 suggestion latency under about 100 ms including network round trip, with a server-side budget closer to 10 to 25 ms.
- Very high read QPS, on the order of hundreds of thousands to millions of prefix lookups per second at large scale.
- High availability for the read path, since a dead autocomplete degrades the whole search experience.
- Suggestions should be fresh within a bounded window, for example daily for the bulk rebuild and minutes for the trending fast path.
- Read-heavy by design, with a read to write ratio that is extremely lopsided.
- Horizontally scalable so the term set and QPS can grow without a rewrite.
- Eventual consistency for popularity is acceptable, exact real-time counts are not required.
Back-of-envelope scale estimates
Show your math. Pulling numbers from thin air signals you have not thought about the load.
Search queries per day
~8.5 billion (Google, public estimate)
Widely cited public figure for Google search volume. Used as the baseline that the per-keystroke read load is derived from.
Prefix lookups per second
~600k to 2M/sec (derived)
If a typical query is typed as 4 to 6 keystrokes that each trigger a debounced lookup, the per-keystroke read rate is several times the search rate. 8.5B searches/day is about 100k searches/sec averaged, and roughly 6x for keystrokes gives the derived range. Peak is higher than average.
Distinct terms and phrases in the suggestion set
hundreds of millions to low billions (estimated)
The head of the distribution is small, but the long tail of real queries is enormous. Most systems keep only phrases above a frequency threshold, which trims a raw multi-billion set down to a servable size.
Storage for the trie with precomputed top-k
tens to low hundreds of GB (estimated)
A trie node storing k completion pointers plus scores costs more than the raw strings, but heavy compression (shared prefixes, FST encoding) keeps a servable English index in the tens of GB range, which fits in memory across a shard set.
Query log volume ingested per day
single-digit TB/day (estimated)
Every search plus metadata (timestamp, locale, result click) is logged. At billions of events per day with a few hundred bytes each, the daily aggregation input is in the terabytes.
Rebuild / update cadence
full daily + trending every few minutes (design choice)
A full trie rebuild from aggregated logs runs once or a few times per day. A lightweight streaming path updates counts for spiking queries on the order of minutes so trends surface quickly.
High-level architecture
The client is the first line of defense. It debounces keystrokes, usually waiting 100 to 300 ms of typing pause before firing a request, and cancels in-flight requests when the prefix changes, which cuts the request count sharply. Requests hit an edge tier where a CDN or edge cache serves the hottest short prefixes directly, since a small number of one and two character prefixes account for a large share of traffic. Cache misses go to the suggestion service, which is a stateless read tier fronting an in-memory trie. Each trie node stores the precomputed top-k completions for the prefix that ends at that node, so serving a request is a walk of the prefix followed by a read of the stored list, which is O(length of the prefix) with no ranking work at query time. The trie is sharded, commonly by prefix range, and replicated for availability and read throughput. Feeding all of this is an offline pipeline that is fully decoupled from the read path. It consumes query logs, aggregates them with a batch or streaming job to compute popularity and recency scores, prunes low-frequency phrases, applies safety filters, computes the top-k at every node, and ships a new immutable trie to the serving tier via an atomic swap. A separate fast path updates counts for recently spiking queries so trends appear within minutes rather than waiting for the next full rebuild.
In a real interview, sketch this on the whiteboard before diving into any single box.
Core components
Walk through each service. The interviewer wants to hear what each one owns, not just the names.
Client debouncer
Runs in the browser or app. Waits for a short typing pause, cancels stale requests, and caches results for prefixes the user has already seen during the session. This removes a large fraction of would-be requests before they leave the device.
Edge cache / CDN
Caches suggestion responses for the hottest short prefixes with a short TTL. Short prefixes are queried by almost everyone, so a small cache absorbs a disproportionate share of read traffic and protects the origin service.
Suggestion service (read tier)
A stateless, horizontally scaled service that receives a prefix, routes to the correct trie shard, walks the prefix, and returns the precomputed top-k list. It also merges in the trending fast path and applies per-request personalization if enabled.
Trie / prefix store
The in-memory index. A trie, ternary search tree, or FST where each node holds the precomputed top-k completions for its prefix along with scores. Built offline and served as an immutable, atomically swapped artifact.
Offline aggregation pipeline
A batch or streaming job that reads query logs, computes popularity and recency, prunes and filters, computes top-k at each node, and produces the new trie. This is the write path and it never blocks reads.
Trending fast path
A lightweight streaming counter (for example over the last few hours) that tracks recently spiking queries and injects them into results so trends surface long before the next full rebuild.
Safety and quality filter
Applies blocklists, policy models, and quality thresholds so offensive or unsafe phrases are removed before they enter the served trie or the trending path.
Data model
Pick the right store per table. Justify each choice with the access pattern, not by reflex.
prefix_topk (served trie)prefix (or node id)completions (ordered top-k with scores)shard_idThe read-optimized artifact. Conceptually a map from each prefix node to its precomputed top-k completions. Stored as a compressed trie or FST in memory, not as literal rows, so a lookup is O(prefix length).
query_frequencyquery_phrasecountrecency_weighted_scorelocalelast_updatedThe aggregation table the offline pipeline maintains from logs. Popularity plus a recency decay produces the final ranking score used to compute top-k.
term_metadataquery_phraseis_blockedlanguagecategoryquality_scorePer-phrase attributes used for filtering and ranking. Blocked or low-quality phrases are excluded from the served trie.
trending_countsquery_phrasewindow_startshort_window_countvelocityShort-window counts for the fast path. High velocity relative to baseline marks a phrase as trending so it can be injected into results within minutes.
user_personalization (optional)user_idrecent_querieslocationupdated_atPer-user recent history and context used to re-rank or add a small number of personal suggestions on top of the global top-k. Kept in a fast key-value store.
Deep dives
These are the conversations the interviewer is steering you toward. Practice each one until you can talk through it without notes.
The trie with precomputed top-k at each node
A plain trie lets you find all completions under a prefix, but that still means walking the whole subtree and then ranking, which is far too slow for millions of lookups per second. The key optimization is to store, at each node, the already-ranked top-k completions for the prefix that ends at that node. Serving a request then becomes: walk the characters of the prefix down the trie, and when you land on the final node, read its stored top-k list. That is O(length of the prefix) plus a constant-size read, with no subtree traversal and no sorting at query time. The trie is built offline, so the cost of computing top-k at every node is paid once per rebuild and amortized across billions of reads.
Why precompute top-k instead of ranking at query time
Ranking at query time would mean, for every keystroke, gathering all completions under the prefix, scoring each by popularity and recency, and sorting to pick the top-k. Under a budget of a few tens of milliseconds and hundreds of thousands of requests per second, that work is prohibitively expensive and wildly redundant, because the same popular prefixes are queried constantly and would be re-ranked identically each time. Precomputing moves all of that cost to the offline build, where it runs once and is shared by everyone. The tradeoff is freshness: precomputed answers are only as current as the last build, which is exactly why the trending fast path exists to patch in recent movement.
The offline aggregation pipeline
The write path is a batch or streaming job that turns raw query logs into a ranked, filtered index. It reads logs (query text, timestamp, locale, and often whether the result was clicked), aggregates counts per phrase with a map-reduce or streaming framework, applies a recency decay so last month's fad does not outrank today's demand, prunes phrases below a frequency threshold to keep the set servable, runs safety and quality filters, and finally computes the top-k at each trie node and serializes the whole structure. The new trie is shipped to the serving tier and swapped in atomically, so readers always see either the old complete index or the new complete index, never a half-built one. Because this pipeline is fully decoupled from reads, a slow or failed build degrades freshness but never latency or availability.
Caching hot prefixes at the edge
The distribution of prefixes is extremely skewed. Single and double character prefixes are typed by nearly every user, so a small set of prefixes accounts for a large share of all lookups. Caching the responses for these hot short prefixes at a CDN or edge tier with a short TTL absorbs a big fraction of traffic close to the user, cutting both latency and origin load. Because suggestions for a given prefix are identical across users (before any personalization), they are highly cacheable. Longer, rarer prefixes have poor cache hit rates and fall through to the suggestion service, which is fine because they are also far less frequent.
Sharding the trie: prefix range vs hashing
The full trie is too large and too hot for one machine, so it is partitioned. Sharding by prefix range (for example a to f on one shard, g to m on another) keeps an entire prefix subtree on a single shard, so a lookup touches exactly one shard and range-based routing is simple. The downside is load skew, because some first letters are far more common than others, so ranges must be sized by traffic rather than evenly by the alphabet. Sharding by a hash of the prefix spreads load more evenly, but a hash of the full prefix scatters related prefixes across shards, and you generally shard on a short prefix key to keep each lookup on one shard. Most designs favor traffic-balanced prefix ranges plus replication of the hottest shards.
Freshness for trending queries
A daily rebuild is fine for stable popularity but useless for a query that spikes because of breaking news, since users expect it to appear within minutes. The answer is a layered fast path. A lightweight streaming job counts queries over a short recent window and flags phrases whose velocity is high relative to their baseline. Those trending phrases are injected into the served results, either by patching the relevant trie nodes in memory or by merging a small trending list into the response at serve time. This gives a two-speed system: a heavy, high-quality daily trie for the bulk of ranking, and a light, fast overlay for what is moving right now.
Typo tolerance and safety filtering
Strict prefix matching fails the moment a user mistypes a character, so some systems add fuzzy matching, for example allowing a small edit distance or precomputing common misspelling variants that point at the corrected phrase. This is expensive, because it widens the search from one path to many, so it is usually bounded to a single edit and applied only when strict matching returns too few results. Safety is handled at build time and serve time: blocklists and policy models remove offensive, unsafe, or legally sensitive phrases before they enter the served trie, and a final serve-time check catches anything that slips through, since an autocomplete that suggests harmful text is a serious product and reputational problem.
Trade-offs to discuss
Every senior interviewer expects you to surface at least 3 of these. Pick the decisions, state the alternatives, and justify your choice.
Precompute top-k vs rank on the fly
Precomputing gives O(prefix length) reads and shares work across billions of requests, at the cost of freshness and a heavier offline build. Ranking on the fly is always current but cannot meet the latency and QPS budget. Precompute wins for the bulk path, with a fast overlay for freshness.
Trie in memory vs on disk
In-memory serving meets the tens-of-milliseconds budget but costs RAM and forces aggressive compression and sharding. On-disk or SSD-backed serving is cheaper and holds a larger set but adds I/O latency that is hard to fit in the budget for the hot path. Most designs keep the head in memory.
Daily rebuild vs near-real-time updates
A daily batch rebuild is simple, produces a clean immutable artifact, and is easy to validate, but it is stale for trends. Near-real-time updates are fresh but complex and risk serving noisy or unsafe spikes. The common answer is both: batch for quality, streaming overlay for freshness.
Prefix-range sharding vs hash sharding
Prefix-range sharding keeps each lookup on one shard and makes routing trivial, but suffers load skew that must be corrected by traffic-weighted ranges. Hash sharding balances load but can scatter related prefixes and complicates range logic. Range sharding plus replication of hot shards is the usual choice.
Personalization on vs off
Personalized suggestions can lift relevance and engagement, but they destroy the shared-cache property (every user needs a different answer), add a per-user store and lookup on the hot path, and raise privacy concerns. Many systems serve a global top-k for cacheability and only lightly re-rank per user.
Strict prefix vs typo tolerance
Strict prefix matching is fast and simple. Typo tolerance improves recall for real users but multiplies the search space and cost, so it is usually bounded to a single edit and used only as a fallback when strict matching is thin.
Larger k and longer suggestion list vs tighter latency and payload
Returning more completions and richer metadata helps the user but grows the payload and per-node storage and can slow the response. A small k, typically 5 to 10, keeps payloads tiny and latency low, which matters more on every keystroke.
How Search Autocomplete (Typeahead) actually does it
Production typeahead systems lean heavily on finite state transducers (FSTs) and precomputed suggesters rather than naive tries. Lucene, which powers Elasticsearch and Solr, encodes terms in an FST, a compact automaton that shares both prefixes and suffixes and can associate an output (like a weight) with each accepted string. Elasticsearch's completion suggester builds a dedicated in-memory FST at index time specifically so prefix lookups are fast, and it stores weights so results can be returned in ranked order without scanning. Google's autocomplete, by its own description, predicts queries from real historical searches and trends, applies removal policies for unsafe or sensitive predictions, and varies suggestions by language, location, and freshness, which is consistent with a log-mining plus fast-trend design. The recurring pattern across all of them is the same: pay the ranking and structure-building cost offline over aggregated query logs, serve an immutable compact automaton in memory for O(prefix length) reads, cache the hottest prefixes, and layer a fast path for what is trending now.
Lessons to study before this interview
If any of these topics are fuzzy, the interviewer will catch it. Each lesson is 15 to 60 minutes with diagrams, code, and a quiz.