hard google · part of Practice Questions · Senior SWE Roadmap
Requirements to clarify
- Functional: given a location and radius, return nearby points of interest (restaurants, businesses); results should be reasonably fresh as POIs change.
- Non-functional: very low latency, high read volume, dataset can be huge (all POIs globally) but query results are always geographically local.
Core components
- Geospatial indexing: geohash (encodes lat/lng into a string where shared prefixes mean spatial proximity — easy to use as a shard/index key) or a quadtree (recursively subdivides space into quadrants, denser areas get finer subdivision) — both turn “find nearby” into an efficient range query instead of scanning all points.
- Sharding by location: since queries are inherently local, geohash prefixes or quadtree cells make natural, load-balanced shard keys.
- Caching: popular areas (city centers) get disproportionate query volume — a cache in front of the index absorbs hot spots (see Caching Strategies).
- Update pipeline: POI data changes (new businesses, closures) are ingested and periodically re-indexed, usually with acceptable staleness of minutes to hours.
Key tradeoffs
- Geohash is simpler to shard with (string prefix = proximity) but has edge cases at grid-cell boundaries; quadtrees adapt better to uneven data density but are more complex to shard.