Design: Maps & Navigation (Google Maps)¶

Difficulty: Senior → Staff | Time: 60–75 minutes

1. Problem Statement¶

Design a mapping and navigation service: a user requests a route from point A to point B, the system returns the fastest path along with turn-by-turn directions and an ETA, the map itself renders as pannable/zoomable tiles, and ETAs stay accurate as live traffic changes the fastest path minute to minute.

The ride-hailing exercise is the closest thing on this site to this one, and it's tempting to reuse its answer wholesale — it isn't the same problem. Ride-hailing's hard query is "who are the K nearest moving points to this point, right now?" — a nearest-neighbor search over a set of independent points, solved with geohash cells. This exercise's hard query is "what is the cheapest path through a graph of a billion edges, where edge weight changes continuously?" — a shortest-path problem, not a nearest-neighbor problem. Finding a driver near you and finding the fastest way from you to somewhere across a continent are different data structures with different failure modes: nearest-neighbor degrades with point density, shortest-path degrades with graph size and staleness of edge weights. Say this distinction early — reusing geohash intuition here (e.g. "just index road segments into geohash cells and scan nearby ones") solves point-location but does nothing for the actual graph-traversal cost, which is where this design lives or dies.

Road-segment spatial indexing (which tile or region a segment belongs to) does reuse ride-hailing's geo-partitioning ideas — reference that page rather than re-deriving it. What's new here is everything downstream of "I've found the relevant part of the graph": how you traverse billions of edges fast enough for a sub-200ms budget, and how you keep edge weights honest against traffic that changes every few seconds.

2. Clarifying Questions¶

3. Functional Requirements¶

• Compute the fastest route between two points, with turn-by-turn directions
• Serve renderable map tiles for panning/zooming at multiple zoom levels
• Ingest live location "breadcrumbs" from phones in transit as traffic probe data
• Reflect current traffic conditions in both the route chosen and the ETA shown
• Re-route or update ETA when conditions change materially mid-trip
• Support alternate routes (fastest, avoid tolls/highways)

4. Non-Functional Requirements¶

5. Capacity Estimation¶

Road graph (global, driving-capable roads):
  ~700M road segments worldwide (OpenStreetMap-scale estimate)
  Each segment ≈ an edge; intersections ≈ nodes
  ~350M nodes, ~800M directed edges (segments are often one-way, or bidirectional = 2 edges)
  Per-edge storage: from_node(8B) + to_node(8B) + weight(4B) + geometry_ptr(8B) + road_class(1B) ≈ 30B
  800M edges x 30B ≈ 24 GB for the raw graph — fits in a single big-memory host,
    but NOT after adding precompute structures (see V2) which multiply this several-fold

Route requests:
  ~50M route requests/day globally → ~580/s average, ~6,000/s at rush-hour peak
  Each request: 1 shortest-path query over the relevant regional subgraph

Tile requests:
  Every pan/zoom/app-open fetches multiple tiles; billions/day globally
  ~2B tile requests/day → ~23,000/s average, ~150,000/s peak (evening commute + weekend travel)
  Tiles are near-static (road geometry changes slowly) → this is a caching problem, not a compute one

Traffic probe ingestion:
  Assume ~5% of active phones running the app or OS-level location sharing report a breadcrumb every ~10-15s
  100M concurrent-ish active devices globally (conservative) x 5% x (1 ping / 12s) ≈ 415,000 probes/second
  Each probe: ~40 bytes (device_hash, lat, lng, speed, heading, ts) → ~17 MB/s raw ingest
  This is the graph's "hot, constantly-mutating" workload — same shape as ride-hailing's driver pings,
    but here it feeds *edge weights*, not point positions on a map

6. API Design¶

# Routing
GET /v1/routes?origin=lat,lng&destination=lat,lng&alternatives=2&avoid=tolls
  → 200 {
      "routes": [{
        "route_id": "rt_abc",
        "distance_m": 14200,
        "duration_s": 1080,
        "duration_in_traffic_s": 1340,
        "legs": [{ "instruction": "Turn right onto Main St", "distance_m": 300, ... }],
        "polyline": "encoded_geometry..."
      }]
    }
  → 400 if origin/destination unreachable, 503 if routing service degraded

