Trie Autocomplete Engine Lab (Interactive)
Type into a real prefix trie with cached top-K and watch debounce cut keystroke queries. Serve live top-K completions from a built trie with per-node caches, comparing cached retrieval against a subtree DFS scan.
Google Typeahead: Live Trie Walk vs Pre-Computed Node Cache
Type a prefix against a real prefix tree of 26 trending queries and compare O(K) cached lookup to a subtree DFS.
- 1. design url shortener (950)
- 2. design uber (910)
- 3. design uber eats (760)
- 4. design unique id generator (640)
- 5. design uptime monitor (320)
At 300k keystroke requests per second a fresh DFS is CPU suicide, so the offline Spark/MapReduce job that rebuilds the trie nightly also writes the Top-5 list into every node on the path — turning serving into walk-prefix, read-list, return. Debouncing collapses "design u" keystrokes into one call, Edge CDN caches the hottest prefixes for seconds, and the trie shards across servers by first character so a rebuild never takes the whole service down.
How It Works Under the Hood
Autocomplete is latency-critical because it fires on every keystroke. The data structure is a trie: walk to the prefix node, then return the most popular completions beneath it. Precomputing top-K by search volume at every node turns each keystroke into an O(K) cache read instead of a depth-first subtree crawl, so a three-character prefix costs the same as an eight-character one. On the client side, debouncing keystrokes for about 150 ms collapses a burst of typing into one request, and rate-limiting per user keeps a fast typist from firing 300k QPS of redundant lookups. Type a real prefix into the corpus and toggle cached-versus-DFS to see candidate nodes scanned diverge.
Core Architectural Principles
- Trie prefix walk then cached top-K is O(K); a live DFS subtree scan visits every node below the prefix.
- Debouncing around 150 ms collapses a keystroke burst into a single query, cutting QPS sharply.
- Node subtree count grows with prefix depth — short prefixes have millions of descendants.
Describe the trie with cached top-K per node as the standard answer and justify why you precompute for read speed versus rebuild periodically for freshness. Then cover the request path: debounce, client and server caching of hot prefixes, and rate limiting. Mention learning-to-rank by frequency, geography, and recency, and that searched-for popularity, not alphabetical order, decides suggestion ranking.
Precomputing top-K at every node gives constant-time suggestions but bloats memory and needs periodic refresh to stay fresh.