Type “bin” into a search box and suggestions appear before you finish the word. “Design search autocomplete” (typeahead) is a frequently reported question at Google, Amazon and Microsoft. It's a beautiful example of a data structure deciding the architecture: once you pick a trie with precomputed answers, the rest of the design follows.
Step 1 · Requirements
- Functional: as the user types, show the top 5 most popular queries starting with that prefix.
- Non-functional: very fast (under ~100 ms end to end, so it feels instant); highly available; suggestions reasonably fresh (daily is fine, trending can be faster); safe.
- Clarify: English only? Personalised? Spelling correction? (Say: start global and unpersonalised, mention the rest as extensions.)
Step 2 · Estimates
- Searches: 100 million daily users × 10 searches × ~6 characters typed ≈ 6 billion prefix requests a day ≈ 70,000/s, more at peak. Debouncing and caching cut this a lot.
- Trie size: keep the top ~100 million distinct queries; with shared prefixes and top-5 lists per node, tens of GB. It fits in memory on a few large servers, so replicate it.
Step 3 · API
GET /suggest?q=bin&limit=5 → ["binary search", "binary tree", "binary search tree", ...] Cache-Control: public, max-age=3600 // short prefixes are the same for everyone
Step 4 · Design
The data structure: a trie with top-k at every node
🎮 Walk the trie as you type
1 step down the trie for 1 letter.
- binary search9,200/wk
- big o notation8,100/wk
- binary tree7,000/wk
- bfs vs dfs6,500/wk
- binary search tree5,000/wk
Notice the work per keystroke is just one step down the trie plus reading a precomputed list. It doesn't matter how many millions of queries exist.
A plain trie would find the “bin” node and then search its whole subtree for the most popular completions: slow for short prefixes like “b” with millions of descendants. Storing the top 5 at each node costs memory but makes every lookup O(length of prefix).
K = 3 # suggestions to show
class Node:
def __init__(self):
self.children = {}
self.top = [] # best K (count, word) pairs for this prefix, precomputed
class Autocomplete:
def __init__(self):
self.root = Node()
def add(self, word: str, count: int):
node = self.root
for ch in word:
node = node.children.setdefault(ch, Node())
# Keep this prefix's top K up to date: highest count first, then A-Z
node.top = sorted(node.top + [(count, word)], key=lambda t: (-t[0], t[1]))[:K]
def suggest(self, prefix: str) -> list[str]:
node = self.root
for ch in prefix: # O(length of prefix): one step per letter
if ch not in node.children:
return []
node = node.children[ch]
return [w for _, w in node.top] # already sorted, no searching needed
ac = Autocomplete()
for word, count in [("binary search", 900), ("binary tree", 700), ("bfs vs dfs", 650),
("big o notation", 800), ("binary search tree", 500), ("bubble sort", 300)]:
ac.add(word, count)
print(ac.suggest("b")) # ['binary search', 'big o notation', 'binary tree']
print(ac.suggest("bin")) # ['binary search', 'binary tree', 'binary search tree']
print(ac.suggest("bu")) # ['bubble sort']Two paths: building and serving
- Data path (offline): log every search, count queries over a window (e.g. last 7 days, weighting recent days more), build a fresh trie, store a snapshot, and roll it out to servers.
- Query path (online): read-only and in memory, so it's simple, fast and easy to replicate. Nothing on this path writes.
Step 5 · Scale and reliability
- Debounce on the client: wait ~100–200 ms after typing stops before sending a request.
- Cache in layers: browsers keep recent prefixes; one- and two-letter prefixes are identical for everyone, so cache them at the CDN.
- Replicate: the trie is read-only, so run many identical copies behind a load balancer.
- Shard if too big: split by prefix range (a–f, g–m…), but balance by traffic, not letters: many more queries start with “s” than “x”.
- Trending: a small streaming job counts searches over the last few minutes and boosts sudden spikes (a cricket match, breaking news).
- Personalisation: blend global suggestions with the user's own recent searches on the client or in a separate service.
🧠 PATH memory card
Remember the autocomplete design for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
An old library card catalogue: drawer B, then the I section, then N. Pinned to the front of each section is a card listing its five most-borrowed titles, so you never flip through every card. Each night the librarian rewrites those front cards from the day's borrowing records, and photocopies of the catalogue sit on every floor.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Every letter is a step down the trie; every node keeps its top 5”
- Every letter is a step→Lookup is O(length of prefix)
- Top 5 at every node→Precomputed top-k: no subtree search
- Refile at night→Offline rebuild from aggregated search logs
- Photocopies→Read-only trie replicated; caches at browser and CDN
- Front card checked→Filter unsafe suggestions before serving
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
User typesb: a one-letter prefix, so the CDN cache answers with the b node's top 5 (binary search, big o notation, binary tree…). Typesi,nquickly: debounced into one request forbin→ server walks root → b → i → n (3 steps) → returns that node's stored top 5 in microseconds. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 8 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Follow-up questions interviewers ask
- “Typos?” Add fuzzy matching (edit distance) for longer prefixes, or a separate “did you mean” service.
- “Multiple languages?” One trie per language or region; tries work with any characters.
- “Why not just query the database with LIKE 'bin%'?” It can't rank by popularity fast enough at 70,000 requests per second. The trie answers from memory in microseconds.
Where to go next
Autocomplete needs to know what people search. A search engine also needs to know what's on the web. Next, the system that reads billions of pages: design a web crawler. Brush up on trees if tries felt new.
Key takeaways
- ✓Use an in-memory trie; finding a prefix takes one step per letter.
- ✓Store the top-k suggestions at every node so reads need no searching.
- ✓Build the trie offline from aggregated logs; keep the serving path read-only.
- ✓Debounce keystrokes and cache common prefixes in the browser and at the CDN.
- ✓Replicate the trie, shard by traffic-balanced prefix ranges, and filter unsafe suggestions.
Frequently asked questions
How does search autocomplete work?
As you type, the app sends the current prefix (for example 'bin') to a suggestion service. The service looks the prefix up in a trie, a tree where each letter is one step down, and returns the most popular complete queries that start with it. To make this instant, each trie node stores its top suggestions in advance, and results are cached in the browser, a CDN and the service.
Why is a trie used for autocomplete?
A trie stores strings by shared prefixes: all queries starting with 'bin' sit under the same node. Finding that node takes one step per letter typed, no matter how many queries exist. Storing the top-k suggestions at every node means the answer is ready the moment the node is reached, with no searching through the subtree.
How are autocomplete suggestions kept up to date?
Search queries are logged, then a batch job (for example daily or weekly) counts how often each query was searched, builds a new trie with the top suggestions per prefix, and swaps it into the serving machines. Trending topics can be added faster with a separate real-time pipeline that counts recent searches over short time windows.
How does autocomplete handle so many requests?
Each keystroke can be a request, so the client waits briefly (debouncing, about 100–200 ms) before sending, browsers cache recent prefixes, popular short prefixes are cached at the CDN and in memory, and the trie is copied across many servers or split by prefix range. The trie lives in memory so a lookup takes microseconds.
How are offensive or unsafe suggestions removed?
A filter layer checks suggestions against blocklists and policy classifiers before they are served, and removed queries are excluded when the next trie is built. Because suggestions are shown to everyone, this filtering is a required part of the design, not an afterthought.
🧠 Quick check: search autocomplete
1. Finding the trie node for the prefix “bin” takes how many steps?
2. Why store the top 5 suggestions at every trie node?
3. A user types “binary” quickly: 6 keystrokes in half a second. What reduces wasted requests?
4. How do new popular searches get into the trie?
Checking your access…