Autocomplete (typeahead) shows suggestions as you type, like Google guessing "pizza near me" after you type "piz". It's a favorite interview question because it's small enough to fully design in 45 minutes, yet it touches a real data structure (the trie), a ranking problem, and a hard latency limit: it fires on almost every keystroke, so it has to be fast.

Requirements

Functional requirements

• As a user types a prefix, return the top-K most relevant completions.
• Suggestions reflect how popular a query has actually been.
• Suggestions update as new searches come in; they aren't frozen forever.

Non-functional requirements

• Latency under 100ms per keystroke, ideally under 50ms. This is a hard UX limit, not a nice-to-have.
• Very high read volume, since it fires on nearly every keystroke of every active user.
• Freshness: a trending query should surface within minutes to hours, not wait for a full daily rebuild.
• Availability over strict consistency: a slightly stale suggestion list beats a slow or failed one.

Remember: autocomplete has to be fast enough that the user never notices it's a network call at all. That single constraint is what rules out "just query the database" as an answer.

Estimates

Assume a search product with 500 million searches a day, and each typed query averages about 20 characters, meaning roughly 20 potential autocomplete requests per search.

• Raw keystroke events: 500M × 20 = 10 billion/day, about 116,000/sec average. Client-side debouncing, only firing after a short pause or every few characters, cuts this 5-10x in practice, still tens of thousands of requests per second.
• Unique query space: assume 100 million unique query strings, about 20 bytes each, 2 GB of raw text. Small enough to fit an entire trie, or a precomputed top-K table, in memory.
• Update volume: roughly 500M query events a day need to feed back into rankings, but this can be batched (hourly, say) rather than applied instantly.

The number that matters most: query volume is enormous, but the unique query space is small enough to precompute and hold entirely in memory. That gap between "huge traffic" and "small unique data" is what makes this design possible.

API

That's essentially the whole external contract. Every bit of complexity lives in how the backend serves this fast and keeps it fresh, which is what the rest of this lesson covers.

Data model

The serving structure is a trie: a tree where each node represents one character, so walking from the root spells out a prefix. Picture climbing a tree letter by letter, "p" then "i" then "z", and each branch you take narrows down to fewer and fewer matching words. Each node also caches its own top-K most frequent completions, so a lookup never has to explore the rest of the tree below it.

The trie is rebuilt from a source-of-truth table that tracks how often each query has actually been searched:

High-level design

Search activity feeds a batch job that periodically recomputes frequency counts, a separate job builds a fresh trie snapshot from those counts, and that snapshot gets pushed out to the servers actually answering requests. The path a user's keystroke takes is short and entirely in-memory: hit the API, route to the shard that owns this prefix, return the cached top-K.

Deep dives

Why does every trie node precompute its own top-K, instead of ranking at query time?

This is the single most important decision in the whole design. A naive trie lookup walks down to the prefix's node, then explores the entire subtree below it to collect and rank every possible completion. For a short, common prefix like "a" or "th", that subtree can hold millions of words, and ranking all of them at request time blows straight through your latency budget.

The fix: do that ranking once, offline, while building the trie, and cache the answer directly on the node. A query then costs O(prefix length) to walk down to the right node, plus O(1) to return the cached list. No live ranking, no subtree walk, on the request path at all.

Remember: precomputing the top-K per node is what turns "rank millions of completions" into "look up a cached answer." Do the expensive work once, offline, not on every keystroke.

How do you rank completions, and keep them fresh without rebuilding everything?

The simplest ranking signal is raw historical frequency. A better one decays frequency over time (score = count * decay(time_since_last_seen)), so a query that was popular a year ago fades out while genuinely trending queries rise quickly. Personalization, boosting a user's own recent searches, is applied as a thin re-ranking step on top of the shared global top-K, not baked into the trie itself, which keeps the trie shareable across every user.

Freshness is solved with two tiers, not one. The main trie snapshot rebuilds on a slower, predictable cadence, say hourly, from batched aggregated counts: cheap and consistent, but not instant. For anything spiking faster than that, like breaking news, maintain a small, separately-updated "hot" structure, a bounded count-min sketch or a simple hash map of trending terms updated in near real time, and merge it into the response at query time as an overlay on top of the trie's cached top-K. This avoids rebuilding a multi-gigabyte trie every time one query spikes, while still surfacing genuinely fast-moving trends within minutes.

How does one server hold a query space that doesn't fit in memory?

The trie needs to live entirely in RAM to hit the latency target, which means it's memory-bound, not disk-bound. Once the full query space is too big for one machine, shard the trie by the first character or two of the prefix, so different servers each hold only a slice of the structure. A request for "piz" routes to whichever shard owns prefixes starting with "p" (or "pi"), and that one shard fully answers it without needing data from anywhere else. Replicate each shard for availability and extra read throughput. When it's time to rebuild, build the new snapshot on a separate builder node and hot-swap it into the serving nodes, the in-memory equivalent of a blue/green deploy, so there's no downtime and no query pays a rebuild cost.

Very short prefixes ("a", "th") are both the highest-traffic case and the least useful one, since the results are too broad to be helpful. Many products simply don't fire autocomplete until the user has typed at least two characters, which also cuts a meaningful amount of load.

Trade-offs and follow-up questions

Q: How do you keep the trie fresh without rebuilding it constantly? A: A two-tier approach: a periodic full rebuild (hourly, say) from batched frequency aggregation covers the stable long tail cheaply, plus a lightweight, frequently-updated trending overlay covers anything spiking faster than that cadence. The API merges both at response time.

Q: The trie for the full query space doesn't fit on one machine. What do you do? A: Shard by prefix, first character or first two characters, so each serving node holds only a fraction of the trie. A thin routing layer sends each request to the one shard that can fully answer it.

Q: How would you personalize suggestions per user without breaking the shared trie's precomputation? A: Keep the shared trie's top-K global and un-personalized, since that's what makes the precomputation cheap and reusable across every user. Apply personalization afterward, as a thin re-ranking step that boosts items from a small, per-user cache of recent searches.