Geohashing & Spatial Indexing

Why This Comes Up in Interviews

Any system involving location — ride-sharing, food delivery, dating apps, store locators, real-time tracking — requires spatial indexing. Interviewers want to hear:

• Why latitude/longitude queries are inherently expensive without spatial indexing
• How geohashing converts 2D coordinates into 1D sortable strings
• Trade-offs between geohashing, quadtrees, and R-trees
• How precision levels map to real-world distances
• How systems like Uber/Lyft handle the "nearby" problem at scale

The Problem: Why Naive Approaches Fail

Query: "Find all restaurants within 1km of me" (lat: 37.7749, lng: -122.4194)

Geohashing Algorithm

Core idea: Recursively divide the world into grid cells. Encode each cell as a string. Nearby locations share common prefixes.

Encoding process for (37.7749, -122.4194):

Result: San Francisco = 9q8yyk... — any location in the same neighborhood shares the prefix 9q8yy.

Precision Levels

Interview rule of thumb: For "find nearby" features, precision 5-6 (1-5km) is typical. Adjust based on expected search radius.

Proximity Search Algorithm

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
graph TD
    QUERY["Query: Find drivers near (37.77, -122.41)"] --> ENCODE["Encode to geohash: 9q8yyk"]
    ENCODE --> SELF["Search cell 9q8yyk"]
    ENCODE --> NEIGHBORS["Search 8 neighboring cells"]
    NEIGHBORS --> N1["9q8yym"]
    NEIGHBORS --> N2["9q8yyj"]
    NEIGHBORS --> N3["9q8yys"]
    NEIGHBORS --> N4["9q8yy7"]
    NEIGHBORS --> N5["... (4 more)"]
    SELF --> MERGE["Merge results from all 9 cells"]
    N1 --> MERGE
    N2 --> MERGE
    N3 --> MERGE
    N4 --> MERGE
    N5 --> MERGE
    MERGE --> RANK["Rank by actual distance, return top K"]

    style QUERY fill:#3498db,color:#fff
    style MERGE fill:#27ae60,color:#fff
    style RANK fill:#f39c12,color:#fff

Why search neighbors? A location near a cell boundary might have closest results in an adjacent cell. Searching the center cell alone misses edge cases (literally).

Algorithm:

1. Compute geohash of query point at desired precision
2. Find 8 neighboring cell hashes (well-defined algorithm)
3. Query all 9 cells from database (single prefix query per cell)
4. Compute actual Haversine distance for results
5. Return top-K by real distance

Geohashing Edge Cases

Quadtrees — Adaptive Spatial Indexing

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
graph TD
    ROOT["World (root cell)"] --> NW["NW Quadrant"]
    ROOT --> NE["NE Quadrant"]
    ROOT --> SW["SW Quadrant"]
    ROOT --> SE["SE Quadrant"]
    NE --> NE_NW["NE-NW (sparse: leaf)"]
    NE --> NE_NE["NE-NE (sparse: leaf)"]
    NE --> NE_SW["NE-SW (dense: subdivide)"]
    NE --> NE_SE["NE-SE (sparse: leaf)"]
    NE_SW --> DEEP1["... (keep subdividing)"]

    style ROOT fill:#e74c3c,color:#fff
    style NE_SW fill:#f39c12,color:#fff
    style DEEP1 fill:#27ae60,color:#fff

When to use which:

• Geohash: Distributed systems (easy to shard by prefix), Redis/DynamoDB, simple proximity
• Quadtree: In-memory indexes, non-uniform data (cities vs rural), game engines
• R-tree: Complex shapes (polygons), range queries, traditional databases

Real-World Implementations

Back-of-Envelope: Uber Driver Matching

Sharding strategy: Partition by geohash prefix (first 3 chars = city-level). Each shard handles one metro area. Hot cities (NYC, SF) get dedicated shards.

Interview Framework

When designing location-based systems:

Step 1: "For the proximity search requirement, I'd use geohashing to convert 2D coordinates into 1D sortable strings. This lets us use standard database indexes for spatial queries."

Step 2: "At precision level 6 (~1.2km cells), I'd search the target cell plus its 8 neighbors — 9 cells total. This guarantees we catch all points within our search radius."

Step 3: "For non-uniform density (Manhattan vs suburbs), I'd consider Uber's H3 hexagonal grid — hexagons have equidistant neighbors and equal area, avoiding the square grid's corner-distance problem."

Step 4: "For sharding, geohash prefixes are natural partition keys. Prefix 9q8 covers San Francisco — all SF drivers on the same shard for fast local queries."

Step 5: "Driver locations update every 4 seconds. I'd use Redis GEO (geohash in sorted set) for real-time positions — O(log N) updates, O(log N + K) radius queries."

Quick Recall