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.