# Tiles
GET /v1/tiles/{z}/{x}/{y}.pbf         # vector tile, standard z/x/y scheme
  → 200 tile bytes, Cache-Control: public, max-age=604800 (topology-only tiles)
  → 404 if out of bounds

# Live traffic probes (fire-and-forget, high volume)
POST /v1/probes
  { "device_hash": "d_9f2a", "lat": 37.77, "lng": -122.41, "speed_mps": 4.1, "heading": 90, "ts": 1755400000 }
  → 202 Accepted (never blocks the client on ingestion success)

# Live re-route / trip session
WS /v1/trips/{trip_id}/stream          # pushes updated ETA / re-route if conditions change materially

7. Data Model — road graph storage, spatial partitioning, and tile storage¶

Road graph. An adjacency-list representation: each node (intersection) stores outgoing edges (road segments), each edge stores a base weight (free-flow travel time), geometry (for rendering/instructions), and road class (highway vs residential — used both for weighting and for "avoid highways" filters).

-- Cold, durable graph source-of-truth (updated on the map-data refresh cadence, not per-request)
CREATE TABLE nodes (
    node_id      BIGINT PRIMARY KEY,
    lat          DOUBLE NOT NULL,
    lng          DOUBLE NOT NULL,
    region_id    INT NOT NULL,          -- spatial partition, see below
    INDEX idx_region (region_id)
);

CREATE TABLE edges (
    edge_id      BIGINT PRIMARY KEY,
    from_node    BIGINT NOT NULL REFERENCES nodes,
    to_node      BIGINT NOT NULL REFERENCES nodes,
    base_weight_s INT NOT NULL,          -- free-flow travel time, from speed limit + length
    road_class   SMALLINT NOT NULL,
    geometry     GEOMETRY NOT NULL,
    INDEX idx_from (from_node)
);

Spatial partitioning of the graph. The graph is partitioned into regions (roughly: countries, or sub-national tiles for large countries) so that (a) a route within one metro area never touches unrelated continents' data in memory, and (b) precompute jobs (V2) can run per-region in parallel and refresh independently. This is the same instinct as ride-hailing's per-city sharding — bound the blast radius of both storage and compute by geography — but here the partition boundary is a real complication the driver-matching problem never had: routes cross region boundaries constantly (a highway trip spans several regions), so regions need overlapping border buffers and a stitching step at query time, not the clean "a rider in Austin never matches a driver in Tokyo" independence ride-hailing enjoys.

Live edge-weight overlay (kept separate from the base graph — critical for V2/V3):

Hot store (in-memory, keyed by edge_id):
  traffic:{edge_id} → { current_weight_s, sample_count, updated_at }
  Refreshed continuously from aggregated probe data; base_weight_s in the durable table never changes
  from this — traffic is always a multiplier/overlay on top of the static graph, never a graph mutation

Tile storage. Pre-rendered (or pre-vectorized) tiles keyed by {zoom}/{x}/{y}, stored in object storage and fronted by a CDN. Regenerated on the map-data refresh cadence (weekly/monthly), not per-request — tiles do not encode live traffic, only road geometry and static labels, which is exactly why they're cacheable at CDN timescales while routes are not.

Object storage: tiles/{z}/{x}/{y}.pbf   (vector tiles; raster equivalent for imagery layers)
CDN in front, cache key = tile path, TTL = days (topology changes slowly)

8. Version 1 — simplest thing that works¶

Single region, full graph in memory, Dijkstra's algorithm run fresh per request, static (non-live) edge weights computed once from speed limits.

graph LR
    Client -->|GET /routes| API[API process]
    API -->|Dijkstra over full graph| Graph[(In-memory graph\nstatic weights)]
    API -->|route + ETA| Client
    Client -->|GET /tiles| API
    API -->|pre-rendered tile| Disk[(Local tile files)]

import heapq

def dijkstra(graph: dict[int, list[tuple[int, float]]], source: int, target: int):
    # graph[node] = [(neighbor, weight_s), ...]
    dist = {source: 0.0}
    prev = {}
    pq = [(0.0, source)]
    visited = set()

    while pq:
        d, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)
        if node == target:
            break
        for neighbor, weight in graph.get(node, []):
            nd = d + weight
            if nd < dist.get(neighbor, float("inf")):
                dist[neighbor] = nd
                prev[neighbor] = node
                heapq.heappush(pq, (nd, neighbor))

    return reconstruct_path(prev, source, target), dist.get(target)

