Scope the requirements
The trap here is treating it as a search problem. It's a precomputation problem: the ranking work happens offline, hours before the keystroke, and the online path is a single key-value lookup. Interviewers score whether you find that inversion early.
Functional — what it must do
- As the user types, return the top 5-10 suggestions for the current prefix on every keystroke.
- Suggestions ranked by historical query popularity — frequency of past searches.
- Suggestions refresh from search logs on a schedule; hourly-to-daily staleness is acceptable, real-time trending is a stretch goal I'll flag.
- Filter offensive and blocked terms before anything reaches a screen.
- Explicitly cut: spell correction, personalisation, and multi-language — I'll assume lowercase alphabetic queries for v1 and offer these back as extensions.
Non-functional — the numbers that shape the design
- Latency under 100 ms end-to-end per keystroke, ideally under 50 ms server-side — anything slower and suggestions arrive after the user has typed past them.
- Read-heavy to an extreme: every search generates ~20 autocomplete requests, one per keystroke.
- High availability on the read path; eventual consistency is fine — a suggestion list a day stale is invisible to users.
- Scale target: 10M DAU, ~20,000 QPS sustained, double at peak.
- Suggestion data survives node restarts — the in-memory structure needs a durable source to rebuild from.
The latency budget is the whole question. Under 100 ms per keystroke means no ranking, no scoring, no database scan at query time — the top-k list for every prefix has to already exist before the user types it. Everything interesting happens in the offline pipeline.
Back-of-envelope estimates
The numbers make two decisions for me: the keystroke amplification says the read path must be a cache hit, and the tiny daily data growth says the trie rebuild is an easy batch job, not a streaming problem.
| Quantity | Estimate | How you got there |
|---|---|---|
| Searches | ~1,200/s | 10M DAU × 10 searches/day ÷ 86,400 s. |
| Autocomplete QPS | ~24,000/s | ~20 keystrokes per search × 1,200 searches/s. This is the number that matters. |
| Peak QPS | ~48,000/s | 2× average; suggestion service is stateless so this is a horizontal-scale problem, not a redesign. |
| New query data | ~0.4 GB/day | 20% of 100M daily queries are new × ~20 bytes each. Trivial — the analytics store yawns. |
| Trie size | ~tens of GB | Millions of distinct queries × prefix nodes × cached top-10 lists. Fits in memory on a few shards. |
| Client debounce saving | ~30-50% | A 50 ms debounce plus browser caching cuts QPS before it ever reaches me — say this early, it's free capacity. |
48k QPS at peak with a 100 ms budget means every request is one memory lookup. And 0.4 GB of new data a day means I can rebuild the whole structure offline daily — the write path and read path never meet.
Sketch the API
One public endpoint. The interesting decisions are on the client, which most candidates forget owns a third of the performance story.
- The client is part of the design: debounce keystrokes by ~50 ms, cache prefix results locally (typing then backspacing re-hits the same prefixes), and cancel in-flight requests when a new keystroke lands — otherwise stale responses race and overwrite fresher ones. Saying this unprompted signals you've built one.
- Responses carry
Cache-Control: max-age=3600— suggestions barely change hour to hour, so let browsers and the CDN absorb repeat prefixes. The cost is up to an hour of staleness, which the requirements already accepted.
Data model
Two worlds: an analytics table that accumulates truth slowly, and a serving structure built from it. The serving structure is the famous part — a trie with the answers precomputed into it.
The serving store is really a key-value problem — key is the prefix, value is a precomputed list — so Redis (or any KV store holding serialized trie shards) fits exactly, with the warehouse behind it for rebuilds. I would not put this in Postgres: there's no relational query here, and a LIKE 'prefix%' scan with an ORDER BY frequency is precisely the query-time work this design exists to avoid. If the team already runs Elasticsearch, its completion suggester is the pragmatic alternative — I'd take it for operational simplicity and give up fine control over ranking and latency.
High-level design
Two decoupled paths. The query path is boring by design: load balancer, stateless suggestion service, trie cache. The data path is a batch pipeline that turns raw search logs into a fresh trie snapshot on a schedule.
- User types a character → client debounces ~50 ms, checks its local cache, then sends
GET /v1/suggestions?q=pre. - The suggestion service consults the shard map to find which trie shard owns this prefix, reads the precomputed top-10 from the Redis trie cache (~1 ms), passes it through the blocked-terms filter, and returns.
- On a cache miss (rare — the cache is warmed from snapshots), it reads the trie DB and back-fills Redis.
- Meanwhile, completed searches flow into Kafka. Aggregators sample and count them into the frequency table.
- On schedule (daily, hourly if the product wants fresher), the trie builder constructs a new trie from the frequency table, writes versioned snapshots to the trie DB, and warms the cache shard by shard — an atomic version flip, never an in-place mutation.
Deep dives — where the interview is won
Precompute top-k at every node — query-time traversal is the classic fail
The naive trie answers a prefix query by walking to the prefix node, then doing a DFS over the entire subtree to collect candidates and sorting them by frequency. For a two-letter prefix like be that subtree holds hundreds of thousands of queries — the traversal alone blows the 100 ms budget by orders of magnitude, and it does so on the shortest prefixes, which are the most common requests. This is the single most common way candidates fail this question.
The fix is to move all of that work to build time: every node stores its own top-10 list, computed once by the trie builder in a bottom-up pass (a node's top-10 is a merge of its children's top-10s plus itself). A query is now O(prefix length) pointer hops and one list read — effectively constant time. I'd also cap indexed prefix length at ~50 characters; nobody needs autocomplete on character 51, and it bounds node count.
Shard by prefix range, not by first letter
Tens of GB of trie doesn't fit one node once you add replicas and headroom, so it shards. The reflex answer — 26 shards, one per first letter — is badly skewed: prefixes starting with 's' or 'c' carry orders of magnitude more queries than 'x' or 'z', so one shard melts while others idle.
The standard fix is a shard-map manager: analyse the historical prefix distribution and split so each shard carries roughly equal query volume — perhaps one shard owns all of 's', another owns 'u' through 'z' combined. The suggestion service consults the (tiny, heavily cached) shard map to route each prefix. The map only changes when a rebuild rebalances it, so it's a static lookup in practice, not a coordination bottleneck.
be and bes must land on the same shard for the trie to make sense. Range-based sharding is forced; the map just makes the ranges fair.Freshness: a daily rebuild plus a small trending patch
A daily rebuild is right for the base ranking — query popularity moves slowly, and rebuilding offline keeps the serving path read-only. But it fails visibly on breaking news: a story erupts at 9am and autocomplete doesn't know until tomorrow. If the interviewer pushes on this, do not offer to update the trie per-query online — one search updates every prefix ancestor's top-10, a write amplification of ~20× at 24k QPS against the structure you're serving reads from.
The layered answer: keep the big trie on its daily rebuild, and run a stream job (Kafka into Flink) that computes a small time-decayed trending set — the last hour's fast risers, a few thousand entries. The suggestion service merges the trending patch into results at query time. Two structures, two update cadences, and the hot path stays a lookup plus a tiny merge.
Durability and deploys for an in-memory structure
The trie lives in memory, so I need answers for "a node restarts" and "a new version ships". Both come from the same mechanism: the trie builder writes versioned, serialized shard snapshots to durable storage. A restarting server loads its shard's latest snapshot — no replaying logs, no rebuilding from the warehouse on the critical path. Losing a cache node costs seconds of degraded latency, never data, because the source of truth is the frequency table upstream.
Version flips are how updates deploy: serve version N while loading N+1 alongside, then atomically switch pointers and drop N. Readers never see a half-built trie. The blocked-terms filter deliberately sits outside the trie, applied at response time — so removing a newly offensive suggestion is a config push, not an emergency rebuild.
Follow-ups you should expect
How would you support personalised suggestions?
What about multi-language support?
Why not Elasticsearch's completion suggester instead of building all this?
How do you handle a trending offensive query — something hateful suddenly spiking?
What breaks first at 10× traffic?
Where candidates lose the room
- Computing top-k at query time by traversing the subtree under the prefix — the number-one fail; it's a build-time job, and the interviewer is waiting for you to see that.
- No client-side debounce, caching, or request cancellation — you multiply your own QPS by 2-3× and let stale responses race fresh ones.
- Updating the trie synchronously on every search — one query bumps every prefix ancestor, a ~20× write amplification aimed at your own read path.
- Sharding alphabetically without mentioning skew — 's' is not 'x', and the interviewer knows it.
- No persistence story for the in-memory trie — a restart shouldn't mean rebuilding from raw logs while users get no suggestions.