Design Search Autocomplete (Typeahead): System Design Interview Walkthrough

If you remember five things

The whole answer in one glance. Everything below is the defense of these five calls.

Precompute top K on every node. Store the best K completions on each trie node at build time, so a lookup is a short prefix walk plus one array read, never a subtree scan of millions of leaves.
Two decoupled halves. A boring fast read path that only reads a handed-over structure, and a smart offline data path that recomputes rankings. A broken ranking job can never take down the search box.
The dataset fits in RAM. Tens of GB of distinct queries, not tens of TB. That one number turns this from a sharded disk database into an in-memory lookup you replicate.
Layered defenses before the trie. Client debounce, a Redis prefix cache, and an in-process LRU for the hottest prefixes mean most requests never touch the trie, and hot keys spread across replicas.
Trade freshness for speed on purpose. Rankings are eventually consistent, rebuilt from a Kafka stream and swapped in atomically behind a pointer. Nobody notices a 3-minute stale suggestion. Everybody feels 300ms of lag.

1Clarifying the requirements#

Pin down what we are shipping before drawing a single box. "Autocomplete" means five different products to five different people, and picking the wrong one quietly wastes the whole interview.

Candidate: Are we completing search queries, like a web search box, or are we completing entities, like users or products?

Interviewer: Search queries. Think of the main search bar on a large site. You type a prefix, we suggest full queries.

Candidate: Do the suggestions need to be personalized per user, or is a single global ranking fine for v1?

Interviewer: Start global. Mention personalization as an extension if you have time.

Candidate: How fresh do suggestions need to be? If a topic blows up right now, do we need it in the dropdown in seconds, or is next-day fine?

Interviewer: Near real-time would be nice, but you can relax it. Tell me the trade-off you are making.

Candidate: Last one. Do we return 10 suggestions? And do we match only on prefix, or also mid-word and typos?

Interviewer: Top 5 to 10. Prefix match is the baseline. Typo tolerance is a bonus, not required.

What those answers just told me:

The interview is about latency, caching, and freshness, not CRUD on queries.
I am cutting entity completion, strong consistency, and typo handling from v1, and I will say so out loud so the interviewer knows those are choices, not oversights.
"Relax freshness, tell me the trade-off" is the interviewer handing me the thesis: speed beats freshness here.

Functional requirements

Given a prefix string, return the top K (5 to 10) most relevant completed queries.
Rank suggestions by popularity: how often people actually search that full query.
Update rankings as real search traffic comes in, ideally within minutes.
Match on prefix, case-insensitive, after basic normalization (trim, lowercase, collapse spaces).

Non-functional requirements

Latency: p99 under 100ms end to end, because this fires on every keystroke. This is the requirement that dominates every decision below.
Availability: very high. If autocomplete is down, the box should still let you search. It degrades, it does not break.
Scale: read-heavy. Many keystroke requests per actual search.
Eventual consistency on rankings is fine. Nobody notices if a suggestion is 3 minutes stale. People notice 300ms of lag.

From the interviewer's chair

This opening is scored before you draw a single box. I am listening for whether you name the latency budget as the thing that drives everything, and whether you cut scope out loud. Start describing a fuzzy-match engine and personalization for v1 and I have quietly downgraded you. Name the hard part (sub-100ms on every keystroke) first, then go spend your time there.

2Back-of-the-envelope estimation#

Get the scale honest so the choices are grounded. One number falls out of this and decides the entire architecture. I will flag it when I reach it.

The point of this section

You are not here to compute bytes to three decimals. You are here to surface one load-bearing fact: the serving dataset fits in RAM. That single realization turns this from a disk-backed sharded database into an in-memory lookup you replicate. Find it fast, then move on.

Users and read traffic.

400M daily active users, each doing about 4 searches a day: 1.6B searches/day.
1.6e9 / 86,400 is about 18,500 searches/second, call it 20K searches/second.
Autocomplete fires on keystrokes, not searches. With debounce, say 4 requests per search.
20K x 4 is about 80K requests/second average, peak spikier, plan 3x: ~240K requests/second.

Writes are cheap and off the hot path.

The only "writes" are logging what people searched so we can re-rank.
Those batch into a stream. They never touch the serving latency budget.

The number that drives the design: dataset size.

