Requirements and estimates
- As the user types, show the top 5–10 most popular queries starting with the prefix.
- Respond within ~100 ms, since it fires on almost every keystroke.
- Popularity can be a day behind; trending terms may update more often.
- Filter offensive or unsafe suggestions.
10M daily users × 10 searches × ~6 keystrokes ≈ 600M requests/day ≈ 7k/s (peak ~20k/s)
A trie with cached top-k
A trie stores queries character by character, so all queries with a prefix live under one node. Walking to the prefix node is O(length of prefix). Searching the whole subtree for the most popular completions on every keystroke would be too slow, so each node stores its top-k completions, computed when the trie is built.
class Node {Map<Character, Node> children = new HashMap<>();List<String> top = new ArrayList<>(); // best k queries under this prefix, precomputed}List<String> suggest(String prefix) {Node n = root;for (char c : prefix.toCharArray()) {n = n.children.get(c);if (n == null) return List.of();}return n.top; // O(prefix length), no subtree search}
Storing top-k at every node costs memory but turns the lookup into a short walk. Limiting prefix length (say 20 characters) and compressing chains (a radix tree) keeps it manageable.
Data pipeline
- Collect: search queries are logged to a stream.
- Aggregate: a batch job (hourly or daily) counts query frequencies, with time decay so stale terms fade.
- Build: workers build the trie with top-k per node and serialize snapshots.
- Serve: suggestion servers load the snapshot into memory and swap atomically to new versions. No writes happen on the serving path.
Scaling and latency
- Replicate the in-memory trie across many servers; if it's too big, shard by prefix range (a–f, g–m…), splitting busy ranges further since prefixes aren't evenly popular.
- Cache responses for short prefixes, which are few and extremely hot, at the CDN or the browser.
- On the client: debounce keystrokes (wait ~100 ms) and reuse earlier results while the user keeps typing the same word.
Serving and building suggestions
The user types "de". The very common short prefix is answered straight from the edge cache.
See it animated
Interview questions
Try answering out loud first, then open the model answer.
Q1Why a trie rather than a database LIKE query?intermediate
LIKE 'prefix%' on billions of rows, then sorting by popularity, is far too slow at thousands of requests per second. A trie groups every completion of a prefix under one node, and caching the top-k there makes each lookup a walk of a few characters in memory.
Q2Why precompute top-k at each node?intermediate
Without it you'd traverse the whole subtree under the prefix and sort by frequency on every keystroke, which for a short prefix like "a" means millions of nodes. Precomputing during the offline build makes reads O(prefix length) at the cost of memory and rebuild time.
Q3How do you keep suggestions up to date?intermediate
Rebuild from aggregated logs on a schedule (daily or hourly) and atomically swap the snapshot on servers. For trending topics, run a smaller fast pipeline (streaming counts over the last hour, such as a count-min sketch) and blend its results in.
Q4How would you shard the trie?advanced
By prefix: route queries by their first character or two to the servers owning that range, and split popular ranges more finely based on observed traffic. Each shard is also replicated for availability and read throughput.
Quick check
0 of 3 answered