How to Design Search Autocomplete (Typeahead)
Learn how to design search autocomplete: trie-based top-K prefix indexes, in-memory serving, sharding, and offline ranking refresh.
Expected Interview Answer
Search autocomplete is designed with a trie (or a precomputed top-K index per prefix) built offline from query logs, served from an in-memory cache so each keystroke returns ranked suggestions within tens of milliseconds.
An offline pipeline aggregates historical query frequencies, then builds a trie where each node stores the top-K most frequent completions for that prefix, avoiding an expensive tree traversal at request time. The trie (or a flattened prefix-to-suggestions map) is sharded across servers, often by first characters, and loaded into memory since disk lookups would be too slow for a sub-100ms budget. At request time the client debounces keystrokes and calls a lightweight API that looks up the prefix and returns cached top-K results, while a separate, less frequent batch job refreshes rankings from recent query trends. Personalization and trending-boost layers can be added on top, but the core system is a read-optimized, precomputed index rebuilt periodically rather than computed live.
- Precomputed top-K per prefix keeps latency low even under huge query volume
- In-memory tries avoid slow disk lookups on every keystroke
- Offline rebuilding keeps rankings fresh without slowing the hot read path
- Sharding by prefix lets the index scale horizontally across many servers
AI Mentor Explanation
Search autocomplete is like a scoreboard operator who has pre-written the most likely next commentary phrases for each situation, like “four runs” or “wicket”, instead of composing a sentence from scratch every ball. As soon as the bowler releases the ball, the operator just picks from a short pre-ranked list rather than searching every possible phrase in the dictionary, which is how a trie returns cached top-K completions instantly. Overnight, the broadcast team reviews which phrases were used most and reorders the pre-written list for tomorrow’s match, mirroring the offline rebuild of query rankings. This precomputed, ranked shortlist is what makes the commentary feel instant during live play.
Step-by-Step Explanation
Step 1
Aggregate query logs offline
A batch job counts historical query frequency to determine which completions are most popular per prefix.
Step 2
Build a trie with top-K per node
Each trie node caches its top-K most frequent completions, avoiding a full subtree scan at request time.
Step 3
Shard and load into memory
The trie is partitioned (often by first character(s)) and served entirely from memory across multiple servers for low latency.
Step 4
Serve and periodically refresh
The API returns cached top-K results per prefix on each keystroke, while a scheduled job rebuilds rankings from recent trends.
What Interviewer Expects
- Describes a trie (or equivalent prefix index) with precomputed top-K completions per node
- Explains why the index is built offline and served from memory for low latency
- Addresses sharding strategy for the trie across multiple servers
- Mentions debouncing on the client and a refresh cadence for trending changes
Common Mistakes
- Computing suggestions live by scanning all queries on every keystroke
- Ignoring the latency budget and using disk-backed lookups on the hot path
- Not addressing how the index stays fresh as new trends emerge
- Forgetting client-side debouncing, causing excessive requests per keystroke
Best Answer (HR Friendly)
“Search autocomplete works by precomputing the most likely search completions ahead of time, based on what people have searched for before, and storing them in a fast in-memory structure. When you type, the system just looks up your partial text and instantly returns the top pre-ranked matches instead of calculating anything from scratch.”
Code Example
class TrieNode:
def __init__(self):
self.children = {}
self.top_k = [] # list of (query, frequency), sorted desc, capped at K
def insert(root, query, frequency, k=5):
node = root
for ch in query:
node = node.children.setdefault(ch, TrieNode())
node.top_k.append((query, frequency))
node.top_k.sort(key=lambda x: -x[1])
node.top_k = node.top_k[:k]
def autocomplete(root, prefix):
node = root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
return [query for query, _ in node.top_k]Follow-up Questions
- How would you shard the trie across servers when the dataset is too large for one machine?
- How do you incorporate personalization or trending-query boosts without breaking the low-latency budget?
- How would you handle updating the trie in near real time for a rapidly trending query?
- What is the client-side strategy for reducing request volume while typing?
MCQ Practice
1. Why does autocomplete precompute top-K completions per trie node instead of computing them live?
Precomputing top-K per node lets each request do a simple lookup instead of scanning a subtree, keeping response times low.
2. Why is the autocomplete index typically served from memory rather than disk?
Autocomplete needs very low latency on every keystroke, and in-memory lookups are far faster than disk-backed ones.
3. What is the purpose of client-side debouncing in an autocomplete UI?
Debouncing waits for a short pause in typing before sending a request, cutting down on redundant calls for every single keystroke.
Flash Cards
What structure backs typical autocomplete systems? — A trie (or equivalent prefix index) where each node caches its top-K most frequent completions.
Why precompute top-K per prefix? — To avoid scanning subtrees live and meet the strict low-latency budget per keystroke.
How does the index stay fresh? — An offline batch job periodically rebuilds rankings from recent query logs and trends.
What does client-side debouncing do? — Delays firing a request until the user briefly pauses typing, reducing request volume.