📝 Problem Description
Design an autocomplete system that suggests search queries as users type. Used by Google Search, Amazon product search, etc. Handle high QPS, personalization, and sub-100ms latency requirements.
👤 Use Cases
1.
User wants to types "app" so that sees suggestions like "apple", "application", "app store"
2.
User wants to selects suggestion so that search executes with that query
3.
System wants to detects trending query so that promotes in suggestions
✅ Functional Requirements
- •Return top 10 suggestions for prefix
- •Rank by popularity/relevance
- •Personalization based on user history
- •Handle typos and fuzzy matching
- •Support trending queries
⚡ Non-Functional Requirements
- •Latency < 50ms p99
- •Support 100K QPS
- •Index billions of queries
- •Real-time trending updates
⚠️ Constraints & Assumptions
- •Must be extremely fast
- •Prefix matching is primary use case
- •Cannot scan entire dataset per request
📊 Capacity Estimation
👥 Users
100M DAU
💾 Storage
100GB (query index)
⚡ QPS
100K suggestions/sec
📐 Assumptions
- • 100M DAU
- • Average 10 searches per day
- • Average 5 keystrokes per search triggering suggestions
- • ~50% keystrokes result in API calls (debounce)
- • 5B unique queries in index
- • Top 1M queries = 90% of traffic
💡 Key Concepts
CRITICAL
Trie Data Structure
Tree where each node represents a character. Enables O(L) prefix lookup where L is prefix length.
CRITICAL
Pre-computed Suggestions
Store top K suggestions at each trie node to avoid real-time aggregation.
HIGH
CDN Caching
Cache common prefixes ("app", "goo") at edge for sub-10ms response.
MEDIUM
Sampling and Aggregation
Use sampling to aggregate billions of search logs efficiently.
💡 Interview Tips
- 💡Start with the trie data structure
- 💡Discuss caching strategies early (CDN, Redis)
- 💡Emphasize the latency requirement (<50ms)
- 💡Be prepared to discuss ranking algorithms
- 💡Know the tradeoffs between freshness and performance
- 💡Understand how to handle trending queries