SYSTEM DESIGN · QUESTION 107
How would you design a search autocomplete system?
On this page
I would clarify corpus size, freshness, personalization, and latency targets, then serve prefix or typo-tolerant suggestions from an indexed candidate source. A request can query a local or distributed trie, FST, or search index, rank candidates using popularity and context, and cache common prefixes. Debounce client requests, limit result counts, and protect the index with updates and fallback behavior.
LET'S MAKE IT SIMPLE
First, the idea in plain English
Autocomplete returns suggestions while someone is still typing. It must respond quickly with a small useful list, even though the full search corpus may be large. The system can precompute prefix candidates, retrieve likely matches, rank them, and refresh popular suggestions as usage changes.
A USEFUL COMPARISON
Picture it this way
A librarian hears the first few letters of a title and quickly offers likely books from a prepared index. The index must be compact and updated; searching every book from scratch after each keystroke would be too slow.
FOLLOW THE JOURNEY
Retrieve and rank suggestions for each query prefix
Trace keystrokes through request control, candidate lookup, ranking, and response.
This simplified visual highlights the main relationships. In practice, the exact design depends on the requirements; Short responses support interactive latency.
A client debounces typed prefixes, an autocomplete service retrieves candidates from an index and cache, ranks a small set, and returns suggestions.
How to read this visual
This simplified visual highlights the main relationships. In practice, the exact design depends on the requirements; Short responses support interactive latency.
UNDER THE HOOD
How it works, step by step
Control request volume
Debounce keystrokes and cancel stale client requests.
Why it matters: Typing can otherwise create many obsolete queries.
Retrieve candidates
Use a prefix index, FST, or search engine for matching suggestions.
Why it matters: Precomputed structures avoid scanning the full corpus.
Rank and filter
Apply popularity, recency, locale, and policy constraints.
Why it matters: Matching strings alone do not produce useful suggestions.
Return bounded results
Send a small list with caching and fallback behavior.
Why it matters: Short responses support interactive latency.
OUTSIDE THE TEXTBOOK
A practical example
A shopping site suggests product names from a catalog as the user types. The service uses a prefix index, ranks by relevance and current availability, filters prohibited or private items, and caches common prefixes. Catalog updates flow into the index asynchronously, with a fallback to recent popular suggestions during rebuilds.
GO A LITTLE DEEPER
Technical details that matter
- Tries provide prefix lookup; finite-state transducers can compress large dictionaries; inverted indexes can support richer matching.
- Personalization requires privacy-aware cache keys and can reduce cache hit rates.
- Typo tolerance and multilingual tokenization increase index and ranking complexity.
MAKE A GOOD CHOICE
When is this useful?
- Product, documentation, and site-search suggestions.
- Command palettes with a bounded set of actions.
- Search interfaces where latency during typing affects usability.
For a small corpus, a database index or in-memory prefix map may be sufficient. Avoid a distributed search platform before measurements justify it.
WATCH OUT FOR
Common misunderstandings
- Sending a backend request for every keystroke without cancellation.
- Ranking only by global popularity and ignoring query relevance.
- Caching personalized results without including user or permission context.
REAL-WORLD TRADE-OFFS
Limitations and failure cases
- Indexes can lag behind catalog changes.
- Personalized ranking can create privacy and cache complexity.
- Low-latency requirements may constrain typo handling and expensive ranking.
WHAT TO REMEMBER
Key takeaways
- 1Autocomplete is a latency-sensitive retrieval and ranking problem.
- 2Debounce and cancel stale requests.
- 3Balance index freshness, relevance, privacy, and cache behavior.
PRACTICE THE FOLLOW-UP
What might an interviewer ask next?
How would you handle stale suggestions?
Version or refresh the index, apply availability checks where needed, and define an acceptable update lag and fallback behavior.
How can you support typo tolerance?
Use edit-distance or n-gram candidate retrieval and rank candidates, while controlling index size and latency.
SAY IT OUT LOUD
How to explain this in an interview
“I would clarify corpus size, freshness, personalization, and latency goals. The client debounces keystrokes, and a service retrieves candidates from a prefix-oriented index or FST, ranks a small set, and caches safe common queries. I would handle index updates and permission-aware results, and measure latency and relevance together.”
Connect this question to the roadmap topic it supports.