Design Autocomplete for Search

Beginner Search & data structures

The problem

Design the autocomplete (type-ahead) feature of a search engine. As a user types, show the most useful completions for what they have typed so far.

You are in a 45-minute interview. The interviewer gave you only the sentence above.

The product is already running a search engine. You are adding the suggestion box.

Think of typing how t and seeing how to tie a tie, how to train your dragon, how to lose weight.

You are given

About 10 million users, each running about 10 searches a day.
Each search triggers about 5 suggestion requests while the user types.
There are about 100 million distinct queries worth suggesting, around 30 bytes each.
Suggestions must feel instant.

What we expect from you

Drive the conversation. Ask questions before drawing anything. State your assumptions out loud so they can be corrected early.
Use numbers. Turn the givens into requests per second, storage and bandwidth. Every later choice should point back to one of them.
Start simple, then evolve. Get a working version on the board first. Add caches, sharding and queues only when a number or a requirement asks for them.
Go deep on the hard parts. For this problem the hard parts are choosing the data structure, keeping lookups in memory and refreshing popular queries without slowing reads.
Name the trade-offs. Say what you chose, what you gave up, and what would make you change your mind.
Think about failure. Point out single points of failure and say what happens when a node, a cache or a whole zone goes down.

Scope

In scope

Returning ranked suggestions for a prefix
The data structure and how it is stored
Refreshing suggestions from search logs
Caching and scaling the read path

Not required

Spell correction and semantic search
Personalised suggestions per user
Building the search results page

Suggested time

Clarify requirements	4 min
Estimate scale	4 min
API and data model	5 min
High-level design	7 min
Deep dive	15 min
Reliability	5 min
Trade-offs and wrap-up	5 min

What makes an answer great

Chooses a trie with top-k per node and says why a SQL LIKE query fails.
Separates a read-only serving path from an offline build path.
Uses debounce and caching to cut load before it reaches the servers.
Says what staleness is acceptable.

Key concepts

Trie

A tree where each step down adds one character. Every node represents a prefix, so all words under a node share it.

Top-k

The k most popular results, pre-computed and stored at each node so a lookup does no ranking.

Debounce

Wait for a short pause in typing before sending a request, so fast typists send one request instead of five.

Eventual consistency

New data shows up after a delay. Fine for suggestions, wrong for a bank balance.

Numbers worth remembering

10M users x 10 searches x 5 keystrokes = 500M requests a day = about 6,000/s
Peak is usually 2 to 3 times the average
Round a day to 86,400 seconds (or about 100,000 for quick maths)

Locked in so far

Decisions you confirm will collect here as you go.

Your design so far