This returns a correct shortest path and works fine for a small graph (a single city, a few hundred thousand edges) queried at low volume. Do not add infrastructure yet — find the actual bottleneck first.

9. Identify the bottleneck¶

10. Version 2 — precomputed hierarchical routing + periodic traffic updates¶

Introduce a contraction hierarchies-style precompute: offline, iteratively "contract" nodes out of the graph in order of importance (a residential dead-end contracts early; a highway interchange contracts late), inserting shortcut edges that represent "the shortest path between these two important nodes, skipping everything unimportant in between." At query time, instead of exploring the full graph, a bidirectional search runs only through progressively "more important" shortcuts — most of the graph is never touched, because the shortcuts already encode what would have been thousands of hops.

Conceptually: think of it like pre-building the "if you're already on the highway, here's the fastest way between any two highway junctions" answer once, offline, so a query crossing a continent barely touches local streets at all — it hops onto shortcut edges almost immediately and only expands local detail near the origin and destination.

graph LR
    Client -->|GET /routes| API[Routing API]
    API -->|bidirectional search over shortcuts| CH[(Contraction hierarchy\nprecomputed graph + shortcuts)]
    Batch[Offline precompute job] -->|nightly rebuild| CH
    Probes[Traffic probes] -->|aggregate, batch| Weights[(Edge weight table)]
    Weights -.->|hourly refresh| Batch

# conceptual shape only — not a full CH implementation
def query_contraction_hierarchy(ch_graph, source, target):
    # forward search from source, backward search from target,
    # both restricted to edges going to "more important" nodes
    forward_dist = bidirectional_dijkstra_forward(ch_graph, source)
    backward_dist = bidirectional_dijkstra_backward(ch_graph, target)
    # shortest path = node minimizing forward_dist[n] + backward_dist[n]
    meeting_node = min(
        set(forward_dist) & set(backward_dist),
        key=lambda n: forward_dist[n] + backward_dist[n]
    )
    return unpack_shortcuts(meeting_node, forward_dist, backward_dist)

A subtlety that matters for what comes next: a shortcut edge's weight is not independent of the base edges it skips — it's the sum (or min, over possibly several represented paths) of weights along whatever it represents. Change a base edge's weight (a road gets slower) and every shortcut whose underlying path crosses that edge is now wrong until it's recomputed; you cannot just poke a new number into one edge and leave the rest of the hierarchy alone. This is why traffic weights are folded in via a distinct customization phase, not a raw edge-weight edit — and it's also why plain node-contraction CH, as sketched above, is the wrong tool for frequent reweighting: there's no cheap way to know which shortcuts a given base-edge change invalidates without re-deriving them.

The production answer (Customizable Route Planning, CRP) restructures the precompute around this exact requirement by splitting it into two genuinely independent phases instead of one:

1. Partition (metric-independent, rebuilt rarely — weekly, on road-network changes). Divide the graph into a hierarchy of cells — geographically contiguous chunks of a few thousand nodes each, grouped into progressively larger cells at higher levels (city block → district → region). This partition depends only on graph topology, never on edge weights, so it's stable across every traffic update.
2. Customization (metric-dependent, cheap, run frequently). For every cell, compute the shortest-path distance between every pair of its boundary nodes (the small number of nodes where the cell connects to its neighbors) using only that cell's internal edges and current weights — this is a small, local computation, independent per cell. Those boundary-to-boundary distances become the edges of an overlay graph at the next level up, and the same step repeats one level higher, using the level-below's boundary distances instead of raw edges. A full customization pass touches every cell once, bottom-up, and is far cheaper than a CH rebuild because each cell's computation is small and independent — seconds to low tens of seconds for a metro region, not minutes to hours.

