medium google · part of Practice Questions · Senior SWE Roadmap
Requirements to clarify
- Functional: as a user types a prefix, return the top-k most relevant/popular completions in real time.
- Non-functional: extremely low latency (feels instant while typing), suggestions should reflect popularity/trends, query volume is very high (fires on nearly every keystroke).
Core components
- Trie augmented with popularity: each trie node (representing a prefix) caches its top-k most frequent completions, so a query is a single trie walk plus an O(1) lookup of the precomputed top-k — not a live re-ranking on every keystroke.
- Data collection pipeline: search query logs are aggregated (often via a separate batch or streaming job) to periodically rebuild/update frequency counts and the cached top-k per node.
- Caching: the most common prefixes (e.g., single letters) are extremely hot — an in-memory cache in front of the trie service absorbs most traffic (see Caching Strategies).
Key tradeoffs
- Real-time popularity updates (fresher suggestions) vs periodic batch rebuilds (simpler, cheaper, slightly stale) — most real systems accept staleness on the order of minutes to hours.