System Design Interview
Search autocomplete inspired by large search engines' typeahead: a sharded trie of precomputed top completions rebuilt from aggregated query logs, edge caching of popular prefixes, real-time trending, personalized re-ranking and blocklist filtering. A teaching design.
See why counting matches on each keystroke can't serve typeahead.
What was missing: Nothing yet.
Why that's risky: Every keystroke triggers a scan over billions of rows; suggestions must appear in tens of milliseconds to be useful.
What gets added: One server answering each prefix by scanning and counting matching queries in the log table.
Trade-offs: Always up to date, far too slow.
Answer every prefix with a single lookup.
What was missing: Suggestions were computed per request.
Why that's risky: Short prefixes like 'a' or 'ho' are requested enormously often, and every request still reaches our servers.
What gets added: A prefix index (a trie whose nodes hold their top 10 completions) sharded by prefix range, a suggest service reading it, query logs aggregated into a stats database, and an index builder that rebuilds the trie every few hours, drops blocked terms, and swaps it in atomically.
Trade-offs: Suggestions are hours old: new trends don't appear until the next rebuild.
Answer the most common prefixes before they reach our servers.
What was missing: Every keystroke reached the suggest servers.
Why that's risky: Breaking news searches don't appear until the next index build.
What gets added: An edge cache holding responses for popular prefixes for about a minute (plus client-side debouncing so pauses, not every keystroke, send requests).
Trade-offs: Cached suggestions can be a minute stale.
Surface what's rising right now without rebuilding the index.
What was missing: New trends waited hours for a rebuild.
Why that's risky: Everyone sees the same suggestions regardless of their own history or location.
What gets added: A trend detector reading the query log stream that spots fast-rising queries over sliding windows and publishes them per prefix, merged with the index's completions at serve time.
Trade-offs: Trending entries are checked against the blocklist before they're published, delaying them slightly.
Order suggestions for the person typing.
What was missing: No personalization.
Why that's risky: Scrapers and manipulation attempts aren't limited, and quality isn't measured.
What gets added: A personal ranker that re-orders the top completions using the person's recent searches and location.
Trade-offs: Personalized responses can't be cached at the edge, so only the re-ranking step is per person.
Resist manipulation and watch quality and speed.
What was missing: No limits or quality monitoring.
Why that's risky: Remaining risk is content: new offensive terms need fast addition to the blocklist.
What gets added: Rate limits per client (manipulators try to push terms by repeating searches), and monitoring of per-keystroke latency, edge hit rate, index freshness and suggestion click-through.
Trade-offs: Limits can affect shared networks; they're tuned per client type.
Use a trie or n‑gram index specialized for prefix lookups. If you also need full‑text features, maintain both: an inverted index for search and a compact trie/n‑gram for suggest. Keep indexes in sync via an async pipeline.
Put a hot result cache in front of the index, shard the suggest replicas behind a load balancer, and keep results small (limit K, compress). Use timeouts/circuit breakers and pre-warm caches on deploy. Track tail latency and cache hit ratio closely.
Combine popularity and recency signals from logs with optional user features (locale, history). Run a Ranking Service that merges index candidates with feature lookups; compute features offline and store in a features DB for low-latency reads.
Stream deltas from content changes and logs into a queue; batch and debounce updates in workers. Maintain a DLQ for bad events and rate-limit backfills. Expose tooling to pause/resume pipelines and rebuild specific shards/sectors.
Maintain a policy filter that runs post-ranking to remove banned terms and low-quality suggestions. Support tenant-specific blocklists and thresholds. Log rejections for review and retraining.
You're in the middle of an interview session. Leaving now will end your current attempt.
Explore concept overviews, real-system examples, key tradeoffs, and interview talking points for each roadmap section.
You've conquered this phase. These are the skills you now own:
