Tries and top-K for prefixes

01The intuition

The problem it solves

A railway enquiry clerk has a thick timetable and travellers who start saying a station name: "Vija…". By the time they finish, the clerk should already be saying "Vijayawada?". Flipping through an alphabetical list for every letter typed is too slow when a million travellers type at once; the clerk needs a book arranged so that after "Vij" the page already shows the few stations that start that way, best first.

Search autocomplete is that clerk. For every prefix a user has typed so far, return the top few completions in under 100 ms. A trie (prefix tree) is the book arranged by letters; storing the best completions at each node is what makes the answer a single lookup instead of a search.

Build it one piece at a time

Step 1: the trie. A tree where each edge is one character and each node represents the prefix spelled by the path from the root. Insert "car", "cat", "cart": the root has child c, which has child a, which has children r and t; r has child t. Nodes where a word ends are marked.

Step 2: find completions. Walk the typed prefix down the trie (3 steps for "car"), then collect every marked node below it: "car", "cart". Walking is O(length of prefix); collecting can be large under a short prefix like "c".

Step 3: add popularity and keep only the top K. Each word carries a score (how often it was searched). At each node, store the top K = 5 completions in its subtree, precomputed. Now "car" returns the node's stored list directly. The collect step is gone.

Step 4: update without rebuilding everything. When "cart" gains searches, its score changes, and the top-K lists along its path (root, c, ca, car, cart) may change: at most as many nodes as the word has letters. Batch updates from a stream of queries every few minutes, and rebuild the whole trie from scratch nightly to fix drift.

Step 5: make it serve the world. Shard the trie by first letter or first two letters so each server holds a slice, and replicate each slice many times because reads dwarf writes. Put the top prefixes (one to three characters, the hottest by far) in a cache or even in the browser. The same structure answers "top 10 hashtags" if the key is time plus tag and the scores are windowed counts.

Why it works, with the numbers

Lookup cost depends on the prefix length, not on the number of words:

time per query ≈ L node hops + one list read, so a 6-character prefix over 100 million terms costs 7 memory reads

Storage is the trade: a top-5 list at every node for 100 million terms with 20 million distinct prefixes is about 20 million × 5 × 8 bytes ≈ 800 MB of lists plus the trie itself, which fits in the memory of a handful of servers. The guarantee is that the stored list at a node equals the true top K of its subtree as of the last update. The failure modes are a prefix nobody can shard well (single-letter prefixes get the most traffic and the biggest subtrees, so they are cached hardest), unicode and languages where "character" is not a byte, and offensive or personal completions, which need a filter at build time rather than at query time.

The trade-off you must say out loud

Precomputed top-K lists cost memory and freshness (a suggestion lags the world by the update interval) to make reads constant-time. Say the update interval and the K. The interviewer will ask about personalisation and typos; the answers are a small per-user trie merged at query time, and fuzzy matching only for prefixes that return nothing, because fuzzy lookups are expensive.

Where it shows up in the 100 Google problems

• Design search autocomplete: the question is this structure plus the pipeline that keeps the scores fresh.
• Design trending topics / top-K over a sliding window: the same top-K-per-node idea with scores that decay as the window slides.

02Used in these problems

• Design search autocomplete
• Design trending topics / top-K over a sliding window