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

By /
⏱ 5 min read

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
  • Snap Interview Guide
  • Airbnb Interview Guide
  • DoorDash Interview Guide
  • Lyft Interview Guide
  • Uber Interview Guide

    • 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

    1. Compute target geohash at precision 7 (153m cell)
    2. Get 8 neighbors
    3. Query DB: WHERE geohash7 IN (9 cells) AND category = ? LIMIT 100
    4. Compute exact distances (Haversine formula) for each result
    5. Sort by distance, apply rating/filter, return top 20
    6. 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.
    Scroll to Top