linkjobai revidoval tento gist 23 hours ago. Přejít na revizi
1 file changed, 36 insertions
typeahead.md(vytvořil soubor)
| @@ -0,0 +1,36 @@ | |||
| 1 | + | # System Design: Search Autocomplete (Typeahead) | |
| 2 | + | ||
| 3 | + | 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. | |
| 4 | + | ||
| 5 | + | ## Requirements | |
| 6 | + | ||
| 7 | + | - Return the top 5 to 10 suggestions for a prefix as the user types. | |
| 8 | + | - Latency under about 100 ms end to end, so each lookup must be a few milliseconds. | |
| 9 | + | - Suggestions ranked by popularity, with some freshness (trending queries). | |
| 10 | + | - Scale example: 10M daily users, about 10 keystrokes per search. | |
| 11 | + | ||
| 12 | + | ## Data structure | |
| 13 | + | ||
| 14 | + | 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. | |
| 15 | + | ||
| 16 | + | Storing the top-k lists at every node costs memory but makes reads very cheap, the right trade-off for a read-heavy system. | |
| 17 | + | ||
| 18 | + | ## Building the data | |
| 19 | + | ||
| 20 | + | 1. Log every search query. | |
| 21 | + | 2. A batch job (hourly or daily) aggregates the query counts. | |
| 22 | + | 3. Rebuild the trie (or the prefix to top-k table) and push it to the serving nodes. | |
| 23 | + | 4. For trending topics, add a smaller real-time layer that is merged at query time. | |
| 24 | + | ||
| 25 | + | ## Serving | |
| 26 | + | ||
| 27 | + | - Shard by prefix (for example by the first one or two characters), with care for uneven letters: "s" has far more queries than "x". | |
| 28 | + | - Cache the hottest prefixes in memory or at the CDN edge. | |
| 29 | + | - Client side: debounce keystrokes (wait about 50 ms) and cache recent responses in the browser. | |
| 30 | + | ||
| 31 | + | ## Extras worth mentioning | |
| 32 | + | ||
| 33 | + | Filtering offensive suggestions, personalisation (blend the user's history with global results), multi-language support, and spelling tolerance with edit-distance matching. | |
| 34 | + | ||
| 35 | + | --- | |
| 36 | + | *Disclosure: I'm with [Linkjob.ai](https://www.linkjob.ai/), which makes an AI interview copilot. This guide is general study material.* | |
Novější
Starší