Billions of searches collapse into far fewer distinct queries. Keep the top 100M distinct queries.
Each is about 20 bytes of text plus a score and metadata, call it 60 bytes.
100M x 60 bytes is about 6 GB of raw text and scores.
The trie built over it is 5x to 10x that with pointers and node overhead, so tens of GB.

tens of GB

The number that reorganizes the designThe serving dataset fits in RAM, not on disk. Once I know that, I am no longer designing a sharded disk database with careful index access. I am designing an in-memory lookup that I replicate. Single-digit-millisecond lookups are only possible because the data never leaves memory. Remember this one.

Bandwidth out (not the scary part).

Each response is about 10 suggestions x 30 bytes plus JSON, call it 1 KB.
80K req/s x 1 KB is about 80 MB/s outbound. Fine.
The scary part is latency per request, not raw bytes.

3Core APIs#

Keep the read path to one endpoint, dead simple. Clean APIs are a feature.

GET /v1/suggest?q=how+to+ma&limit=10&lang=en

{
  "prefix": "how to ma",
  "suggestions": [
    { "text": "how to make pizza", "score": 98213 },
    { "text": "how to marinate chicken", "score": 71004 },
    { "text": "how to manage stress", "score": 65590 }
  ],
  "cached": true,
  "took_ms": 7
}

Choices worth defending in that shape:

It is a GET so edge caches and CDNs can cache it by URL.
The normalized prefix is echoed back so the client discards a response that arrived late and no longer matches what the user typed, which matters once we debounce and cancel.
lang is first-class because we build one trie per language.
took_ms and cached are there so I can watch hit rates and tail latency in production instead of guessing.

The write side is not a user-facing API. It is an ingest event fired after a real search completes:

{
  "event": "query_executed",
  "query": "how to make pizza",
  "ts": 1793050000,
  "lang": "en",
  "country": "US"
}

Those events stream into a pipeline that recomputes scores.
The client never calls a write endpoint for autocomplete.
That separation is the first thing I want the interviewer to see: reads and writes are two different systems with two different latency budgets.

4High-level design#

The point of this section

The box diagram is table stakes. What earns points is the single seam: two decoupled halves with a trie handed from one to the other. The read path never writes. A bug in the ranking job can leave yesterday's trie serving, which is a perfectly fine failure mode, but it can never break the search box. Draw the boxes fast, then defend that seam.

Two halves: a serving path that is read-only and fast, and a data path that is offline-ish and recomputes what to serve.

flowchart LR U[Client] --> G[API Gateway] G --> S[Suggest Service] S --> C[(Redis Prefix Cache)] S --> T[Trie Nodes In Memory] L[Search Logs] --> K[Kafka] K --> A[Aggregation Job] A --> R[(Ranked Query Store)] R --> B[Trie Builder] B --> T

The whole system at a glance. The seam that matters is the handoff: the Trie Builder compiles a structure that the Suggest Service only ever reads. The read path and the ranking logic never share a process.

Serving path.

The client sends a prefix.
The gateway handles TLS, rate limiting, and auth.
The Suggest Service checks the Redis prefix cache first; a hit returns immediately.
On a miss it walks the in-memory trie, grabs the top K for that prefix, writes the result back to cache, and returns.

Data path.

Every executed search is logged and streamed through Kafka.
An aggregation job counts query frequencies over rolling windows and produces a ranked list of queries with scores.
A builder compiles that list into a fresh trie.
We ship the new trie to the serving fleet and swap it in. The serving boxes never do writes.

Why two halves.

The read path needs to be boring and fast; the ranking logic needs to be smart and can afford to be slow.
Mixing them gets you a system that is neither fast nor smart.
Keeping them apart means a bug in the ranking job can never take down the search box: the worst a broken data path does is leave yesterday's trie serving.

5Data model#

Use a few stores, each picked for its access pattern. The aggregation output is the source of truth for what gets indexed.

Ranked query store (aggregation output, what the builder compiles):

Field	Type	Notes
query_norm	string	Normalized query text, the key. Lowercased, trimmed.
query_display	string	Original casing to show the user.
score	bigint	Popularity score. Weighted count over a time window.
lang	string	Language bucket, so we build per-language tries.
country	string	Optional, for regional ranking.
updated_at	timestamp	When this score was last recomputed.

Raw event log (before aggregation, high volume, append-only, short retention):

Field	Type	Notes
query	string	The exact query the user ran.
ts	bigint	Epoch seconds. Used for time-decay weighting.
lang	string	Detected or client-supplied language.
country	string	For regional slices.

