# System Design Interview: Design a Location-Based Services System (Yelp/Google Maps)

Source: https://www.techinterview.org/post/3233463178/system-design-location-based-services-geospatial/
Updated: 2026-04-17 · techinterview.org

## What Is a Location-Based Services System?

A location-based services (LBS) system enables geospatial queries: find nearby restaurants, show points of interest on a map, compute distances, and provide routing. Examples: Yelp (nearby search), Google Maps Places API, Foursquare. Core challenges: geospatial indexing for efficient proximity queries, handling moving objects (vehicles vs static POIs), and global scale (billions of GPS coordinates).

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-software-engineer-interview/)

- [Snap Interview Guide](https://techinterview.org/snap-software-engineer-interview/)

- [Airbnb Interview Guide](https://techinterview.org/airbnb-software-engineer-interview/)

- [DoorDash Interview Guide](https://techinterview.org/doordash-software-engineer-interview/)

- [Lyft Interview Guide](https://techinterview.org/lyft-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

## System Requirements

### Functional

  - Add/update/delete locations (businesses, POIs)

  - Search nearby: find N closest locations within radius R of a point

  - Filter: by category, rating, open hours

  - Geofencing: detect when a device enters/exits a defined area

### Non-Functional

  - 500M locations globally, 100K searches/second

  - Search latency <100ms

  - 1M location updates/second (for moving objects)

## Geospatial Indexing: Geohash

Geohash divides the world into a grid of cells using a base-32 encoded string. Longer hash = smaller cell. Precision: 6 chars ≈ 1.2km x 0.6km; 7 chars ≈ 153m x 153m. Properties: locations with the same geohash prefix are geographically close (mostly — boundary edge cases exist). Nearby cells share long common prefixes.


```
import geohash2

# Encode
hash = geohash2.encode(lat, lon, precision=7)  # e.g., "9q8yy"

# Search nearby: get the target cell + 8 neighbors
neighbors = geohash2.neighbors(target_hash)  # 8 surrounding cells
search_cells = [target_hash] + neighbors

# DB query
SELECT * FROM locations
WHERE geohash LIKE 'dp3wj%'  # all locations in cell
AND category = 'restaurant'
ORDER BY distance(lat, lon, ?, ?)
LIMIT 20
```

DB index on geohash prefix enables O(log N) range queries per cell. The 9-cell search (target + 8 neighbors) handles boundary cases where the nearest location is in an adjacent cell.

## Alternative: Quadtree

A quadtree recursively subdivides a 2D area into four quadrants until each leaf contains fewer than K points (e.g., K=100). Pros: adaptive density — dense cities get finer subdivision, sparse areas get coarser. Cons: complex updates (rebalancing on insert/delete), harder to distribute. Geohash is preferred for DB-backed systems; quadtree for in-memory spatial indexes (game engines, GIS tools).

## Data Model


```
locations: id, name, lat, lon, geohash7, category, rating,
           hours_json, address, created_at
location_tags: location_id, tag

-- Indexes:
CREATE INDEX ON locations (geohash7, category);
CREATE INDEX ON locations (geohash7, rating DESC);
```


## Search Flow

  - Compute target geohash at precision 7 (153m cell)

  - Get 8 neighbors

  - Query DB: WHERE geohash7 IN (9 cells) AND category = ? LIMIT 100

  - Compute exact distances (Haversine formula) for each result

  - Sort by distance, apply rating/filter, return top 20

  - If fewer than 20 results: expand to precision-6 cells (1.2km) and repeat

## Caching

Search results are highly cacheable: same query (location, radius, category) returns the same results for minutes. Cache key: "{geohash6}:{category}:{radius}". TTL: 60 seconds for static POIs (restaurants), 5 seconds for dynamic (drivers, riders). Redis stores the result set as a JSON array. Cache invalidation: when a location is added/deleted, invalidate all cells that overlap with it.

## Geofencing

Detect when a device enters or exits a polygon. Storage: store geofences as GeoJSON polygons in PostGIS. Point-in-polygon check: ST_Contains(geofence_polygon, ST_Point(lat, lon)). For 1M device updates/second: use geohash to pre-filter — only check geofences whose bounding box overlaps the device's geohash cell. This reduces polygon checks from all geofences to the few dozen in the local area.

## Interview Tips

  - Geohash + 9-cell neighbor search is the standard nearby-POI solution.

  - Haversine formula for great-circle distance — O(1), no index needed for final sort.

  - Adaptive radius expansion (precision 7 → 6 → 5) handles sparse areas.

  - PostGIS for complex geofencing; Redis GeoSet for simple radius queries.