Search Autocomplete System — System Design Interview

Phase 1: Clarify, Scope & Constraints

Interviewer: "Design a search autocomplete system — like what you see when you type in Google's search bar and a dropdown of suggestions appears. Where do you start?"

Candidate: "Let me clarify the scope. Autocomplete systems can serve many contexts: global search engines, e-commerce product search, social network user search, location/address search. The design varies significantly depending on the data set size and update frequency. Can you tell me the context?"

Interviewer: "Think Google Search scale. 10 billion queries per day. The suggestions should reflect currently trending searches."

Candidate: "That's the most interesting case — combining a massive static query corpus with real-time trend data. Let me identify the core user journeys:

1. Suggest: As the user types each character, return the top-K (typically 5–10) search query completions in < 100ms.
2. Trending: Suggestions should reflect recently trending searches (e.g., a breaking news event should bubble up within minutes).
3. Personalization (optional): Suggestions may be personalized based on the user's search history.

Non-goals for V1:

• Spelling correction / 'Did you mean?' (separate NLP problem)
• Personalized suggestions based on individual history (V2 feature)
• Multi-language or locale-specific suggestions (scope to English for V1)
• Query result ranking (autocomplete suggests queries, not answers)

Core complexity:

Two separate hard problems:

1. Read path: Must be extremely fast (< 100ms total, < 50ms for the autocomplete service itself) and handle massive QPS (millions of prefix queries per second at Google scale).
2. Write path: Aggregating billions of daily queries to maintain top-K completion candidates…