This is one of the most common system design interview questions across all company tiers, asked at Google, Amazon, Twitter, and virtually every product company.
The reason: it has a clear probe (the trie data structure and its distributed form), and it reveals whether candidates
understand read-heavy system optimization, pre-computation, and the latency constraints of real-time user interaction.
The Question
“Design the search autocomplete / typeahead system. As a user types in a search box, the system suggests the top 5–10 completions in real time.”
Variants: “Design Google search suggestions,” “Design Twitter’s search autocomplete,” “Design Amazon’s search bar.”
Step 1 — Clarify
1. What goes in suggestions? Historical search queries (Google-style), titles in a product catalog (Amazon-style), or usernames/topics (Twitter-style)? The data source changes the indexing strategy significantly.
2. How many queries is the system handling? Google processes ~100K searches/sec. For most interviews: 10M DAU × 10 searches/day = 100M searches/day = ~1,200/sec average, 10K/sec peak.
3. How fresh must suggestions be? Do new trending searches need to appear in suggestions within minutes, or is 24-hour staleness acceptable? Real-time freshness is much harder. Start by assuming daily updates — offer to discuss real-time as an extension.
4. Personalized or global? Global suggestions (same results for all users) are vastly simpler. Personalized (based on your history) requires per-user ranking on top of the global index.
5. Latency SLO? Suggestions must appear within 100ms of each keystroke to feel real-time. This is the hardest constraint in the system.
Step 2 — Estimate
- 10K search requests/sec at peak (one autocomplete request per keystroke) - Average query length: 20 characters → 20 requests per search session in the worst case
- Top-K queries to track: top 10 million unique queries globally
- Trie storage: each node is ~16 bytes (character + children pointers + metadata) — a trie of 10M queries averages ~50M nodes × 16 bytes = 800 MB. Fits in memory on a single machine.
- Response size: 5–10 query strings, avg 30 bytes each = 300 bytes per response
The 800 MB insight is critical. The entire suggestion index for most production systems fits in memory. This is what enables sub-millisecond lookups.
Step 3 — Data Model and Core Data Structure
The trie
A trie (prefix tree) is the natural structure for autocomplete. Each node represents a character. A path from root to a node spells a prefix. Each node stores the top-K completions for that prefix.
root
└── ‘s’
└── ‘e’
└── ‘a’
├── ‘r’ → [”search engine”, “search bar”, “sear...”] ← top-5 stored here
└── ‘s’ → [”season”, “seasoning”, ...]
The key design choice: Pre-compute and cache the top-K results at every node in the trie. This trades storage for latency — instead of traversing to all leaf nodes on every query, the answer is stored at the prefix node. Query time: O(len(prefix)) — just traverse down the trie.
Without pre-computation: query time is O(all_suffixes) — must find all strings below the current node and rank them.
query_frequency table (offline aggregation source)
query_text, frequency_count, last_updated_at
This is the source of truth for what goes in the trie. Updated daily via a MapReduce / Spark job over the day’s search logs. The job counts query occurrences, normalizes (lowercase, trim), and writes the top-N queries per prefix into the trie build pipeline.
Step 4 — Architecture
Three components with different update cadences.
Query service (read path — latency-critical)
1. Client types a character → sends GET /suggest?q=sea
2. Request hits a load balancer → routes to one of N Trie servers (in-memory trie, sharded by prefix range or consistent hash)
3. Trie server traverses the trie in O(len(query)) time → returns top-5 cached completions 4. Response cached at CDN edge (short TTL — 60 seconds) for common prefixes (typing “the” returns the same results for everyone)
5. Total latency: < 10ms (CDN hit) or < 50ms (trie server hit)
Trie build service (write path — offline, daily)
1. Raw search logs → Kafka → Spark/Flink streaming job
2. Aggregation job computes top-10M queries by frequency for the trailing 7 days
3. Trie builder constructs a new trie from scratch and pre-computes top-K at every node 4. New trie serialized to S3
5. Trie servers download and hot-swap the in-memory trie (blue-green style — new trie loaded in background, traffic cut over atomically)
The hot-swap is the L5+ signal. Naive implementations rebuild the trie in place and serve stale or partially-built data during the rebuild. The correct approach: build the new trie entirely before serving any requests from it.
Trending query ingestion (real-time extension)
For real-time freshness (new trending query appears within minutes):
1. Search events stream to Kafka
2. A windowed aggregation job (5-minute tumbling window) identifies queries surging in frequency
3. Trending queries are injected into the trie via a small patch update (not a full rebuild)
4. Patch propagates to all trie servers via pub-sub
This is the L6 extension — daily batch covers the base case, real-time streaming handles trending. Name both.
Preparing for a distributed systems interview?
→Download the free Interview Pack
→ Subscribe now to access source code repository - 200 + coding lessons
