System Design Interviews, Step by Step · Classic Walkthroughs, Part 2
Design Search Autocomplete
Suggest the top completions as a user types, in under 100 ms. Precompute the top suggestions for every prefix from query logs, serve them from memory, and rebuild periodically.
The question
"Design the autocomplete for a search box: as the user types, show the five most popular queries that start with what they've typed."
Clarify the requirements
- Functional: top 5 suggestions for a prefix, ranked by popularity; filter offensive terms; suggestions can lag real trends by up to an hour.
- Scale: 10 million daily users, each searching ~5 times, typing ~6 characters before choosing.
- Non-functional: under 100 ms end to end (it must keep up with typing); highly available; English, lowercase, letters and spaces (we'll mention other languages).
Estimate the scale
- Keystroke requests: 10M × 5 × 6 = 300M/day ≈ 3,500/s, peak ~10,000/s. Clients debounce (wait ~100 ms after a keystroke), which cuts this a lot.
- Distinct queries worth suggesting: perhaps 10–20 million. Storing the top 5 for every prefix of those fits in a few GB of memory: replicate it on every serving node.
API and data model
GET /suggest?q=how+to+ma -> ["how to make pancakes", "how to make money online", ...]
query_counts (offline): query | count_last_7_days (from search logs)
serving index (in memory): prefix -> top 5 [(query, score)]
High-level design
┌──────────── offline, hourly ─────────────┐
search logs ─► aggregation job ─► build prefix index ─► publish snapshot
│
user typing ─► CDN / browser cache ─► suggest service (index in memory, many replicas)
The serving path is a memory lookup: no database, no computation at request time. All the heavy work (counting, ranking, building the index) happens offline and is swapped in as a new snapshot.
Deep dives
1. The data structure. A trie (prefix tree) stores each query along a path of characters. Searching the whole subtree for the best completions at request time is too slow for popular short prefixes ("a" has millions of completions), so each node caches its top 5 while the index is built. A lookup is then O(length of the prefix).
import heapq
class Node:
def __init__(self):
self.children = {}
self.top = [] # best (score, query) pairs under this prefix, precomputed
def build(query_counts, k=3):
root = Node()
for query, count in query_counts.items():
node = root
for ch in query:
node = node.children.setdefault(ch, Node())
node.top.append((count, query))
stack = [root] # keep only the k best at every node
while stack:
node = stack.pop()
node.top = heapq.nlargest(k, node.top)
stack.extend(node.children.values())
return root
def suggest(root, prefix):
node = root
for ch in prefix.lower():
node = node.children.get(ch)
if node is None:
return []
return [query for _, query in node.top]
counts = {
"how to make pancakes": 9000, "how to make money": 12000, "how to tie a tie": 7000,
"how to make slime": 3000, "hotel near me": 15000, "how tall is everest": 2500,
"python tutorial": 8000, "pizza near me": 20000,
}
index = build(counts)
for prefix in ["ho", "how to", "how to m", "p", "xyz"]:
print(f"{prefix!r:<11} -> {suggest(index, prefix)}")
Output
'ho' -> ['hotel near me', 'how to make money', 'how to make pancakes'] 'how to' -> ['how to make money', 'how to make pancakes', 'how to tie a tie'] 'how to m' -> ['how to make money', 'how to make pancakes', 'how to make slime'] 'p' -> ['pizza near me', 'python tutorial'] 'xyz' -> []
2. Building and shipping the index. An hourly job aggregates the last week of searches (recent days weighted more), drops rare queries and blocked terms, builds the trie, and writes a snapshot. Servers load the new snapshot in the background and swap it in atomically: no downtime and no partial index.
3. Latency tricks. Debounce on the client; cache responses for short prefixes in the browser and at the CDN (the top suggestions for "ho" are the same for everyone for an hour); prefetch the next likely prefix.
4. Trending queries. For breaking news, a small real-time layer counts the last few minutes of searches and blends sudden spikes into the results, while the hourly index remains the base.
Trade-offs
- Precomputed top-k vs search at request time: precomputing is fast and predictable but lags behind; request-time search is fresh but slow for short prefixes.
- Memory vs coverage: dropping rare queries keeps the index small; personalised suggestions need a separate per-user layer.
- Freshness vs stability: hourly rebuilds are simple; a streaming layer adds trends at extra complexity.
- Sharding the trie (by first letters) only if it outgrows a single server's memory, which is rare for the top-k version.
What interviewers look for
- A trie (or prefix map) with precomputed top-k per node.
- Separating the offline build from the in-memory serving path.
- Latency budget awareness: debouncing, caching, no database on the hot path.
- Filtering, freshness and how updates are swapped in safely.
Key points
- Serve suggestions from memory: prefix → precomputed top 5.
- Build the index offline from logs; swap snapshots atomically.
- Debounce and cache short prefixes in the browser and CDN.
- Add a small real-time layer for trends if freshness matters.
Practice questions
Why store the top-k suggestions at every trie node instead of searching the subtree on each request?
Answer
Short prefixes like 'a' have millions of completions; walking and ranking them per keystroke is far too slow. Precomputing the top k at each node during the offline build makes a lookup just a walk down the prefix: O(prefix length).
How does an autocomplete service update its suggestions without downtime?
Answer
An offline job rebuilds the index from recent query logs and writes a snapshot; each server loads the new snapshot in the background and swaps it in atomically, so requests always see either the old or the new complete index.
Open in the app to mark lessons complete, take notes and track your progress.