Serving structure (not a database table, an in-memory trie). Each node conceptually:

Field	Type	Notes
char	char	The character this edge represents.
children	map	Child nodes keyed by next char.
top_k	list	Precomputed top K completions under this node.

That top_k list on each node is the trick that makes lookups O(length of prefix) instead of a subtree scan.
It is the signature hard part of this design, so I will come back to it.

6Deep dives#

6.1 The lookup: precompute top K at each node#

This is the heart of the problem, so I spend real time here. The naive trie walk does not survive the latency budget.

Naive: follow the prefix to its node, traverse the whole subtree to collect every completion, sort by score, take the top 10.
For a prefix like "a" that subtree is tens of millions of leaves.
At roughly 100 nanoseconds per node that is seconds of work against a 100ms budget. It misses by orders of magnitude.

So at build time, precompute and store the top K completions directly on every node.

A request for "how to ma" walks 9 edges and reads a ready-made list off the final node.
No subtree scan at serve time: 9 pointer hops plus one array read, well under a millisecond.
The cost moves to the offline builder, which is exactly where expensive work should live.

How the builder fills top_k efficiently (bottom-up).

A leaf's top_k is just itself.
An internal node's top_k is the merge of its children's top_k lists plus any completion ending at this node, keeping the highest K by score.
Each child already carries only K entries, so merging a node with C children is merging C sorted lists of length K: cheap.
The whole trie builds in roughly one linear pass; no node ever sees more than C times K candidates.

sequenceDiagram participant U as Client participant S as Suggest Service participant C as Redis Cache participant T as Trie U->>S: GET suggest q how to ma S->>C: GET prefix how to ma C-->>S: miss S->>T: walk to node for prefix T-->>S: node top_k list S->>C: SET prefix with TTL S-->>U: top 10 suggestions

A single lookup. On a cache miss the service walks the prefix to its node, reads the precomputed top_k off that node, writes it back to the prefix cache, and returns. No subtree scan anywhere on the serve path.

Pause before you read on: storing 10 completions on every node multiplies memory. If the fleet runs tight on RAM, what do you give up, and what do you keep?

Reveal the answer

You keep the O(prefix length) lookup for the hot shallow prefixes and trade memory only where it is cheap. Two levers: (1) only store top_k on nodes above a depth threshold or whose subtree is large, and fall back to a bounded scan on the rare deep-and-sparse nodes where the subtree is tiny anyway; (2) store offsets into a shared string pool instead of copying query text onto every node, so the 10 entries become 10 small integers, not 10 full strings. The second one alone usually buys back most of the memory.

The build cost and how to pay it down.

Storing 10 completions per node multiplies memory. We accept that because memory is cheap and latency is sacred, and the estimation already told me it fits in RAM with headroom.
If memory gets tight, store top_k only on larger-subtree or shallower nodes and bounded-scan the rest.
Store references into a shared string pool, so each node's 10 entries are 10 small integers, not 10 copied strings.

6.2 Caching, debouncing, and the hot-key problem#

Three layers of defense sit in front of the trie, and each shaves load before it reaches memory.

First, the client debounces.

Do not fire on every keystroke. Wait about 150ms after the last key, and cancel in-flight requests when the user keeps typing.
That alone cuts request volume by more than half: the single highest-leverage move.
It is free (runs on the device) and improves perceived snappiness because we stop painting stale dropdowns.

Second, a Redis prefix cache.

Short prefixes like "a", "ho", "how" are requested constantly and their answers barely change minute to minute.
Cache the top K response keyed by the normalized prefix, TTL of a few minutes.
Short-prefix hit rate is very high, so most load never reaches the trie.
The cache key must be the same normalized string we index under, or hits silently vanish.

Third, the hot-key problem (the one that bites in production).

A single wildly popular prefix during a breaking-news moment can hammer one cache shard.
Consistent hashing sends every request for that prefix to the same Redis node, so it melts while the rest idle.

Defend it three ways, together:

Replicate the hottest prefixes across multiple cache nodes and pick a replica at random on read, spreading load across N nodes instead of pounding one.
In-process LRU inside the Suggest Service for the top few thousand prefixes, so the very hottest never cross the network. An in-process hit is a map lookup: nanoseconds, zero network. This is the big win.
Serve short prefixes slightly staler on purpose. A 2-character prefix does not need second-level freshness, so give those a longer TTL and let the in-process copy ride.

