Proximity / Geo Search
Difficulty: Hard | Topic #27
What to Learn
Geohashing (encoding lat/lng into a string prefix), quadtrees for dynamic data, PostGIS for polygon queries, radius search with grid cells, nearest-neighbor search.
Resources
- Hello Interview: Proximity Search Deep Dive ↗
- ByteByteGo: Design A Location Based Service ↗
- Gaurav Sen: Geohashing Algorithm — Proximity Search ↗
Covered by Problems
| Problem | Difficulty | Link |
|---|---|---|
| Local Business Reviews (Yelp) | Easy | → |
| Local Delivery Service | Easy | → |
| Dating App (Tinder) | Medium | → |
| Ride Sharing (Uber) | Hard | → |
Key Concepts to Master
- Geohash encoding — how string prefix defines a bounding box
- Geohash precision levels and their coverage area
- Quadtree for dynamic point data (driver locations)
- Expanding search radius by querying neighboring geohash cells
- PostGIS ST_DWithin for exact distance queries on polygon data