System Design Case Studies

Designing a Search Autocomplete

Autocomplete has to return ranked suggestions for a partial prefix in single-digit milliseconds, which means the ranking work has to happen ahead of time, not at request time.

A trie keyed by character, with each node caching its top-K most popular completions, turns a prefix lookup into an O(prefix length) walk instead of scanning all candidate strings
Precomputing top-K per node happens offline, on a schedule, aggregating query popularity from search logs — the read path never recomputes rankings live
A trie for a large vocabulary does not fit on one machine — sharding by first character, or by a prefix range, distributes it, at the cost of merging results across a shard boundary
Freshness tradeoff: a trending query will not appear until the next offline rebuild unless a separate fast-path layer specifically boosts very recent spikes
Client-side debouncing — waiting roughly 100-200ms after the last keystroke before firing a request — cuts request volume dramatically for a barely perceptible latency cost
The read path is cacheable per-prefix, since the same common prefixes are requested by many users, absorbing a large fraction of traffic before it reaches the trie service at all

High-level architecture

A trie node with a cached top-K

Offline rebuild vs live re-ranking
	Offline trie rebuild	Live re-ranking
Freshness	lags until the next scheduled rebuild	immediate
Read latency	very low — a precomputed lookup	higher — ranking work on the hot path
Cost	batch job cost, off the request path	ongoing compute on every request

Serving suggestions from a precomputed trie

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    List<String> topK = new ArrayList<>();   // precomputed offline, capped at K (e.g. 5-10)
}

List<String> suggest(TrieNode root, String prefix) {
    TrieNode node = root;
    for (char c : prefix.toCharArray()) {
        node = node.children.get(c);
        if (node == null) return List.of();
    }
    return node.topK;
}