03. Search Autocomplete — Interview Q&A

~15 min read · Part 4 of 4 (Overview → HLD → LLD → Q&A)

These are the questions an interviewer actually asks once the diagram is on the board. Each answer is the strong version, followed by the wrong answer that quietly sinks candidates.

Q1. How do you return top-10 suggestions for a prefix fast enough to keep up with typing? Treat a prefix query as a lookup of a precomputed answer, not a search. Build a trie (radix/FST for compression) where every node stores its own precomputed top-10 completions, aggregated offline from query-frequency logs. A request then walks to the prefix's node — O(len(prefix)), at most ~30 character steps — and reads the list; there is no ranking or sorting at request time. Front it with a prefix-result cache so the hottest prefixes never even reach the trie. That is how you hold a ~30–50 ms internal budget at scale. Common wrong answer to avoid: "Run a LIKE 'prefix%' query against the database per keystroke." That scans and ranks on every request, misses the point that keystrokes generate enormous volume, and blows the latency budget the instant traffic is real.

Q2. Why store top-k at every node instead of just at the leaves? Because the alternative — walking the whole subtree under a prefix and ranking its completions at request time — is exactly the per-request work we are trying to avoid. Storing the precomputed top-k on each node turns a lookup into a single node read. It costs memory (10 (id, score) pairs per node, ~80 bytes, pushing the index to ~39 GB) but that memory is the price of the latency, and it is what makes even a cache miss resolve in a few milliseconds. Common wrong answer to avoid: "Store completions only at leaf/terminal nodes and gather them on the way." That reintroduces a subtree traversal and a sort into the hot path for every cold prefix.

Q3. The system must serve 100,000 prefix queries per second in under 100 ms — how? Recognize first that these are keystrokes, not searches, and that prefix popularity is Zipfian: a small set of short prefixes absorbs most traffic and the same prefix deserves the same answer for everyone. So cache the top-10 for the hottest ~1M prefixes and serve ~95% of the 100k QPS from memory, leaving only ~5,000 QPS to reach the trie shards. The edge/CDN absorbs the very hottest prefixes near users; the in-RAM sharded trie handles the cold-miss remainder at single-digit milliseconds. After a ~40–60 ms network round trip, the internal budget is ~30–50 ms, which the cache-then-lookup path fits comfortably. Common wrong answer to avoid: "Add more application servers until it's fast." Serving-tier CPU is not the bottleneck; the design is memory-and-cache-bound, and without the cache hit ratio every one of those servers still hammers the index.

Q4. How do you surface a trending term within minutes when the base index rebuilds only every few hours? Split freshness into two tiers. The base trie is rebuilt in a batch job every few hours — that is the expensive precompute — and owns the stable 99.9% of rankings. A separate real-time layer consumes the query event stream and maintains sliding-window counts over the last ~10 minutes, exposing surging candidates per prefix, refreshed every ~10 s. At serve time you merge the two by blended score. A spiking term crosses the surge threshold in ~2 minutes of counting and, bounded by a ~30 s cache TTL, appears to users in under 3 minutes — without touching the trie. The next batch build then bakes it into the base permanently. Trending is not a trie-rebuild problem; it is a streaming-merge problem. Common wrong answer to avoid: "Rebuild the trie more often." A full build over 100M queries takes ~1 hour; running it per minute is impossible, and even hourly can't meet "within minutes."

Q5. What's the memory footprint, and why keep the whole trie in RAM? Indexing the top ~100M distinct queries (avg 20 chars) yields roughly 300M trie nodes after prefix compression; at ~130 bytes/node (top-10 as (id, score) pairs plus structure) that's ~39 GB, plus a ~2 GB string dictionary, sharded across ~8–12 machines at 3–5 GB each. It stays in RAM because the latency budget demands it: an in-memory walk is single-digit milliseconds, whereas SSD-backed random reads at 10–20 ms each would blow p99 once you add fan-out and the trending merge. This is a memory-bound system, not a storage one. Common wrong answer to avoid: "Keep the trie on disk / in a database to save memory." The 10× memory saving costs you the latency budget; disk-backed prefix lookup can't hit the target under load.

Q6. How do you shard the trie, and what about skew? Partition by prefix — the shard that owns a prefix range holds that subtree. The catch is that prefix traffic is Zipfian, so the shard owning short common prefixes sees far more load than one owning rare ones. Handle it with two levers: replicate hot shards so several replicas share popular-prefix load, and let the front cache absorb the very hottest prefixes so they rarely reach any shard. Concretely the cache turns 100k QPS into ~5k at the shards, and replication spreads that residue evenly. The hottest prefix should be the cheapest to serve because it lives in edge and cache, not in a shard walk. Common wrong answer to avoid: "Hash the prefix so load spreads evenly." Hashing scatters a prefix and its extensions across shards, so a single prefix walk would need cross-shard hops; you shard by prefix subtree and fix skew with replication and caching instead.

Q7. Won't per-user personalization make results better? Why keep it so limited? Because personalization trades directly against the cache hit ratio that makes the whole thing affordable. A globally cached prefix result is shared by everyone, which is what buys the 95% hit ratio and the 20× load reduction from 100k to 5k QPS at the index. The moment you rank per user, every result is unique, the hit ratio collapses toward zero, and all 100k QPS hit the backend. So personalization stays cheap: fetch the shared cached candidate set and re-rank those ~10–20 items against the user's recent searches in a thin per-user step. Personalization is not a re-indexing problem; it is a re-ranking problem. Common wrong answer to avoid: "Maintain a personalized index or top-k per user." That destroys cache sharing and multiplies backend load ~20×, for a relevance gain a light re-rank of the shared set already captures.