The layered read path. Debounce kills most requests on the device, the in-process LRU answers the hottest prefixes in nanoseconds, Redis absorbs the warm middle, and the trie only ever sees the cold long tail.

The payoff.

By the time a request reaches the trie, it is a relatively rare, cold-ish prefix.
The common case is answered in memory on the same box; the hot case is spread so no single node is a target.
That layering is what keeps p99 under 100ms even during a traffic spike.

6.3 Freshness: rebuilding and swapping the index#

Rankings have to move as behavior changes, but the serving trie is a static structure the builder hands over. Refreshing without pausing serving is the second hard part, because a live read path and a changing dataset are in natural tension.

The aggregation job runs on a window.

Recompute scores every few minutes from the Kafka stream, applying time decay so recent searches weigh more than month-old ones.
A half-life weight makes trending queries climb and stale ones fade on their own: an hour-old search counts for less than a minute-old one.
It writes the ranked list to the query store, and the builder compiles a new trie from it.

The swap has to be invisible to in-flight reads.

Each serving box holds the trie behind a pointer.
Build the new trie off to the side in memory; when ready, atomically flip the pointer.
In-flight requests finish on the old trie, new requests hit the new one, and we drop the old reference once it drains.
This is copy-on-write with a version swap: no locks on the read path, no downtime. The one cost is holding two tries for the few seconds of build, so size the box to fit two.

flowchart LR OLD[Old Trie v1] --> P[Serving Pointer] BLD[Builder] --> NEW[New Trie v2] NEW -.atomic flip.-> P P --> RQ[Read Requests]

The atomic swap. The new trie builds beside the live one, the serving pointer flips in a single step, and old in-flight reads drain off the previous version before it is dropped. No read ever blocks on a build.

If you need true near-real-time.

For most products, a full rebuild every few minutes is enough.
If the interviewer pushes on "breaking news in seconds," layer a small delta trie for very recent trending queries on top of the big base trie.
Look up the prefix in both, merge the two short top_k lists, keep the best K. The base rebuilds slowly, the tiny delta updates every few seconds.
I only reach for this when pushed, because it doubles the lookup and adds a merge.

The honest trade-off.

Full periodic rebuild is simple, predictable, and easy to reason about, but suggestions lag reality by the rebuild interval.
The delta-trie approach is fresher but adds a merge step and more moving parts.
For most products, pick the simple one and say why.

7Bottlenecks and trade-offs#

Memory on the serving fleet is the cost driver.

Storing top K on every node is the memory hog.
If the dataset outgrows comfortable RAM, shard the trie by first character or by language across boxes and route to the right shard.
English tries on one set, other languages on another.
Sharding by prefix also spreads hot-key load, since different popular prefixes land on different shards.

The short-prefix fan-in.

One- and two-character prefixes dominate traffic and are the hottest keys in the system.
Caching and in-process LRU handle it, and I lean on the fact that these answers are allowed to be stale.
If "a" returns a slightly old top 10, nobody cares.

Debounce versus perceived speed.

Too aggressive and the dropdown feels laggy; too loose and we drown in requests.
150ms is my starting point, tuned with real latency data, not a guess.
A refinement: debounce less on the first couple of characters and more as the query lengthens, since early keystrokes change the result set the most.

Consistency.

Eventual consistency on rankings, and I defend that hard. Strong consistency buys nothing the user can perceive and costs latency everyone feels.
The one place I want correctness is normalization: the prefix the client sends and the keys we index must normalize identically, or cache hits silently vanish and lookups miss.
Ship the exact same normalization function to client and server to kill that bug before it exists.

Availability over perfection.

If the Suggest Service is unhealthy, the client shows no dropdown and the search box still works. Autocomplete is an enhancement, never on the critical path of running a search.
The client gives up on the suggest call after a tight timeout, say 80ms, and lets the user type and hit enter.

Personalization, if asked.

Two-stage blend: fetch the global top N from the trie, then re-rank that small set with a lightweight per-user signal (recent searches, a small model) at request time.
Never build a per-user trie; that multiplies the dataset by the user count.
You personalize the ordering of a globally-sourced candidate set. Cheap, and the big structure stays shared.

Typo tolerance, if asked.

