Design Autocomplete
Design search autocomplete (typeahead) in a 45-minute interview: a trie with top-k per node, prefix tables, the offline aggregation pipeline, trending, caching and a latency budget.
On this page
How to use this page
This page follows the order of a real system design interview. At each step there is a Your turn box: write your own answer first, then open ours and compare. Autocomplete is a lesson in moving work off the request path: the request itself must be almost free, so nearly everything is computed in advance.
| Phase | Time in a 45-min interview | What you produce |
|---|---|---|
| 1. Clarify requirements | 5 min | What is ranked, how fresh, what is filtered |
| 2. Estimate | 5 min | Requests/s, trie size, the latency budget |
| 3. API | 2 min | One cacheable GET |
| 4. Data model | 5 min | Query log, counts, trie snapshot, blocklist |
| 5. High-level design | 10 min | The online path and the offline path |
| 6. Deep dives | 10–15 min | Data structure, top-k, freshness, caching, sharding |
| 7. Wrap up | 2–3 min | Bottlenecks, failures, what you would monitor |
As the user types in a search box, show the top 10 most popular completions for the prefix, updated as trends change (within an hour or so). Filter offensive suggestions. Skip spelling correction, personalisation and the search results themselves.
1. Clarify the requirements
The interviewer says: "Design autocomplete for a search box." Write the questions you would ask, the functional and non-functional requirements with targets, and what you would leave out.
Compare with our answer
The questions that matter most: Ranked by what: global popularity, or personalised? How many suggestions? How quickly must a new trend appear? Do we need spelling correction? Which languages? Then agree the list below.
A strong answer mentions: top 10 completions by popularity · freshness measured in an hour, not seconds · filtering offensive suggestions · a latency target the user feels (under ~100 ms) · failing open when the service is down · personalisation and typo correction out of scope (or a follow-up).
Functional: what it must do
- Suggest completions for a prefix: Top 10, ordered by popularity
- Update with trends: New popular queries appear within ~1 hour
- Filter: Remove offensive or dangerous suggestions
- Works for every keystroke: Including very short prefixes
Out of scope
Spelling correctionPersonalised suggestionsSearch results
Non-functional: how well it must work
| Quality | Target | Why |
|---|---|---|
| Latency | < 100 ms as the user sees it (p99); < 10 ms on the server | Slower than typing feels broken |
| Availability | 99.99% | But failing open (no suggestions) is acceptable |
| Freshness | Hours, not seconds | Popularity changes slowly |
| Scale | ~140 K suggestion requests/s on average, 2–3× at peak |
2. Back-of-the-envelope estimates
Assume 200 M daily users, 10 searches each a day, and 6 suggestion requests per search after debouncing. There are 100 M distinct queries worth keeping, averaging 25 bytes. Work out requests per second and roughly how much memory a structure holding all queries and their top-10 lists needs. Then split a 100 ms budget between the network and the server.
Compare with our answer
- Requests: 200 M × 10 × 6 = 12 B a day ÷ 86,400 ≈ 140 K/s, 300–400 K/s at peak.
- Searches logged: 200 M × 10 = 2 B a day, the input to the offline pipeline.
- Trie: a compressed trie has at most about 2 nodes per query; each node stores 10 query ids plus child pointers, ~75 bytes. 100 M × (25 + 2 × 75) ≈ 18 GB: fits in one server's memory.
- Latency budget: see the table below. The server's share is under 10 ms.
A strong answer mentions: requests/s with a peak factor · a memory size that fits one machine, so replicate rather than shard at first · the logging volume · splitting the latency budget so the server's slice is tiny.
Assumptions: daily active users 200 M; searches per user per day 10; keystrokes per search (after debouncing) 6; distinct queries kept 100 M; average query length (bytes) 25.
| Number | Estimate | Why it matters |
|---|---|---|
| Suggestion requests per second | 139 K / s | ≈ 140,000/s average: serve from memory, close to the user. |
| Searches logged per day | 2 B | Input to the offline popularity pipeline. |
| Trie size (compressed, top-10 ids per node) | 17.5 GB | ≈ 18 GB: fits in one server’s RAM; replicate it, and shard by prefix when it outgrows a machine. |
- Debounce on the client (wait ~100 ms between keystrokes) and cache recent prefixes to cut requests.
- The trie is rebuilt offline and loaded read-only: no locking on the read path.
The numbers say: replicate, don't shard (yet). An 18 GB read-only structure copied to dozens of stateless servers serves 140 K/s easily, since one server walking an in-memory trie handles tens of thousands of lookups a second.
Here is a typical latency budget, measured from the keystroke to the suggestions appearing:
| Step | Time | Notes |
|---|---|---|
| Debounce wait | 0 (not counted) | The browser waits ~100 ms after a keystroke before sending; it's a deliberate pause |
| Network to an edge (CDN) | 10–40 ms round trip | Depends on the user's connection; mobile is worse |
| Edge cache hit | ~1 ms | Popular prefixes stop here |
| Edge → origin on a miss | 10–60 ms | Same continent |
| Suggestion server | 1–5 ms | Walk the trie, return a list |
| Render in the browser | ~5 ms | |
| Total | ~30–100 ms | Leaves almost nothing for the server to waste |
3. API
What does the browser call, and how do you make the response cacheable by a CDN?
Compare with our answer
A strong answer mentions: a single GET with the prefix and locale in the URL (no cookies, no user id), so it can be cached by prefix · a Cache-Control max-age of minutes · a tiny JSON response · normalising the prefix (lowercase, trim) so How and how share a cache entry.
| Call | Request | Response | Notes |
|---|---|---|---|
GET /v1/suggest?q=how%20to%20b&lang=en | – | { suggestions: ["how to boil eggs", …] } | Cacheable for minutes by prefix; tiny response |
Keep the request anonymous and deterministic: the same q and lang always give the same answer for the next few minutes. That is what lets browsers and the CDN cache it. Personalisation, if added later, should be a separate small call merged on the client, so it doesn't destroy the cache hit rate.
4. Data model
What is written on every search, what is computed offline, and what does a suggestion server load into memory?
Compare with our answer
A strong answer mentions: an append-only query log (sampled) · aggregated counts per query and locale with time decay · a versioned trie snapshot in object storage · a blocklist applied at build time · no database on the request path at all.
query log Event stream → data lake
query, ts, locale, region
Every completed search is logged (sampled) for counting.
query counts Batch / streaming aggregation (Spark / Flink)
query, locale → weighted_count
Counts per query over a sliding window, with recent searches weighted more.
trie snapshot Serialised file in object storage
node(prefix) → children, top10[(query, score)]
Built offline, versioned, loaded by every suggestion server.
blocklist Small curated list
pattern, reason
Removes offensive or dangerous suggestions before the trie is built.
The point of this model: the online path reads nothing but memory. The query log and counts live in a data pipeline (Kafka into a data lake, then Spark or Flink), and the only thing that crosses into the serving world is a snapshot: a single file, built and validated offline, that servers download and swap in.
Sampling means logging, say, 1 in 10 searches instead of all of them. Popular queries still show up thousands of times, so the ranking barely changes, and the pipeline is 10× cheaper. The cost: rare queries may never cross the threshold for being suggested, which is usually fine.
5. High-level design
Sketch two halves: the online path from a keystroke to the suggestions, and the offline path from a completed search to a new snapshot on every server.
Compare with our answer
Compare with the figure. The pieces people most often forget: client-side debouncing and caching, the edge cache, and the atomic swap of a new snapshot (servers never edit the live structure).
The online and offline halves, then one keystroke traced through them
- Two halves. The online path is tiny and fast: browser caches, an edge cache, and stateless suggestion servers walking an in-memory trie. The offline path logs searches, aggregates popularity, filters, builds a new trie every hour, and ships it to the servers.
- As the user types, the browser waits a moment between keystrokes and checks its own cache. Then it asks the suggestion service, often answered by an edge cache. The service walks down the in-memory trie to the prefix node, which already stores its top ten, and returns them.
| Component | What it does |
|---|---|
| Client logic | Debounce keystrokes; cache prefixes locally |
| Edge cache | Popular prefixes cached for minutes |
| Suggest service | Stateless; walks the in-memory trie |
| Trie | Each node stores its top-10 completions |
| Query log + aggregator | Counts searches with recency weighting |
| Trie builder | Filters, builds, versions and ships snapshots |
| Blocklist | Removes harmful suggestions |
Trace the online path:
- The user types
how to b. The browser waits ~100 ms for more keystrokes (debouncing), then checks its own cache of recent prefixes. - On a miss, it calls
GET /v1/suggest?q=how%20to%20b&lang=en. The CDN answers if another user asked for this prefix in the last few minutes. - On a CDN miss, a stateless suggestion server walks its in-memory trie to the node for
how to b. - That node already holds its top 10. The server returns them; nothing is sorted at request time.
6. Deep dives
Two or three sentences each: which data structure finds completions for a prefix fast? How do you return the top 10 for "a" without looking at millions of queries? How do new trends appear? What do you do when the structure outgrows one machine?
Compare with our answer
A strong answer mentions:
- A trie (or a prefix → list key-value table), with the comparison between them.
- Top-k precomputed per node offline, trading memory and build time for constant-time reads.
- Hourly rebuilds from time-decayed counts with an atomic swap, plus a small streaming overlay for breaking trends.
- Sharding by locale and by prefix range balanced by traffic, with replicas per shard.
Data structure: a trie, or a prefix table
A trie (prefix tree) stores strings one character per level, so each node is a prefix, and finding the node for how to b takes 8 steps no matter how many queries exist. A radix tree (compressed trie) merges chains of single-child nodes into one node, cutting memory several times.
Walking a trie, and why each node stores its own top k
| Option | How | Good at | Catch |
|---|---|---|---|
SQL LIKE 'how to b%' ORDER BY count LIMIT 10 | Index range scan, then sort by count | Simple; fine for a small site | Sorts every match on every keystroke; short prefixes match millions |
| Trie with top-k per node (chosen) | In-memory tree built offline | Compact (~18 GB here); lookups in microseconds | Custom code; one machine's RAM per shard; rebuilt, not edited |
| Prefix table in a key-value store | Key = every prefix up to ~20 chars, value = its top 10 | Any KV store (Redis, Cassandra, DynamoDB); no custom tree | Many more keys (often ~1 B prefixes, ~100 GB); a network hop per lookup |
The prefix table is a fair alternative and some interviewers prefer it: it's just a precomputed trie flattened into keys. It costs more memory (each prefix stores its own key and list, with nothing shared) and adds a network round trip (0.2–0.5 ms to Redis), but it scales by adding KV nodes and needs no custom server. Either way, the key idea is the same: the top 10 are stored, not computed.
Top-k per node: pay at build time
For the prefix a, millions of queries match. Traversing them and sorting on every request is hopeless. So the builder computes, bottom-up, the top 10 for every node: each node's list is the best 10 from its own query (if it is one) and its children's lists. Requests become "walk to the node, return its list".
Store query ids (4–8 bytes) in each list, not strings, with the strings held once in a separate table; that keeps the lists small. Limit very deep nodes too: few people type 40 characters before picking a suggestion, so many builders stop storing lists below a certain depth.
How the builder computes every list
The build is a batch job (Spark or MapReduce) over the scored queries. For each query, emit one record per prefix: "how to boil eggs" with score 9,100 emits ("h", …), ("ho", …), up to the depth limit. Group by prefix and keep the best 10 per prefix with a small heap (a min-heap of size 10: a new candidate replaces the smallest only if it's larger). With 100 M queries averaging ~20 stored prefix levels, that's ~2 B emitted records, which a cluster processes in minutes. The output is the prefix table directly; the trie builder then serialises it as a compressed tree.
Freshness: the offline pipeline and trending queries
The offline pipeline: log, aggregate, filter, build and swap
- Offline, completed searches flow into a log. An aggregator counts them with recent searches weighted higher. Every hour a builder removes blocked phrases, builds a new trie with the top ten stored at every node, and the servers swap to the new snapshot.
The aggregator scores each query with time decay, so recent searches count more. A common form is an exponential decay with a half-life: a search from 24 hours ago counts half as much as one now (with a 24-hour half-life). Scores are recomputed hourly over the recent window and merged with the decayed long-term totals.
An hourly rebuild means a breaking event ("earthquake in …") takes up to an hour or two to appear. If the requirement is minutes, add a trending overlay: a stream processor (Flink, Kafka Streams) counts queries over the last 5–15 minutes, compares each count with its usual level, and publishes a small list of spiking queries every minute. Suggestion servers merge that small list into the trie's answer at request time. The overlay is tiny (thousands of queries), so merging costs microseconds.
Safety on the fast path
The trending overlay is exactly where abuse and tragedy show up first: coordinated bots pushing a phrase, or offensive completions about a breaking news story. Run the blocklist and a classifier on the overlay as well, require a minimum number of distinct users (not just searches) before a query can trend, and give humans a kill switch that removes a suggestion everywhere within a minute (a small "removed" list that servers check on every response).
Shipping the snapshot to every server
Copying an 18 GB file to a hundred servers (several regions, with peak headroom) every hour is about 1.8 TB of internal traffic an hour, and a bad file on every server at once is an outage. The usual approach:
- Versioned snapshots in object storage (
trie-en-v451), with a manifest pointing at the current version. - Validation before release: size within a few percent of the last build, a fixed set of probe queries returning sensible results, no blocked terms present.
- Staged rollout: a few canary servers load it first; their latency and click-through are compared with the rest before the manifest moves for everyone.
- Memory headroom for the swap: a server holds the old and new versions together for a moment, so it needs about 2× the snapshot size in RAM, or it memory-maps the file (lets the operating system page it in from disk) so loading costs little extra.
- Deltas when the full file gets too large: ship only the changed nodes and apply them to a copy, then swap.
Caching: most requests never reach a server
Caching works at three layers, each cheaper than the next:
| Layer | What it holds | Effect |
|---|---|---|
| Browser | Responses for prefixes typed this session | Backspacing and retyping cost nothing |
| CDN / edge | Popular prefixes, max-age of a few minutes | Short prefixes (a, ho, how) are a large share of traffic and almost always hit |
| Server | The trie itself is in memory | A miss still costs only a few milliseconds |
Two client tricks cut traffic further: debouncing (send only after ~100 ms without a keystroke) and prefetching (the response for how can include the top results for how and how t, the likely next prefixes). Together with caching, these often halve the requests that reach the origin.
Sharding when it outgrows one machine
Add languages and the trie outgrows one server. Shard first by locale (one trie per language or market, which is natural since users rarely mix), then by prefix range within a large locale.
7. Bottlenecks, failures and monitoring
Scaling bottlenecks
| Bottleneck | Fix |
|---|---|
| Request volume | Edge and browser caches; many stateless replicas |
| Trie memory | Compress (radix tree), shard by locale/prefix |
| Hot prefixes (“a”, “how”) | Cached everywhere; trivially cheap with precomputed lists |
| Build time | Distributed aggregation; incremental builds per shard |
When things fail
| Failure | What happens |
|---|---|
| Suggest service down | The search box still works, just without suggestions (fail open) |
| Bad trie build (e.g. offensive entries) | Versioned snapshots; validate before swap; instant rollback |
| Aggregation pipeline delayed | Keep serving the previous trie |
What to monitor
Suggestion latency (p99)Requests per keystrokeCache hit ratioTrie build ageSuggestion click-through rateBlocklist hits
8. Follow-up questions
Answer in order. 1) Product wants personalised suggestions (your own recent searches first). What changes, and what happens to caching? 2) A celebrity dies and people search for them within minutes, but suggestions lag for an hour. Fix it. 3) Legal asks you to remove one suggestion from every server within 5 minutes. How?
Compare with our answer
A strong answer mentions:
- Keep the global, cacheable call unchanged; add a small per-user history call (or keep history in the browser) and merge on the client, so the global response stays cacheable. Server-side personalisation per request would kill the CDN hit rate.
- A streaming trending overlay counting the last few minutes, detecting spikes against a baseline, filtered for safety, merged at request time.
- A small removal list pushed to every server (and CDN purges for the affected prefixes), checked on every response; the next full build drops it permanently.
How would you personalise suggestions?
Blend the global top-k with the user’s own recent searches, stored per user and merged at request time.
How do you handle typos?
Fuzzy matching (edit distance) on a separate index, used when the exact prefix has few results.
How do you support many languages?
One trie per locale; normalise accents and case; route by the user’s locale.
- Numbers: 140 K req/s average (300–400 K peak); 2 B searches logged a day; trie ~18 GB for 100 M queries.
- Latency budget: ~100 ms user-visible; server gets < 10 ms; edge cache answers popular prefixes.
- Structure: trie (radix-compressed) in memory, or a prefix → top-10 table in a KV store.
- Top-k per node, computed bottom-up offline; store query ids, not strings.
- Offline pipeline: sampled log → decayed counts → blocklist → build → validate → atomic snapshot swap.
- Trending overlay: streaming counts over minutes, merged at request time, with safety filters.
- Caching: browser + CDN (minutes) + debouncing (~100 ms) + prefetching next prefixes.
- Sharding: locale first, then prefix ranges balanced by traffic; replicate hot shards.
- Fail open: no suggestions is acceptable; no search box is not.
1. Your suggestion service stores counts in Postgres and answers WHERE query LIKE 'a%' ORDER BY count DESC LIMIT 10. Why does it struggle at 140 K requests a second?
A prefix LIKE can use an index to find the range, but ranking that range by popularity on every keystroke is the expensive part. Precomputing the top 10 per prefix removes it.
2. Why does each trie node store its own top 10 rather than computing it from its subtree?
Precomputing top-k trades memory and build time for constant work per request. It makes in-place updates harder, not easier.
3. A teammate proposes incrementing counts in the live trie on every search so suggestions are always current. What is the main problem?
One count change ripples up to every ancestor's top-k list, and short prefixes are the hottest nodes. Offline rebuilds plus an atomic swap keep reads lock-free.
4. Product adds "your recent searches first" by reading the user's cookie in the suggestion service. What is the biggest side effect?
A per-user response can't be shared. Keep the global call anonymous and cacheable, and merge personal history on the client from a separate small call.
5. Suggestions must reflect a breaking news event within 10 minutes, but the trie is rebuilt hourly. What is the most practical fix?
Full rebuilds over billions of logged searches take time and risk bad snapshots. A small overlay from a stream processor gives minutes-level freshness cheaply.
6. You split the English trie into four shards: a–f, g–m, n–s, t–z. What goes wrong?
Letters are not equally popular. Set boundaries by measured traffic and replicate hot shards; each prefix still maps to exactly one shard.
7. The suggestion cluster goes down during a deploy. What should users see?
Autocomplete is a helper. Failing open keeps search working, which is the product that matters.
Score 60% or more and the lesson is marked complete.