Loading...
A 20-minute mock system design interview. You drive the pace. Jump to the board when you are ready; skip capacity math if you want. The interviewer grades your thinking, not a template match.
This is the rare question where a data structure — the trie — is the centerpiece. Prefix match is the easy part. The interview is making the trie O(1), updating it without stopping the world, and sharding a tree.
Two shared surfaces (only one is on screen at a time; use the panel arrow to switch):
Build incrementally while you talk. Trace one keystroke — the "n" after "di" — end to end through your diagram to a ranked top-5 list. Argue the tradeoff, not "industry standard."
Read this before you go in. These are the decisions, and why they matter.
Typing "dinner" sends six requests (q=d, q=di, … q=dinner) — about 20 per completed query. That ×20 multiplier is the single best estimation signal in this question. It drives the QPS that kills a database round-trip, and the client etiquette that cuts load: debounce ~50 ms, cancel in-flight requests, do not fire until 2–3 characters, browser-cache responses (Cache-Control: private, max-age=3600 — Google caches autocomplete for an hour).
SELECT query FROM freq_table WHERE query LIKE 'din%' ORDER BY frequency DESC LIMIT 5 is a fine warm-up and works small. At ~24K QPS with a ~100 ms budget, the round-trip plus prefix scan breaks. State it, then volunteer the transition: the aggregated index is small (~3 GB of unique terms, ~25 GB with a year's growth), so the whole thing lives in memory as a trie. Elasticsearch's completion suggester is equally defensible if you can name its operational cost against a purpose-built trie.
The naive algorithm is three steps: find the prefix node — O(p); walk the subtree for completions — O(c); sort by frequency and take five — O(c log c). A popular short prefix has a huge subtree, and that blows 100 ms.
Two fixes. Cap prefix length (~50 chars) so the walk is constant. Cache the top five at every node — node "din" already holds its list. Query becomes find node + read list = O(1). Name the trade: space for time.
Know the cost. Bumping one query's frequency means updating the cached list in every ancestor up to the root. That is why nobody updates the serving trie in place. A space refinement: store references to terminal nodes plus frequencies, and reconstruct the phrase by walking parents — do not duplicate full strings on every node. Single-child chains can collapse into a radix / compressed trie.
Do not update per search. Tens of thousands of writes would contend with 100 ms reads, and the top suggestions barely move. Instead: log completed searches (sampled 1-in-N — if a term under 1,000 searches never surfaces, 1-in-1,000 is safe) → aggregate periodically with MapReduce → workers rebuild the trie offline → atomic swap, or update a secondary while the primary serves and promote it.
Ask how fresh suggestions must be before you pick the interval. Weekly is fine for Google keywords; breaking-news products need short intervals. A sliding window or exponential moving average weights recent data so old queries do not sit at the top forever. In-place update is only viable for a small trie.
The typeahead API is read-only. There is no "record a search" endpoint on this service. The search system writes completed queries to the log; this service consumes the next rebuild.
Partitioning a tree is harder than partitioning a table: a prefix query must land on the shard that holds its subtree.
Legal or safety orders a suggestion gone now; your rebuild is weekly. Two-stage answer: a filter layer in front of the trie cache for immediate effect, plus asynchronous physical deletion from the Trie DB and aggregated data so the next rebuild is clean and the blocklist does not grow forever.
If a trie server dies, replaying raw logs takes hours. Snapshot the trie periodically. Grokking's encoding is level-order: each node's character plus child count, children immediately after (C2,A2,R1,T,P,O1,D). Do not serialize the top-k lists — children do not exist yet when a node is read — recompute them bottom-up on load. Trie DB options: a document store of weekly snapshots (MongoDB), or a key-value store where every prefix is a key and the node's top-k is the value. The KV shape is easy to shard and easy to cache.
One complete design you can study, then rebuild in your own words. Do not recite it. In the interview, draw your graph and defend the choices.
Rough numbers are fine; the keystroke multiplier is what gets graded.
Two subsystems. The query path never leaves memory: a keystroke hits the API, the in-memory trie shard, and a filter — nothing else. The data-gathering pipeline rebuilds the trie offline from sampled search logs. Those logs do not come from the suggest API; they come from completed searches.
Web Client / Mobile Client (debounce ~50 ms, min 2–3 chars, browser cache 1 h)
→ Load Balancer (carries the prefix → shard map)
→ Service "Query API" (mark distributed)
→ Cache "Trie Cache" (in-memory trie shards; mark distributed)
-- miss --> MongoDB "Trie DB" (serialized snapshots)
→ Service "Filter" (blocklist; then respond)
[offline — not on the suggest path]
Web Client --completed search--> Blob Store "Analytics Logs" (sampled 1-in-N)
→ Worker "Aggregator" (weekly MapReduce → query, week, frequency)
→ Cron → Worker "Trie Builder" (rebuild bottom-up, atomic swap)
→ MongoDB "Trie DB" and Cache "Trie Cache"
GET /v1/suggest?q=<prefix>&limit=5. Debounces ~50 ms, cancels in-flight requests, caches responses for an hour. The cheapest capacity you will ever buy.di and issues GET /v1/suggest?q=din&limit=5. A fresh browser-cache hit would return here with no network call.din in the shard map and routes to the shard that owns the d… range.d → di → din). Node "din" already holds its top five — dinner ideas 4200, dinosaur 3100, dining table 2750, dinner recipes 2600, dino game 1900. No subtree scan, no sort.Cache-Control: private, max-age=3600.Cache miss / server restart: replenish from the Trie DB snapshot. Serialization is level-order — character plus child count, children immediately after (C2,A2,R1,T,P,O1,D). Top-5 lists are not serialized; recompute them bottom-up on load. A secondary replica serves during recovery.
Takedown today, rebuild weekly: add to the filter's blocklist for immediate effect; delete from the Trie DB and aggregated data asynchronously so the next rebuild is clean.
Breaking news: a brand-new top query shows nothing until the next rebuild. Name the lag; sketch the extension — streaming aggregation (Kafka + a stream processor) and recency-weighted ranking — and acknowledge real-time top-k is a materially harder problem.
Prefix spans two shards (capacity-range sharding): an aggregator tier between the load balancer and trie servers merges the partial top-5 lists.
QueryLog(query, timestamp) — raw, append-only, sampled
AggregatedData(query, week, frequency) — MapReduce output, trie weights
TrieNode(prefix → {children, top5: [(query, freq)]}) — KV form: prefix is the key
BlockList(query, reason) — filter layer + async delete queue
A key-value trie (prefix → top-5 in DynamoDB or Redis) instead of document snapshots. Redis sorted sets per prefix instead of an explicit trie. Hourly aggregation instead of weekly, if you argue freshness. Elasticsearch's completion suggester, if you can defend its operational cost against a purpose-built trie. What matters is that you can argue the tradeoff.