Prefix tries do not handle typos. To make "how to amke" find "how to make," add an edit-distance fallback.
When the prefix lookup returns too few results, run a bounded fuzzy match (a small BK-tree or a precomputed set of common misspellings).
Keep it as a fallback so the common case stays O(prefix length) and only the rare empty-result case pays for fuzzy matching.

Trade a little freshness for a lot of speed, because on a search box the user feels every millisecond and forgives every stale ranking.

8Summary#

The decisions that matter:

Precomputed top K per node. Built bottom-up, so a lookup is a short walk and an array read, not a subtree scan. The single most important call, driven entirely by the per-keystroke latency budget.
Two decoupled halves. A boring fast read path and a smart offline data path that never share a process, so a broken ranking job can never break the search box.
The dataset fits in RAM. Tens of GB, not tens of TB. That one number is why single-digit-millisecond lookups are possible, and it reorganizes the entire design into an in-memory lookup you replicate.
Layered defenses before the trie. Client debounce, Redis prefix cache, and in-process LRU for the hottest prefixes. Most requests never touch the trie, and the hot-key case spreads across replicas.
Eventual consistency with an atomic swap. Recompute from a Kafka stream with time decay, rebuild periodically, flip the serving pointer with copy-on-write. Freshness lags on purpose; latency and availability do not.
Out of scope by choice: entity completion, personalization for v1, typo tolerance, strong consistency. Naming them keeps me honest about what the interview covered.

Follow-ups the interviewer will ask (and your answers)

"A lookup for the prefix 'a' could match tens of millions of queries. How is that fast?"

It never scans the subtree. At build time the builder stores the top K completions directly on every node, bottom-up: a leaf carries itself, an internal node merges its children's K-length lists plus any completion ending there, keeping the best K. At serve time the lookup for 'a' is one edge walk and one array read, under a millisecond. The expensive work lives in the offline builder.

"Breaking news just happened. How do you get that query into the dropdown in seconds, not minutes?"

Layer a small delta trie for very recent trending queries on top of the big base trie. The base rebuilds every few minutes from the aggregation job; the tiny delta updates every few seconds. On read, look up the prefix in both, merge the two short top_k lists, keep the best K. It doubles the lookup and adds a merge, so I only reach for it when near-real-time is a hard requirement.

"One hot prefix is hammering a single Redis shard during a spike. Now what?"

Three things together. Replicate the hottest prefixes across multiple cache nodes and pick a replica at random on read, so load spreads across N nodes. Keep an in-process LRU inside the Suggest Service for the top few thousand prefixes, so the very hottest never cross the network (a nanosecond map lookup). And serve short prefixes slightly staler on purpose with a longer TTL, since a 2-character prefix does not need second-level freshness.

"You rebuild the trie every few minutes. How do you swap it without blocking live reads?"

Copy-on-write behind a pointer. Each box builds the new trie off to the side in memory, then atomically flips the serving pointer. In-flight requests finish on the old trie, new requests hit the new one, and the old reference drops once it drains. No locks on the read path and no downtime. The only cost is holding two tries for the few seconds of build, so I size the box to fit two.

"Cache hit rate looks terrible in production even though prefixes repeat constantly. Why?"

Almost always a normalization mismatch: the client sends a prefix normalized one way and we index and cache under another, so the keys never line up and every request misses. The fix is to ship the exact same normalization function (trim, lowercase, collapse spaces) to the client and the server, so the cache key is provably identical on both sides.

What you can now explain in the room

Why a naive trie subtree scan misses the latency budget, and how precomputed top_k per node fixes it.
Why the serving dataset fits in RAM, and how that one number reorganizes the whole design.
Why reads and writes are two separate systems, and why a broken ranking job can never break search.
How debounce, a Redis prefix cache, and an in-process LRU defend hot keys in layers.
How to rebuild the index from a Kafka stream with time decay and swap it in with copy-on-write.
Why you trade freshness for speed on purpose, and where you refuse to (normalization).

For how real companies frame this, see our related guides on designing a search ranking system, a rate limiter, and a distributed cache.

← Previous

Design Salesforce (Multi-Tenant CRM)

Design Slack

Get a prep plan built around your Design Search Autocomplete (Typeahead) interview

Tell us the role and your interview date. We will send back a dated, day by day plan. Free.

Thanks. Check your inbox, your Design Search Autocomplete (Typeahead) prep plan is on the way.