This gives away every stage. For a clean attempt, practise it first, then come back.
The short version
- Suggestions must feel instant, so everything is served from memory. No database on the read path.
- A trie with the top 5 stored at every node turns each keystroke into a few steps and one read.
- Build the trie once a day from search logs, and add a small fast layer for what’s trending.
- Most requests can be avoided: the app waits briefly between keys, and short prefixes are cached for everyone.
- Count people, not searches, and filter blocked terms twice, so nobody can push a phrase to the top.
The 45 minutes
Before we start
Start typing “cri” into a search box and you’ll see “cricket score”, “cricket world cup” and so on, before you’ve finished the word. Every letter you type sends a new request, and the answer has to come back before your next keystroke.
That’s the challenge: huge numbers of tiny requests that must be answered almost instantly, using data built from what millions of other people searched. The interview tests whether you see that the hard work should happen before anyone types, not while they’re typing.
Same order as always: requirements, quick maths, data and API, a design that grows, then deep dives.
Minutes 0–5Requirements
Interviewer: Design search autocomplete for Chirp. As someone types, show the top 5 suggestions based on what other people search.
You: What are we suggesting: past searches, people, hashtags?
Interviewer: Popular search queries. People and hashtags can come later.
You: How many people search, and how much do they type?
Interviewer: 50 million daily users, about 10 searches each. A search is around 6 keystrokes.
You: How fast must suggestions appear?
Interviewer: They should feel instant. Under 100 milliseconds from keystroke to screen.
You: How fresh? If something starts trending, how soon should it show up?
Interviewer: Daily is fine for most things, but a breaking trend should show within about 15 minutes.
You: Are suggestions personal?
Interviewer: Nice to have: your own recent searches first. The main list is the same for everyone.
You: Anything we must filter out?
Interviewer: Offensive or harmful suggestions must never appear. And people shouldn’t be able to push a phrase up by searching it over and over.
Functional requirements
- As the user types, return the top 5 suggestions that start with what they’ve typed.
- Rank suggestions by how popular they are.
- Keep suggestions up to date from what people search, including fast-moving trends.
- Never show offensive or blocked suggestions.
Nice to have: show the user’s own recent searches first. Out of scope: spelling correction and the actual search results page.
Non-functional requirements
- Instant: suggestions on screen within about 100 ms. After the network, the server gets maybe 20 ms.
- Big: about 3 billion suggestion requests a day, around 100,000 a second at the busiest time.
- Fresh: daily updates in general, and trends within about 15 minutes.
- Safe to fail: if suggestions break, the search box still works. Autocomplete is a helper.
- Hard to game: a few people searching one phrase thousands of times shouldn’t move it up.
Minutes 5–10Back-of-the-envelope estimates
You: 50 million users times 10 searches is 500 million searches a day, about 5,800 a second.
You: Each search is about 6 keystrokes, and each keystroke can ask for suggestions, so roughly 35,000 suggestion requests a second, maybe 100,000 at the busiest time.
You: For the data: say we keep the 10 million most popular queries, about 20 characters each. Queries share beginnings (“cricket score” and “cricket world cup” share “cricket “), so we end up with around 60 million prefixes. At about 120 bytes each, that’s roughly 7 GB.
You: 7 GB fits in a single server’s memory. So every server can hold everything, and we never touch a database while someone is typing.
Two conclusions: it all fits in memory, and we’ll have a huge number of tiny, repetitive requests. Both shape everything that follows.
Minutes 10–15Core entities and the API
Core entities
- Search: what someone searched and when. These come in as a stream from the search service.
- Query count: for each query, how many different people searched it, per day.
- Suggestion list: for each prefix (“c”, “cr”, “cri”…), the top 5 queries that start with it.
The API
/v1/suggest?q=cri&limit=5Top suggestions for what’s been typed so far.
- 200
{ "suggestions": ["cricket score", "cricket world cup", "crispy dosa", "crime news", "crichton"] }
That’s the whole public API, and two things about it matter. It’s a GET with everything in the URL, so browsers and CDNs can cache it. And it returns the same answer for everyone typing “cri”, which makes caching even more effective.
Minutes 15–25The design, built up
Stage 1Search the database as they type
You: The simplest version: a table of queries and how many times each was searched. On every keystroke, run a query like WHERE query LIKE ‘cri%’ ORDER BY count DESC LIMIT 5.
It works for a small app. But every keystroke now scans part of a table and sorts the results. At 100,000 requests a second, the database can’t keep up, and the 20 ms budget is long gone.
Stage 2A trie in memory, with the top 5 ready at every node
You: Better: build a trie and keep it in memory. A trie is a tree where each step down adds one letter. Everything starting with “cri” sits under one node.
You: And the important trick: when we build the trie, we store the top 5 suggestions at every single node. A request walks down three nodes, c, r, i, and reads a list that’s already sorted. No searching, no sorting.
You: A daily job builds the trie from search counts and saves it. Suggestion servers load it into memory. Since it’s only about 7 GB, every server holds a full copy, and we add servers to handle more traffic.
See why storing the top 5 matters:
Stage 3A pipeline from search logs, plus a trending layer
You: Where do the counts come from? Every time someone completes a search, the search service writes a small event to a queue. Two things read it.
You: A daily builder counts the day’s searches, filters out blocked terms and rarely searched queries, builds a fresh trie with the top 5 at each node, and saves it to object storage. Servers load the new one and swap it in.
You: For trends, a stream counter keeps counts for the last 15 minutes. Suggestion servers mix a small trending list into their answers, so a breaking story shows up quickly without waiting for tomorrow’s build.
Two speeds for two needs: slow and thorough for the bulk, fast and small for what’s new. (Queues are covered in lesson 4.1.)
Stage 4Fewer requests: wait between keys, cache short prefixes
You: The cheapest request is one we never receive. Three things cut traffic a lot.
You: The app waits about 150 ms after each keystroke before asking. If you’re typing fast, it only asks once you pause. It also cancels requests you’ve typed past, and remembers answers it already has, so deleting a letter costs nothing.
You: Short prefixes like “c” or “cr” are asked for millions of times, with the same answer for everyone. A CDN can cache those for a minute, right next to users.
Waiting between keystrokes alone removes about half of all requests. (Lesson 2.3 covers CDNs.)
Checking the design against the requirements
| Requirement | Where the design handles it |
|---|---|
| Top 5 as you type | Trie in memory, top 5 stored at every node |
| Ranked by popularity | Counts from search logs, built into each node’s list |
| Up to date, including trends | Daily builder plus a 15-minute trending layer |
| No offensive suggestions | Filtered when building and again when serving |
| Instant | Everything in memory; a few steps and one read per request |
| Big | Full copy on every server; device waiting and CDN caching cut traffic |
| Fresh | Daily build; trends within 15 minutes |
| Safe to fail | Search works without suggestions; the app just shows none |
| Hard to game | Counting distinct people per query, with a minimum threshold |
Deep diveFinding the top 5 fast
Interviewer: Why store the top 5 at every node? Isn’t that wasteful?
Bad solutionSearch a table on every keystroke
LIKE 'cri%' plus sorting. Fine for thousands of queries, far too slow for millions, and the database is on the path of every keystroke.
Good solutionA trie, searched at request time
Walk down to the “cri” node, then visit every query below it and sort by popularity. Fast for long prefixes with few queries below them. But a one-letter prefix like “c” has millions of queries under it, and that’s exactly what people type first.
Great solutionA trie with the top 5 already stored at each node
Do the sorting once, when building. Every node keeps its own top 5. A request is a few steps down and one read, whether the prefix has ten queries below it or ten million. The cost is extra memory (about 7 GB in total) and a nightly build, both easily affordable.
Deep diveKeeping suggestions fresh
Interviewer: Why not update the trie every time someone searches?
You: That would put writes on the path that has to be fastest, and every server would need every update. It also lets a sudden burst of searches move suggestions instantly, which is how manipulation works.
You: So most of the freshness comes from the daily rebuild, and only trends get the fast path.
Bad solutionUpdate the trie live on every search
Writes on the read path, constant locking, and easy to manipulate.
Good solutionRebuild every day and swap
A daily job counts, filters and builds, and servers swap in the new trie. Simple and safe, but a story that broke this morning won’t appear until tomorrow.
Great solutionDaily rebuild plus a trending layer
Keep the daily rebuild for the bulk. Add a stream job that counts searches in 15-minute windows, and let servers blend in a small trending list for each short prefix, with older counts fading out. Fresh where it matters, cheap everywhere else.
Deep dive100,000 requests a second
Interviewer: How do you handle that much traffic?
You: Mostly by not receiving it. The app waits about 150 ms between keystrokes before asking, cancels requests the user has typed past, and keeps answers it has already seen. That removes roughly half the requests.
You: Then cache shared answers. Everyone typing “cr” gets the same five suggestions, so short prefixes can be cached at the CDN for a minute.
You: What’s left goes to suggestion servers, each holding the whole trie. To handle more, add more servers. No splitting needed while it fits in memory.
Interviewer: And if it stops fitting?
You: Then split it by prefix range across groups of servers. But not alphabetically: far more queries start with “s” than with “x”. Split by measured size so every group gets a fair share.
That uneven spread is the same problem lesson 5.1 covers for databases (partitioning).
Deep diveBlocking bad suggestions and stopping manipulation
Interviewer: How do you keep offensive suggestions out, and stop people gaming it?
You: Check a block list twice: when building the trie, so blocked terms never get in, and again when serving, so a term we block today disappears immediately instead of tomorrow.
You: Count people, not searches. If ten people search one phrase a thousand times each, that should count as ten, not ten thousand.
You: And require a minimum number of different people before anything is suggested at all. That also keeps private things, like someone’s phone number that a few people searched, out of everyone’s suggestions.
Deep diveMy recent searches first
Interviewer: How would you show my own recent searches?
You: Keep them on the device. When suggestions arrive, the app puts your matching recent searches first and fills the rest from the shared list. The server’s answer stays the same for everyone, so it stays cacheable. If recent searches must follow you across devices, keep a short list per user on the server and merge the same way.
The complete architecture
Here’s everything together: the full design from the last stage, with every part we added along the way. If you only remember one picture from this question, make it this one.
How one request travels through it:
- You type ‘cri’. The app waits about 150 ms; if you keep typing, it cancels and waits again. It also remembers answers it has already fetched.
- Short, common prefixes are answered by the CDN, because everyone typing ‘cri’ gets the same suggestions.
- Otherwise a suggestion server walks its in-memory trie to the ‘cri’ node, where the top 5 are already stored. No sorting, no database.
- It mixes in anything trending in the last 15 minutes for that prefix, removes blocked terms, and replies.
- Meanwhile every completed search is logged to a queue. A stream counter keeps 15-minute counts for trends, and a daily job builds a fresh trie from the day’s counts.
- The new trie is saved to object storage, and servers load it and swap it in without restarting.
How this answer gets scored
Interviewers don’t tick boxes, but their notes on this question tend to land on the same few moments. Here’s what each one sounds like from the other side of the table.
| Moment | What earns credit | What costs you |
|---|---|---|
| The first five minutes | Asking about speed and freshness separately | Assuming suggestions must update in real time |
| The numbers | Noticing the whole thing fits in memory | Sizing a database cluster for a 7 GB dataset |
| Data structure | A trie with the top 5 stored at each node | A database query on every keystroke |
| Freshness | A daily build plus a small trending layer | Updating the trie on every search |
| Traffic | Waiting between keys, caching short prefixes | Sending a request on every keystroke |
| Safety | Block list at build and serve time; counting people | Counting raw searches |
What the left column has in common: every choice points back to a requirement or a number from earlier. If you can say where each box came from, the interviewer will notice.
Stay in the loop
Get new problems and walkthroughs by email
One short email when something new is published: a deep-dive walkthrough, an LLD problem, or a real outage retold. No spam, unsubscribe any time.