Design Search Autocomplete

Design Search Autocomplete

Step 1 of 11

peak10 000 q/s

Ten thousand queries a second, and every keystroke is a candidate request. Cut them first.

The Idea

Turn each keystroke into ten ranked suggestions inside 100 ms. Assume 10 000 queries a second at peak over 50 million distinct prefixes — far too tight to run a real search and rank it while somebody is still typing.

Real-World Example

A library's card drawer. The tabs already sort the cards, so you are not searching at all: you are walking down a path that somebody else built and sorted in advance.

The Tradeoff

A trie whose nodes carry their own top-10 answers a prefix in one lookup, and must be rebuilt as popularity shifts, so suggestions lag by however long that job takes. Debouncing on the client and caching at the edge delete most of the traffic before it ever exists.

Your turn

Put the steps in the right order.

1. 1Return the node's precomputed top-10 list↑↓
2. 2Debounce the keystroke and cancel the request still in flight↑↓
3. 3Walk the trie down to the node for that prefix↑↓
4. 4Check the edge cache for this exact prefix first↑↓

Check order

Mini quiz

1 / 3

Each trie node stores its own top-10 list so that:

• AThe trie uses less memory
• BA prefix is answered by one lookup instead of a ranked search
• CTypos are corrected
• DThe cache can be skipped