System Design: Search Autocomplete (Typeahead)
Designing autocomplete, like the search box suggestions on Google or Amazon, is a popular interview question because it combines a classic data structure (the trie) with real latency constraints.
Requirements
- Return the top 5 to 10 suggestions for a prefix as the user types.
- Latency under about 100 ms end to end, so each lookup must be a few milliseconds.
- Suggestions ranked by popularity, with some freshness (trending queries).
- Scale example: 10M daily users, about 10 keystrokes per search.
Data structure
A trie where each node stores the top-k completions for its prefix. Looking up a prefix is then O(length of the prefix), with no subtree walk at query time.
Storing the top-k lists at every node costs memory but makes reads very cheap, the right trade-off for a read-heavy system.
Building the data
- Log every search query.
- A batch job (hourly or daily) aggregates the query counts.
- Rebuild the trie (or the prefix to top-k table) and push it to the serving nodes.
- For trending topics, add a smaller real-time layer that is merged at query time.
Serving
- Shard by prefix (for example by the first one or two characters), with care for uneven letters: "s" has far more queries than "x".
- Cache the hottest prefixes in memory or at the CDN edge.
- Client side: debounce keystrokes (wait about 50 ms) and cache recent responses in the browser.
Extras worth mentioning
Filtering offensive suggestions, personalisation (blend the user's history with global results), multi-language support, and spelling tolerance with edit-distance matching.
Disclosure: I'm with Linkjob.ai, which makes an AI interview copilot. This guide is general study material.