# 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

1. Log every search query.
2. A batch job (hourly or daily) aggregates the query counts.
3. Rebuild the trie (or the prefix to top-k table) and push it to the serving nodes.
4. 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](https://www.linkjob.ai/), which makes an AI interview copilot. This guide is general study material.*