The key property CRP buys that plain CH doesn't: when only a handful of edges change, only the handful of cells containing those edges need their boundary distances recomputed — and that recomputation only has to propagate up through the partition levels where the boundary distances actually changed, which for a single road segment is almost always one cell and rarely more than a couple of levels. This is what makes the next section's incident-response mechanism possible without the bitset-of-covered-edges idea an earlier draft of this page proposed (infeasible at this scale, and wrong besides — a shortcut's constituent path isn't a contiguous range of edge IDs, so "which edges does this shortcut cover" isn't a cheap membership check to begin with). CRP sidesteps the question entirely: it never asks "which shortcuts does this edge affect," it just recomputes the one or two cells the edge lives in.

11. Identify the next bottleneck¶

12. Version 3 — production architecture¶

graph TD
    Phones[Phone probes] -->|breadcrumbs, ~415K/s| Ingest[Traffic Ingestion Pipeline]
    Ingest -->|map-match to edges, aggregate| Stream[Kafka: edge-weight updates]
    Stream --> CellCust[Incremental Customization Service\ntracks which cells changed]
    Stream --> IncidentDet[Incident Detection Service]
    IncidentDet -->|flag closed/degraded edges| CellCust
    CellCust -->|recompute boundary distances,\naffected cells + levels only| Overlay[(Overlay graph\nin-memory, per-cell boundary distances)]

    Client -->|GET /routes| GW[Routing Gateway]
    GW -->|bidirectional search over overlay + cells| RouteSvc[Routing Service replicas]
    RouteSvc -->|partition + last full customization, read-only| CH[(CRP partition + overlay\nsharded by region)]
    RouteSvc -->|read latest boundary distances| Overlay
    RouteSvc -->|route + duration_in_traffic| Client

    Batch[Offline partition + full-customization cluster] -->|full customization, periodic| CH
    Batch --> Overlay
    RawGraph[(Durable road graph\nversioned)] --> Batch

    ClientTiles[Client] -->|GET /tiles| CDN[CDN edge]
    CDN -->|miss| TileOrigin[(Tile object storage)]
    RawGraph -->|regenerate on refresh| TileOrigin

Key production decisions:

• Incident response is incremental customization scoped to the affected cells, not a query-time patch. A closed edge or a sudden speed drop is mapped to the one or two cells it lives in, and the customization service recomputes only those cells' boundary-to-boundary distances (a small, local Dijkstra-scale computation) and propagates the change up through the partition levels only as far as a boundary distance actually moved — usually one or two levels for a single incident, not the whole region. The updated overlay distances are pushed live within seconds of detection, and every subsequent query simply reads the current overlay — there's no per-query decision about whether to trust a shortcut, because the overlay itself is kept correct rather than being read speculatively and checked against a separate flag list.
• Incident detection watches the aggregated probe stream for signatures a simple average wouldn't catch fast enough — a cluster of probes all reporting near-zero speed on an edge that's normally free-flowing — and proactively flags the edge as degraded/closed rather than waiting for enough individual probe updates to organically drag the average down, handing the flagged edge straight to the customization service as a priority recompute.
• Routing service is stateless and horizontally scaled, holding a read-only copy (or shard) of the hierarchy; hot corridors during rush hour are handled by scaling replica count, not by any special-casing of "popular" edges — unlike ride-hailing's hot geohash cell (which needs cell-splitting because it's a write hot spot), this is a read hot spot, so it's just more read replicas.
• Tile serving is fully decoupled — CDN with object storage origin, regenerated on the map-data refresh cadence, never touching the routing path.
• The durable road graph is versioned, and the offline precompute cluster builds each hierarchy version from a specific graph snapshot — this is what makes the graph-refresh failure mode (below) tractable.

13. Failure analysis¶

14. Consistency considerations¶

• Graph topology is strongly versioned, weights are eventually consistent. A route's turns must come from one consistent graph snapshot (mixing two versions mid-route risks referencing a segment that doesn't exist in one of them), but the weight used to rank candidate paths is allowed to be a few seconds to a couple of minutes stale — the same "structure needs correctness, weight tolerates staleness" split that makes V3 work.
• Read-your-own-incident: if a user reports a hazard (crowdsourced incident, in products that support it) they should see it reflected in their own subsequent route queries quickly, even if the wider population takes longer to converge — similar in spirit to pastebin's read-your-writes for the creator.
• Tiles are eventually consistent across regions by design — a newly added road showing up in Tokyo's tile cache a few minutes before it shows up in São Paulo's is an acceptable and unremarkable staleness window, unlike a closed-road routing correctness bug.
• Incident data must never be strongly consistent at the cost of latency — a route computed with a 2-second-old view of an incident is far preferable to one that blocks 500ms waiting for a guaranteed-fresh read; treat incidents as fast-converging eventual state, not a lock.

