← Create New Paste

Designing Search Autocomplete (Typeahead) in a System Design Interview

5 views
"Design the search box suggestions for a large site" is a favorite system design prompt because it looks small and hides a lot of depth. Here is a structure that keeps you organized and shows the trade-offs interviewers want to hear. 1. Clarify requirements first Ask what is being suggested (search queries, products, usernames), how many suggestions to show (often five to ten), whether results are personalized, which languages must be supported, and how fresh suggestions must be. A typical latency target is under 100 ms end to end, because suggestions update on every keystroke. Agree on scale: for example 10 million daily users, each typing a few searches a day with several keystrokes each, which quickly turns into tens of thousands of requests per second at peak. 2. Separate the read path from the data pipeline The read path must be extremely fast and simple: take a prefix, return the top k completions. The data pipeline can be slow: aggregate query logs, count frequencies, filter offensive terms, and build the structure the read path uses. Saying this out loud early is one of the strongest signals you can give, because it shows you know where the hard constraints actually are. 3. Choose the core data structure A trie keyed by characters is the classic answer. The key optimization is storing the precomputed top k completions at every node, so a lookup is just walking down the prefix and reading a list, with no subtree traversal at query time. Mention the memory cost and how you would limit it: cap prefix length, store only the top k at each node, and prune rare queries. An alternative many teams use in practice is a key-value store mapping every prefix directly to its top k list, which is simpler to shard and cache. 4. Scale it Shard by prefix range, but watch for hot spots: far more queries begin with "s" than with "x", so split ranges by observed traffic rather than by alphabet. Put a cache in front, and use browser caching for short prefixes since they are requested constantly and change slowly. Clients should debounce keystrokes and cancel in-flight requests, which can cut traffic dramatically. 5. Keep it fresh Rebuild the structure in batch (hourly or daily) from aggregated logs and swap versions atomically. For trending events, add a small real-time layer that blends recent counts with the batch scores, often with time decay so yesterday's spike fades naturally. 6. Cover the edges Interviewers like hearing about filtering unsafe suggestions, handling typos with fuzzy matching, personalization as a re-ranking step on top of global results, and multi-language input. Practice talking through it The hardest part is often explaining all of this clearly while someone is listening and asking follow-ups. Practice aloud with a timer, and sketch the diagram as you talk. Some candidates also use Linkjob AI (https://linkjob.ai), which gives real-time help during live job interviews and technical interviews, to stay structured when a follow-up question throws them off track.
Created Nov 15, 2026 17:00 Expires Nov 15, 2027 17:00