Question 12 · Track 4 · Find it
Design search autocomplete
You are not searching. You are reading a precomputed answer.
Find it. 4 clarifying questions to ask first, the answer in 4 moves, the follow-up that catches a memorised answer and 2 supporting topics to watch or read.
What it is really testing
Whether you move the work offline, and whether you understand a p99 latency budget of a few milliseconds.
Ask these first
Before a single box goes on the board. The answers change the design, which is the point of asking out loud.
- How many suggestions, and how fast must they appear?
- Do suggestions personalise per user?
- How quickly must a brand-new trending query appear?
- Do we have to filter offensive or unsafe suggestions?
The answer, in 4 moves
In this order. Each move earns the next one — say them out loud rather than drawing all four and narrating afterwards.
- 1Build a trie offline from real query logs, not from the document corpus.
- 2Precompute the top-K completions AT each prefix node — no ranking at request time.
- 3Cache hot prefixes at the edge; the first two characters are most of the traffic.
- 4Rank by frequency with a recency decay, and rebuild on a schedule.
The trap
The follow-up that separates a rehearsed answer from a real one.
Every millisecond of ranking you do per keystroke is multiplied by every keystroke of every user. If your answer contains the word "query" at request time, you have already lost the latency budget.
Watch or read
The pieces of this answer, each covered on its own. Take them whichever way suits you, then give the whole answer without looking.
Inverted indexes (FTS5)
You have 10,000 markdown notes and you search for 'postgres backup'. grep takes 400 ms and returns 40 files in folder order. SQLite FTS5 takes 3 ms and puts the right note first. Same files, same query — the difference is an inverted index and BM25 ranking. Here's how both actually work, the negative-score gotcha everyone hits once, the staleness trap of a derived index, and where lexical search ends and vector search begins — including why RAG pipelines still run BM25 next to embeddings.
Cache vs CDN
Cache and CDN both store copies for faster reads, but solve different problems: cache cuts backend work for dynamic data; CDN cuts network distance for static content. Learn when to use each.
Part of System Design Interviews, Answered Out Loud. The fundamentals underneath it are the free CS course.