15. Observability¶

Metrics:
  route_latency_ms p50/p99 (SLO: p99 < 200ms)
  tile_latency_ms p50/p99, tile_cache_hit_rate (CDN)
  traffic_ingestion_lag_ms per region
  overlay_update_latency_ms (probe observed → weight applied)
  hierarchy_version_skew (fraction of active sessions on a non-latest graph version)
  incident_detection_time_s (probe anomaly → flagged edge)
  routing_replica_qps (detect hot-corridor read concentration)

Alerts:
  route_latency_p99 > 200ms for 5 min
  traffic_ingestion_lag > 3 min
  overlay_update_latency_p99 > 90s
  routes_through_flagged_closed_edge > 0  (should never happen — hard correctness alarm)
  hierarchy_version_skew: too many sessions stuck on an old version past its expected retirement window

16. Cost analysis¶

Routing service (stateless replicas holding sharded hierarchy, global):
  ~150 replicas x $400/mo (memory-heavy instances for graph shards): ~$60,000/mo

Offline precompute cluster (periodic full/partial rebuilds per region):
  Bursty batch compute, ~$8,000/mo amortized

Traffic ingestion (Kafka + aggregation, 415K probes/sec):
  ~$10,000/mo (comparable in shape to ride-hailing's location-ingestion cost, larger volume)

Tile storage + CDN (2B requests/day):
  Object storage: ~$2,000/mo
  CDN egress at this volume: ~$15,000/mo (dominant tile cost — this is the lever to pull first)

Total: ~$95,000/mo at global scale

Cost lever: CDN cache hit rate on tiles. Going from 90% to 98% hit rate on 2B requests/day
  cuts origin fetches (and CDN-to-origin bandwidth) by 5x — worth more than any routing-side optimization
  because tile volume outnumbers route volume by roughly 40:1.

17. Alternative architectures¶

18. Staff Engineer Extensions¶

19. Interview follow-ups¶

1. "How is this different from the ride-hailing exercise?" — Ride-hailing's hard problem is nearest-neighbor search over independent moving points (geohash cells). This exercise's hard problem is shortest-path over a graph with continuously changing edge weights (contraction hierarchies + a live overlay). Point-location/spatial-indexing ideas transfer; the traversal algorithm and the precompute-vs-live split do not.
2. "Why not just re-run Dijkstra but on a smaller graph — e.g. only major roads?" — That's roughly what contraction hierarchies achieve, but done principledly: the hierarchy's shortcut edges are an automatically-derived "important roads only" view, generated per-region from the actual graph rather than a hand-maintained "highways only" subset that would miss a case where the fastest path genuinely goes through a local road.
3. "How do you handle a road that's one-way, or a turn restriction (no left turn)?" — Directed edges naturally encode one-way streets. Turn restrictions require the graph to model transitions between edges, not just nodes (a "no left turn from Main St onto 1st Ave" is a constraint on an edge-pair, not a node) — briefly mention this without deriving the full edge-expanded graph representation, it's a well-known extension.
4. "What happens if two conflicting live updates arrive for the same edge near-simultaneously — a probe says it's clear, an official incident feed says it's closed?" — Authoritative sources (DOT closure feeds, verified incident reports) should outrank aggregated probe inference — a single confirmed closure is a hard override, while probe-derived weight is a statistical estimate that should never silently contradict a known-true closure.

Self-Assessment¶

• [ ] I can explain why this exercise's hard problem (graph shortest-path) is different from ride-hailing's (nearest-neighbor), not just superficially similar because both are "maps"
• [ ] I can describe, conceptually, what a contraction hierarchy precomputes and why that makes queries fast without deriving the full algorithm
• [ ] I can explain why structure (the hierarchy) and weight (traffic) are kept separate, and why that split is what makes incident response fast
• [ ] I can justify why tile serving and route computation have completely different latency/caching strategies despite being "the same product"
• [ ] I can walk through how a road-graph version refresh avoids breaking an in-flight navigation session