📝 Problem Description
Design a location-based service like Yelp that finds nearby businesses. Support geospatial queries, filtering, ratings, and efficient proximity search at scale.
👤 Use Cases
1.
User wants to searches "coffee near me" so that sees nearby coffee shops
2.
User wants to filters by rating so that sees highly rated places
3.
Business wants to updates info so that changes reflected in search
4.
User wants to writes review so that rating updated
✅ Functional Requirements
- •Search businesses by location and category
- •Filter by rating, price, open now
- •Sort by distance, rating, relevance
- •Display business details, photos, reviews
- •Real-time open/closed status
- •Business owner can update info
⚡ Non-Functional Requirements
- •Search latency < 200ms
- •Support 200M businesses
- •Handle 100K searches/sec
- •Fresh data (< 5 min delay)
⚠️ Constraints & Assumptions
- •Geospatial queries are expensive
- •Hot areas (NYC, SF) are dense
- •Hours vary by timezone
📊 Capacity Estimation
👥 Users
100M daily users
💾 Storage
10TB (businesses, reviews, photos)
⚡ QPS
Search: 100K/sec, Writes: 1K/sec
📐 Assumptions
- • 200M businesses worldwide
- • 100M daily active users
- • 10 searches per user per day
- • 1B reviews total
- • Search radius: 1-10 km typical
- • Dense areas: 10K+ businesses per km²
💡 Key Concepts
CRITICAL
QuadTree
Recursive 2D subdivision for spatial indexing.
HIGH
Geohash
Encode lat/lng into sortable string for range queries.
MEDIUM
R-Tree
Balanced tree for spatial objects.
HIGH
Haversine Distance
Calculate great-circle distance on Earth.
💡 Interview Tips
- 💡Start with the geospatial indexing (QuadTree or Geohash)
- 💡Discuss the search ranking algorithm
- 💡Emphasize the importance of local caching
- 💡Be prepared to discuss review authenticity
- 💡Know the tradeoffs between different geo indexes
- 💡Understand how to combine location and text search