Design search autocomplete (typeahead): the system design interview walkthrough
The request to design search autocomplete sounds like one line — as the user types, suggest completions — and that one line hides the whole interview. Doing it for a small dictionary is trivial; doing it in under a hundred milliseconds on every keystroke, for billions of queries a day, ranked by how popular each completion is, is a read-latency and precomputation problem with a dozen sharp edges. This is one of the most common typeahead system design prompts because it forces the read-heavy muscles at once: a data structure tuned for prefixes, precomputed ranking, an offline pipeline, and sharding under enormous read QPS.
The round turns on two decisions. First, the shape of the lookup: autocomplete is overwhelmingly read-heavy, so you reach for a trie (a prefix tree) and then make the leap most candidates miss — you precompute the top-k completions at every node so a lookup is O(prefix length), not a scan of everything under the prefix. Second, where the popularity numbers come from, which is where the offline query-log aggregation pipeline comes in — the read path never touches raw logs. This walkthrough follows the path a strong candidate draws on the whiteboard — requirements, estimate, API and data model, high-level design, then the deep dives — and at each step it names the follow-up the interviewer uses to tell a memorised answer from an engineer who understands the tradeoff.
How the search autocomplete round is actually run
A search autocomplete round runs about 60 minutes on a shared canvas — you draw the boxes and arrows while you talk, and the interviewer interrupts. It is a favourite because the one-line problem opens onto deep water fast: the moment you say "look up the prefix," the question becomes how, in tens of milliseconds, ranked, at this scale — and every answer after that (precompute, aggregate, shard) compounds. Get the read spine clean and you have shown the whole loop in one problem.
The interviewer rarely lets "store the queries and search them" stand. "Every keystroke the user makes is a request to your service — how do you answer in under a hundred milliseconds, ranked by popularity, at billions of queries a day?" That question — serving ranked prefix matches fast at huge read QPS — is the one a copied answer can never rehearse, and the one this round is really testing.
The rounds here are modelled on how the loop runs, not scraped from any candidate's recall. What matters for prep is the shape: a blank canvas, a clock, and a follow-up after every decision you make.
The five-step framework for any HLD round
Every high-level design answer fits the same spine. Say it out loud at the start so the interviewer knows you have a plan, then walk it:
- Clarify requirements — functional and non-functional, and what you are explicitly not building.
- Estimate — queries per day, keystrokes per search, and the resulting read QPS, to justify every later choice.
- High-level design — the boxes and arrows: client, autocomplete service, trie servers, cache, and the offline pipeline.
- Deep dive — the two or three decisions that actually decide this system.
- Follow-ups — bottlenecks, failure modes, and what you would change at ten times the scale.
What the debrief measures
The score is not "right or wrong design." A good HLD debrief reads on four dimensions, and every move below maps to one: problem solving (did you reach a trie with precomputed top-k, fed by an offline pipeline, served from shards behind a cache), communication (did you say why you precompute top-k instead of ranking at query time in a sentence), technical execution (per-node top-k, batch aggregation, prefix sharding, hot-swap of rebuilt tries), and time management (did you spend your 60 minutes on the read path and the pipeline, not on the client's debounce logic). Reading a walkthrough teaches the design; it does not teach you to deliver it on the clock while someone pushes back.
Step 1 — Requirements: what a search autocomplete must do
Spend the first few minutes here. Jumping to boxes before you have scoped the problem is the fastest way to design the wrong system.
| Type | Requirement |
|---|---|
| Functional | Given a prefix, return the top-k most relevant completions (k is small, ~5–10); completions are ranked by popularity; the ranking updates as query popularity shifts over time. |
| Functional (optional) | Personalised suggestions, spell-correction / fuzzy matching, multi-language, trending terms — call these out, then scope most of them for later. |
| Non-functional | Very low latency (p99 under ~100 ms — it fires on every keystroke); extremely read-heavy (reads vastly outnumber updates); suggestions can be a little stale (hours is fine); highly available; scales to billions of searches a day. |
The sentence that earns points: "Autocomplete is read-heavy and latency-critical, and the suggestions are allowed to be stale, so the core of the design is a precomputed structure we read in tens of milliseconds — building it from query counts is an offline job, not part of the request." Say that and you have framed the entire design before drawing a box.
Step 2 — Capacity estimation (back of the envelope)
Estimation here is about proving one thing: the hard axis is read QPS on the lookup, not the write path.
| Quantity | Assumption | Result |
|---|---|---|
| Searches | ~5B/day | ~60K searches/sec average |
| Keystrokes per search | ~4 prefix requests (one per character, debounced) | ~240K autocomplete reads/sec, far higher at peak |
| Reads vs writes | every keystroke reads; counts update offline | read QPS ≫ update QPS — reads dominate by orders of magnitude |
| Distinct queries to index | ~top few hundred million popular queries | fits a sharded in-memory trie, not one host |
Two conclusions fall out, and you should say both out loud. First, serving the reads is the system — hundreds of thousands of prefix lookups a second, each needing an answer in tens of milliseconds, means the design is dominated by a read-optimised, in-memory, precomputed structure fronted by a cache, not by write throughput. Second, because suggestions may be stale for hours, collecting and ranking the counts is a batch job you run offline and push to the serving tier — nothing on the hot path touches a raw query log. You have now pointed the interview at the real deep dive — the trie and its precomputed top-k — before anyone asked.
Step 3 — API and data model
The API is tiny. The read path is a single call; everything that feeds ranking happens offline, not through a user-facing write endpoint.
| Channel | Operations |
|---|---|
| Read (hot path) |
suggest(prefix, k=10) → returns the ranked top-k completions for that prefix. Fires on each debounced keystroke. |
| Ingest (offline) | every executed search is logged (query, timestamp, optional user/locale); the log is the only "write", and it is consumed by the batch pipeline, never by suggest. |
The data model splits in two — what the hot path reads, and what the pipeline builds it from:
| Entity | Notes |
|---|---|
trie node |
one character of a prefix; stores child pointers and a precomputed top-k list of (completion, weight) for the prefix ending at this node. |
query count |
query → aggregated weight (frequency over a recent window); the output of the aggregation job, the input to the trie builder. |
query log |
append-only (query, ts, …) events; raw material for aggregation, never read on the hot path. |
Step 4 — High-level design: the read-optimised trie architecture
Now the boxes. The system has two halves that meet only at a handoff: a read path that serves suggestions, and an offline pipeline that builds what the read path serves.
- Client: debounces keystrokes (waits a few tens of ms between characters) so you are not firing a request on every single key, and caches recent prefixes locally.
-
Autocomplete service (stateless): receives
suggest(prefix), checks the cache, and on a miss asks the right trie server. - Trie servers (sharded by prefix): hold the in-memory trie with precomputed top-k per node; a lookup walks the prefix and returns the node's top-k. Replicated for read QPS.
- Cache: fronts the trie servers — popular prefixes (the short, common ones) are served straight from cache so most reads never hit a trie server at all.
- Offline pipeline: query logs → aggregator (batch/stream) → trie builder → push the rebuilt trie to the serving tier, periodically.
Say explicitly that the two halves are decoupled: the read path never touches a raw log, and the pipeline never blocks a lookup. That separation — a fast, precomputed read tier and a slow, batch build tier — is the single most important structural insight of the whole design, and naming it unprompted is a signal the interviewer is listening for.
Deep dive: the trie with precomputed top-k per node
This is the first decision that actually decides the round. Given a prefix, how do you return the ranked top-k completions in tens of milliseconds?
| Approach | How it works | The catch |
|---|---|---|
| Scan a query table | On each keystroke, SELECT … WHERE query LIKE 'pre%' ORDER BY count DESC LIMIT k. |
A range scan plus a sort per keystroke — far too slow at this QPS, and it hammers the database. |
| Plain trie, rank at query time | Walk the prefix, then gather all completions under that node and sort them by weight. | A popular prefix like "a" has millions of descendants — gathering and sorting them per request blows the latency budget. |
| Trie with precomputed top-k per node | Each node stores the already-ranked top-k completions for its prefix; a lookup walks the prefix (O(length)) and returns the stored list. | The right fit — reads are tiny and constant-ish; cost is memory and a build step that computes the lists offline. |
Pick the trie with precomputed top-k and say why in one line: autocomplete reads vastly outnumber updates and must be fast, so you pay the ranking cost once at build time and store the answer at each node, turning every lookup into a short walk plus a read instead of a scan-and-sort.
The leap is precompute, don't rank at query time. During the build, you roll the top-k up the tree: a node's top-k is computed from its children's completions and their weights, so by the time serving starts, the answer for every prefix is already sitting at the node. A lookup is then O(prefix length) — walk the characters, read the list, done — with no scan of the subtree and no sort on the hot path.
"A user types the single letter 'a' — millions of queries start with it. How do you not scan them on every keystroke?" You don't scan: the top-k for prefix "a" was computed once at build time and stored on the "a" node, so the lookup is a one-node read. Precomputing the per-node top-k is the senior move.
System Design
HLD · Search & discovery · 60 min
Design search autocomplete out loud, with follow-ups
Deep dive: the data collection and aggregation pipeline (offline)
This is the decision most candidates under-think. The trie is only as good as the weights in it — so where do the popularity numbers come from, and how do they change over time without touching the read path?
The key move is that collecting counts is an offline pipeline, entirely off the hot path. One message to a search box never updates the trie directly; instead the counts are aggregated in the background and the trie is rebuilt periodically:
-
Log every executed search — each real search appends a
(query, timestamp, …)event to a log (a stream like Kafka, or batched files). This is the only "write" in the system. -
Aggregate the counts — a batch or streaming job (classically MapReduce, or a stream aggregator) rolls the raw events into
query → weightover a recent window, so popularity reflects what people search now, with old queries decaying. - Build the trie — a builder takes the aggregated weights and constructs a fresh trie, computing the top-k at every node during the build (rolling children up to parents).
- Publish to the serving tier — the rebuilt trie (or the changed shards) is pushed to the trie servers, which swap it in. Reads continue against the current trie until the new one is live.
Because the whole loop runs on a schedule (hourly, say), the suggestions are stale-but-fast — exactly the tradeoff the requirements allowed. Nothing on the read path waits for aggregation, and the aggregation never slows a lookup.
"The popularity of queries changes constantly — do you update the trie on every search?" No. You batch-aggregate the counts offline and rebuild the trie periodically; reads stay fast and a little stale, which the requirements permit. Updating per query would put a write on the hot path and destroy the read latency.
System Design
HLD · Offline aggregation · 60 min
Defend the offline rebuild pipeline out loud
Deep dive: serving, sharding and scale
Groups of popular prefixes and a trie too large for one host change the shape of the problem. The read QPS is enormous and the trie does not fit on a single machine — so how do you serve it without downtime?
| Concern | The move |
|---|---|
| Read QPS | Front the trie servers with a cache. Short, popular prefixes dominate traffic, so a cache of hot prefixes absorbs most reads before they reach a trie server; replicate the trie servers so the remaining reads spread across replicas. |
| Trie too big for one host | Shard the trie by prefix — e.g. route prefixes by their first letter(s) to different servers, so each host holds a slice of the tree. The autocomplete service maps a prefix to its shard. |
| Hot shards | Some prefixes (common first letters) are far hotter than others; give hot shards more replicas, or split them further, so load is balanced rather than even by key range. |
| Updating without downtime | The pipeline builds a new trie out of band; you hot-swap it in — load the rebuilt shard alongside the old one and flip the pointer — so reads never stop while the trie is refreshed. |
Say the sharding key out loud: you shard by prefix, not by hashing whole queries, because a lookup is a prefix walk — all completions for "net…" must live together, so routing by the leading characters keeps a single lookup on a single shard. Then repeat the real scaling axis: the pressure is the sheer volume of prefix reads, which is why the cache, the replicas, and the in-memory sharded trie — not the log store or the pipeline — are where this system lives or dies.
"The trie is too big to fit on one machine — now what?" Shard it by prefix so each server owns a slice of the tree; the autocomplete service routes a prefix to its shard, you replicate each shard for read QPS, and give hot prefixes extra replicas. A lookup still touches exactly one shard.
The follow-ups that decide the search autocomplete round
Scan the probes from each deep dive and they rhyme. Master these five and you are ready for a version of the question that is not drawn exactly like this one.
- "Why a trie, and why precompute the top-k?" → Reads vastly outnumber updates and must be fast; a plain scan or a rank-at-query-time trie sorts huge subtrees per keystroke, so you pay the ranking cost once at build time and store top-k per node. (communication)
- "A user types 'a' — how do you not scan millions of queries?" → The top-k for "a" is already stored on that node from the build, so the lookup is a one-node read, not a subtree scan. (problem solving)
- "Popularity changes constantly — do you update on every query?" → No; batch-aggregate counts offline and rebuild the trie periodically; reads stay fast and a little stale, which the requirements allow. (technical execution)
-
"Where do the weights come from?" → Log every executed search, aggregate
query → weightover a recent window (MapReduce / stream), build the trie from those weights, push it to the servers. (technical execution) - "The trie doesn't fit on one host — now what?" → Shard by prefix, replicate each shard for QPS, cache hot prefixes, and hot-swap rebuilt tries so reads never stop. (problem solving)
Each maps to a debrief dimension. Reading this list teaches you the answers; it does not teach you to deliver them while someone interrupts — that only comes from saying them out loud.
How to prepare: a one-week plan
You do not need fifty systems. You need this one cold and the framework automatic, so the next "design X" is just new nouns in the same five steps.
- Days 1–2: Learn the five-step framework until it is reflex. Do search autocomplete end to end on paper — requirements, estimate, API, data model, the two-halves boxes.
- Days 3–4: Drill the trie deep dive: scan vs rank-at-query-time vs precomputed top-k, O(prefix length) lookups, rolling top-k up the tree at build. Say each tradeoff in one sentence.
- Days 5–6: Own the pipeline and scale — query-log aggregation, periodic rebuild, prefix sharding, caching hot prefixes, hot-swapping tries. Answer each of the five follow-ups out loud.
- Day 7: A full timed 60-minute round, narrating the whole way, with someone (or something) interrupting. This is the rep that counts.
This post is the deep walkthrough behind one row of the broader Top 25 system design interview questions — once search autocomplete is automatic, the same spine carries the rest of the list.
Frequently asked questions
How do I design search autocomplete step by step?
Follow the five-step HLD framework. Clarify requirements (given a prefix, return the top-k most popular completions, fast, updated as popularity shifts; staleness of hours is fine); estimate to show the hard axis is read QPS on the lookup, not the write path; define the tiny suggest(prefix, k) read API plus offline query logging, with a trie-node and query-count data model; draw the two halves (client debounce → autocomplete service → cache → prefix-sharded trie servers, plus an offline query-log → aggregator → trie-builder pipeline); then deep-dive the decisions that matter — the trie with precomputed top-k, the aggregation pipeline, and sharding at scale. Finish on the follow-ups about staleness and hot prefixes.
Why use a trie for autocomplete instead of a database query?
Because a database range scan plus a sort runs on every keystroke, and that is far too slow at hundreds of thousands of reads a second. A trie (prefix tree) turns a prefix lookup into a short walk down the characters, which is O(prefix length) rather than a scan of a big table. When you also store the precomputed top-k completions at each node, the walk ends in a single read of an already-ranked list — no sorting on the hot path. The cost is holding the trie in memory and building it offline, which the read-heavy, staleness-tolerant workload makes a good trade.
Why precompute the top-k at each trie node instead of ranking at query time?
Because ranking at query time means gathering every completion under the prefix and sorting it per request. For a popular prefix like a single letter, that subtree has millions of entries, so sorting it on every keystroke blows the latency budget. Precomputing rolls the top-k up the tree once during the build, so each node already holds its ranked list; a lookup just reads it. You pay the ranking cost once, offline, instead of on every one of billions of reads.
How does the autocomplete system stay up to date as query popularity changes?
Through an offline pipeline, not live writes. Every executed search is logged, and a batch or streaming job aggregates those events into query → weight over a recent window so popularity reflects current behaviour. A builder then constructs a fresh trie with recomputed top-k and pushes it to the serving tier periodically — hourly, say. Reads keep serving the current trie and are allowed to be stale for a while, which is exactly the tradeoff the requirements permit; nothing on the hot path waits for aggregation.
How do you scale an autocomplete trie that is too big for one machine?
You shard the trie by prefix and replicate each shard. Routing prefixes by their leading characters sends each lookup to the one server that holds that slice of the tree, so a single lookup touches a single shard. Each shard is replicated to absorb read QPS, hot prefixes (common first letters) get extra replicas, and a cache in front serves the most popular short prefixes before they reach a server. Rebuilt tries are hot-swapped in shard by shard, so refreshing the data never stops reads.
How do I practise a system design interview out loud?
Reading a walkthrough is not the same as defending a design while someone interrupts. On Zynter, the HLD track runs live voice rounds modelled on how real system design loops run — you talk through a shared design on the canvas, and a voice interviewer pushes with the follow-ups above one at a time, then gives you a debrief on problem solving, communication, technical execution, and time management. The score is a practice signal, not a hiring decision.
Practise it on Zynter
You can read the whole design. The round is won on the precompute and the sharding.
Pick the Search Autocomplete round, draw the two-halves design on the canvas, and defend it out loud to a voice interviewer that keeps asking "how do you answer in under a hundred milliseconds?" and "the trie doesn't fit on one host — now what?" — then read the debrief. Zynter.ai is on-demand mock interviews modelled on real company loops, with 150+ rounds across 20 companies including the HLD system design track (Sep 2026).
Practise the Search Autocomplete round →
Browse all interview tracks
Top comments (1)
One small API contract question: suggest accepts k, but each node stores a fixed top-k list. What happens when a caller requests 50 suggestions and the index only retains 10? I'd use that as practice variation on prachub platform like cap the request, rebuild with a larger maximum, or explain the slower fallback and its latency cost.