Q8. How is the base trie's ranking actually computed? Rank by popularity — aggregated query frequency from the logs — propagated bottom-up. Insert each query as a leaf carrying its frequency, then post-order DFS: each node's top-k is the merge of its children's already-trimmed top-k lists (plus its own terminal entry if it is a full query), kept to the k highest scores. Since each child contributes at most k candidates, the work is linear in nodes times a small k, so a full build over 100M queries finishes inside the ~1-hour window. Apply time-decay to the frequency (score = freq × 0.5^(age/halflife)) so last year's popular query doesn't outrank this month's. Common wrong answer to avoid: "Sort all completions of each prefix at request time." That's the request-time ranking the precompute exists to eliminate; it doesn't scale to 100k QPS.

Q9. A trie rebuild swaps in a new index and cache entries get invalidated — what happens at 100k QPS? This is the dangerous moment. If a swap flushes cached entries while 100k QPS is flowing, the ~95% that were cache hits now miss at once and all fan out to the shards — a jump from ~5k to ~100k QPS against machines sized for 5k, which browns them out. Contain it three ways: swap the index atomically behind a pointer flip so no lookup sees a half-built trie; stagger swaps across shards and replicas so the cache re-warms in waves; and use single-flight coalescing keyed on prefix so many concurrent misses for the same cold prefix collapse into one shard walk. That's the line between a graceful rebuild and a self-inflicted outage. Common wrong answer to avoid: "Just flush the whole cache on every rebuild." A synchronized global flush is exactly what triggers the stampede; warm incrementally and coalesce misses.

Q10. What happens if the real-time trending layer goes down? Suggestions fall back to base rankings only — slightly stale on fast-moving terms, but the feature stays up because the trending merge is additive, not required. Availability is unaffected; only freshness degrades. On recovery the stream processor reprocesses from the retained event log and its sliding-window counts catch up within a window or two. Since the base trie still serves everything, users mostly won't notice unless something is actively trending during the outage. Common wrong answer to avoid: "Autocomplete goes down." It shouldn't — trending is an enhancement layered over a self-sufficient base index, so its loss is a freshness dip, not an outage.

Q11. How do you keep offensive or manipulated terms out of the suggestions? Apply a blocklist at both build time and serve time, and gate eligibility on more than raw count. A term must clear a minimum frequency and a minimum distinct-user threshold before it can rank, which defeats a single actor spamming one query. The build-time filter keeps blocked terms out of the trie; the serve-time filter over the merged list suppresses a term added to the blocklist between builds immediately, even though it still sits in the base trie until the next rebuild. Keep a kill-switch that purges a term from cache and index in one action. Common wrong answer to avoid: "Rank purely by frequency." That lets a coordinated group or a single high-volume script push offensive or manipulative completions to the top.

Q12. Why not just use the database's built-in prefix/full-text search per keystroke? Because the workload is the opposite of what a general query engine is tuned for: 100k QPS of tiny, repetitive, latency-critical prefix lookups where the same answer serves millions of users. A precomputed in-RAM trie plus a result cache answers the common case without ranking anything at request time, at single-digit milliseconds; a database prefix scan ranks per request, competes with other queries, and doesn't exploit the fact that the answer is shared and stable. The database still matters — as the log store feeding the batch build — but not on the read path. Common wrong answer to avoid: "Elasticsearch/Postgres full-text search handles it out of the box." It can, at low volume; at 100k QPS with a 100 ms p99 you need the precomputed index and cache, which is why even Elasticsearch ships a dedicated in-memory completion suggester rather than reusing normal search.

Deeper follow-ups

• How would you support multi-word / mid-query completion ("new york t") rather than only completing the current token?
• How would you add fuzzy matching (typo tolerance, "netflx" → "netflix") without abandoning the trie or blowing the latency budget?
• How would you tune the prefix-cache TTL against trending freshness — what breaks if you push it from 30 s to 5 minutes, or down to 1 s?
• How would you localize rankings per region and language without multiplying the index by every locale combination?
• How would you A/B-test a ranking change (e.g. adding time-decay) safely on the live serving tier?
• How would you detect and defend against a query-injection attack designed to poison trending in real time, before the distinct-user threshold catches it?

How this round is scored

Interviewers use autocomplete to see whether you reframe the problem before designing it — recognizing that a prefix query is a lookup of a precomputed answer, not a search, and that keystroke volume plus Zipfian skew makes caching the whole game. The defining seniority signal is how you handle the freshness-versus-precompute tension: a strong candidate lands the two-tier design (batch base + real-time merge) and can put minutes-and-seconds on why it meets "within minutes," rather than hand-waving "rebuild more often." Tradeoff fluency shows up in the memory-vs-latency and personalization-vs-cache-hit-rate discussions, where you name both sides with numbers — 39 GB in RAM to hold the budget, 95% hit ratio collapsing to zero under per-user ranking. The failure-mode thinking — the rebuild-swap stampede at 100k QPS, the trending-layer outage degrading freshness not availability — separates candidates who have operated these systems from those who have only drawn them. Doing the back-of-envelope math out loud (100k keystrokes → ~15k searches → ~5k shard QPS after cache) and using it to justify choices is what pushes an answer from "correct" to "senior."