Heavy Lifting + Your Rehearsal
Design search autocomplete
You type three letters and the search engine already knows what you want. It does this a hundred thousand times a second, for every keystroke of every user, with a budget of about 100 milliseconds before the suggestion feels stale. The trick is that almost nothing is computed when you type — the answer was ready hours ago.
Requirements: given a prefix, return the top 5 suggestions, ordered by popularity, fast enough to render before the next keystroke. Scale check: a large search engine sees on the order of 100K queries per second — and autocomplete fires per keystroke, not per search, so expect several times that, say 300–500K requests per second at peak. Read-only, latency-critical, and tolerant of data that is hours old: those three properties will do all the design work for you.
The core structure is a trie: one node per character of every prefix, so 'weather' lives under w → we → wea → weat… The naive move is to walk to the prefix node, then scan its whole subtree to find the five most frequent queries — that is O(subtree size) per keystroke, and it dies at scale. The key optimization: store the top-k suggestions inside every node, precomputed. Now a lookup is walk p characters, read one list — O(prefix length), a handful of pointer hops. The cost is memory: a hot word appears in the lists of up to p nodes along its path, so with 20M prefix nodes, k = 5, and ~30 bytes per entry you are looking at several GB of RAM. That is exactly why k is 5 and not 50.
Never live. Query logs flow into an offline pipeline — a daily or weekly batch job that aggregates frequencies per query (MapReduce, Spark, whatever the shop runs), ranks them, and produces the top-k list for every prefix. Before anything enters that ranking, it passes through filtering: profanity, abuse patterns, legal takedowns, and known injection attacks are stripped at the pipeline stage, so a banned phrase can never reach the trie — let alone a user's screen. Trying to update the trie per query instead would mean writes racing at hundreds of thousands per second against readers that demand 100ms: a lock contention nightmare you simply declined to have.
When the trie outgrows one machine's RAM, you shard it. The naive split is by first-letter ranges — a–f here, g–l there — and it is skewed: 's' carries far more traffic than 'x', so one shard melts while another idles. Hashing the prefix spreads load evenly, at the price of losing range locality you never needed anyway. Updates are just as deliberate: the pipeline builds the entire new trie offline, ships it to the serving machines, and each server swaps the old structure for the new one atomically — a pointer flip, or a swap of the data directory. Readers never see a half-built trie, and a bad build is rolled back by flipping the pointer back.
Autocomplete is a precomputed answer, rebuilt offline on a schedule. The live system does one thing: read. Every hard part — ranking, filtering, freshness — was moved to a batch job where minutes are cheap, so that the serving path could stay a memory walk measured in microseconds.
Why store the top-k list inside every trie node, and what do you pay for it? (Without it, answering a prefix means scanning the node's whole subtree for the k most frequent queries — O(subtree size) per keystroke, unworkable at hundreds of thousands of QPS. With it, lookup is O(prefix length): walk the prefix, read a ready list. The price is memory — each hot word is duplicated in the lists of up to p nodes — plus an offline rebuild every time the lists need refreshing.)
Trie for the shape, top-k at every node for the speed, an offline log pipeline for the rankings, filters before the trie ever sees a word, hashed-prefix sharding when RAM runs out, and an atomic swap so updates never blink. Autocomplete is the purest case of 'precompute the read path' you will ever design.
Take your own product's search logs — or a public query dataset — and build the pipeline on paper: how you'd count frequencies, what you'd filter out, and how often you'd rebuild. Then estimate the trie: how many prefixes, what k you'd pick, and whether it fits in one machine's RAM. The numbers will surprise you less than you think — that is the point.
Heavy Lifting + Your Rehearsal