IntermediateSystem-Design
30 min
Design Search Autocomplete
SearchIRCachingML
Advertisement
Interview Question
Design an autocomplete service that suggests queries as users type, with personalization and typo tolerance.
Key Points to Cover
- Data structures: tries/prefix trees, FSTs, n-gram indexes
- Signals: popularity, personalization, context, seasonality
- Typo tolerance: edit distance, phonetic hashing
- Latency: in-memory shards, cache warmers, precompute
- Feedback loops: click/log-based re-ranking
Evaluation Rubric
Efficient prefix and typo-tolerant indexing25% weight
Signal-based ranking and personalization25% weight
Low-latency serving path and caching25% weight
Feedback loops and evaluation25% weight
Hints
- 💡Keep P99 under ~50ms at peak.
Potential Follow-up Questions
- ❓How do you handle banned terms?
- ❓How do you avoid query echo chambers?
Advertisement