system-design

Difficulty: Tier 3 Asked at: Google, Uber, Careem, Amazon Time budget: 45–60 min

Maps is a graph problem at planetary scale: the road network is a huge weighted graph, and “directions from A to B” is shortest-path over it — but plain Dijkstra over a continent is far too slow for interactive use. The signature ideas are graph partitioning + precomputed contraction hierarchies for fast routing, and real-time traffic as dynamic edge weights. This is the case study where graph algorithms meet distributed systems.

Prerequisites: Geospatial Indexing, Graph Databases, Caching

1. Requirements

Functional:

Compute driving/walking directions (route) between two points.
Show ETA, accounting for real-time traffic.
Reroute when conditions change; alternative routes.
Map rendering (tiles), search for places (reference search/geospatial).

Non-functional:

Fast routing — a route in well under a second, interactively.
Massive graph — hundreds of millions of road segments globally.
Fresh traffic — ETAs reflect current conditions.
Global scale, high availability.

Out of scope: map tile rendering pipeline internals, place search internals, satellite imagery.

2. Estimation

Road network: ~hundreds of millions of nodes (intersections) and edges (segments) globally.
Routing queries: millions/day; each must be sub-second over a continental graph → 🚨 plain shortest- path won’t cut it; precomputation is mandatory.
Traffic data: streamed from millions of devices (phones, cars) → updates edge weights continuously.

3. The core: the road network as a graph

🚨 Model roads as a weighted directed graph: nodes = intersections, edges = road segments, edge weight = travel time (distance ÷ speed, adjusted for traffic). “Directions” = shortest path by travel time.

Why plain Dijkstra/A* isn’t enough: shortest-path over a graph with hundreds of millions of edges takes too long per query for interactive use, especially for long routes (city to city). You must precompute to make queries fast.

4. Making routing fast: precomputation

🚨 The key technique: partition the graph and precompute shortcuts.

Graph partitioning: divide the map into regions/cells. Most of a long route is “highway-level” travel between regions; only the ends need street-level detail.
Contraction Hierarchies (CH) / precomputed shortcuts: offline, precompute shortcut edges that skip over unimportant nodes, so a query traverses far fewer nodes. Long-distance routing hops between important nodes (highways) instead of every intersection. 🚨 This turns a continental shortest-path from seconds into milliseconds.
Hierarchical routing: route at a coarse (highway) level between regions, refine to streets only near the start/end. Mirrors how a human reads a map.

flowchart LR
    A[Start] --> Local1[Street-level<br/>near start]
    Local1 --> HW[Highway-level<br/>precomputed shortcuts]
    HW --> Local2[Street-level<br/>near end]
    Local2 --> B[End]

5. Deep dives

5a. Precomputation vs. dynamic traffic

Precomputed shortcuts assume static weights, but traffic changes weights constantly — the tension. Resolve it: precompute the structure (shortcuts, hierarchy) on the static road graph, and overlay live traffic as weight adjustments on the relevant edges at query time. Most of the world isn’t congested, so you adjust only affected segments and re-evaluate near them. 🚨 Separate the static graph structure (precomputed) from the dynamic weights (live) — this is the crux.

5b. Real-time traffic

Traffic comes from crowdsourced GPS traces (millions of phones reporting speed/location) aggregated per road segment in near-real-time → current speed per edge → updated travel-time weights. This is a streaming aggregation problem (ad-click aggregator flavor). Feed it into ETA/routing. Historical patterns (rush hour) predict future segments of a long trip.

5c. Sharding the graph geographically

The graph is partitioned by geography across machines. A route within a region is served locally; a long cross-region route uses the highway-level hierarchy to hop between regions, touching each region’s shard only near the route. Geographic locality keeps most queries local. (Geospatial)

5d. ETA computation

ETA = sum of (segment travel times) along the route, using current + predicted traffic (for later parts of a long trip, predict what traffic will be when you arrive there, from historical patterns). Continuously recompute as the driver progresses and conditions change → reroute if a faster path emerges.

5e. Map tiles & rendering

Map display uses precomputed image/vector tiles at multiple zoom levels, served from a CDN (static, cacheable) — a separate, mostly-read concern from routing. Mention it, don’t dwell.

6. Bottlenecks & scaling further

Routing latency → contraction hierarchies / precomputed shortcuts + hierarchical routing.
Dynamic traffic → precompute static structure, overlay live weights.
Traffic ingestion → streaming aggregation of GPS traces per segment.
Graph size → geographic partitioning; local queries stay local.
Map rendering → precomputed tiles + CDN (separate path).
Query volume → cache popular routes (common commutes).

7. Trade-off summary

Decision	Chosen	Alternative	Why
Routing	Precomputed shortcuts (CH) + hierarchy	Plain Dijkstra/A* per query	Continental shortest-path is too slow live
Traffic	Static structure + live weight overlay	Recompute everything live	Only affected segments change; keep precompute
Traffic data	Crowdsourced GPS, streamed	Sensors only	Ubiquitous, near-real-time coverage
Graph storage	Geographic partitioning	Single graph	Locality; long routes hop via hierarchy
Tiles	Precomputed + CDN	Render on demand	Static, cacheable, cheap

8. Follow-up questions

Why can't you just run Dijkstra or A* on each routing request?

Because the road network has hundreds of millions of nodes and edges, and a plain shortest-path algorithm explores a large fraction of the graph for long routes — a city-to-city trip could touch enormous numbers of intersections — which takes far too long to meet an interactive sub-second budget, especially at millions of queries a day. A* with a good heuristic helps but still explores too much over continental distances. The solution is precomputation: offline, you build contraction hierarchies or precomputed shortcut edges that let a query skip over the vast majority of unimportant nodes and route at a highway-like level between important nodes, refining to street level only near the endpoints. This transforms the per-query work from traversing millions of nodes to traversing a few thousand, turning seconds into milliseconds. The cost is a heavy offline preprocessing step and the need to keep it consistent with the road graph, which is worth it because routing queries vastly outnumber road-network changes.

Precomputed shortcuts assume fixed weights, but traffic changes constantly. How do you reconcile that?

By separating what's static from what's dynamic. The *structure* of the road network — which segments connect where, and the shortcut hierarchy that makes routing fast — is essentially static and is what you precompute. Traffic changes the *weights* (travel times) on edges, not the structure, and at any moment only a subset of segments are actually congested. So you precompute the hierarchy on the static graph and overlay live traffic as weight adjustments on the affected edges at query time, re-evaluating around those edges rather than recomputing the entire preprocessing. For most of a route, which passes through uncongested areas, the precomputed shortcuts remain valid; near congestion you incorporate the updated weights and may choose alternate shortcuts. This static-structure/dynamic-weights split is the crux: it preserves the huge speedup from precomputation while still reflecting current conditions in the ETA and the chosen route.

Where does real-time traffic data come from and how is it processed?

Primarily from crowdsourced GPS traces — the location and speed reports continuously sent by millions of phones and vehicles using the maps app. These reports are aggregated per road segment in near-real-time through a streaming pipeline: match each trace to the road segment it's on, aggregate the observed speeds for each segment over a short window, and derive a current travel-time weight for that segment. That stream of per-segment speeds updates the edge weights the router uses. Historical aggregates of the same data give typical patterns (e.g., this highway is slow at 6pm), which are used to *predict* conditions for the later parts of a long trip — since you'll reach a distant segment in an hour, you weight it by predicted, not current, traffic. It's fundamentally a large-scale streaming aggregation problem feeding dynamic weights into routing and ETA.

How do you compute an accurate ETA for a two-hour trip?

By summing predicted segment travel times along the route using traffic as it will be *when you arrive at each segment*, not just current conditions. For the near part of the trip you use current traffic, but for segments you'll reach later you use predicted traffic derived from historical patterns for that segment at that future time of day — because a segment that's clear now may be congested by the time you get there, and vice versa. The ETA is the sum of these time-appropriate segment estimates. As the driver progresses and new real-time data arrives, you continuously recompute the remaining ETA and the route, rerouting if a faster path has emerged due to changing conditions. So an accurate ETA blends real-time data for the immediate portion with time-shifted historical prediction for the distant portion, updated continuously — treating ETA as a live estimate that improves as the trip unfolds rather than a one-shot calculation.

9. What junior / mid / senior answers look like

Junior: models roads as a graph and proposes Dijkstra per query. Correct in principle but can’t meet latency at continental scale; may not consider traffic.
Mid: recognizes precomputation is needed (shortcuts/hierarchy), overlays live traffic as weights, geographically partitions the graph, aggregates GPS traffic.
Senior: cleanly separates precomputed static structure from dynamic weights, uses contraction- hierarchy/hierarchical routing for sub-second continental routes, builds streaming crowdsourced traffic with historical prediction for ETAs, partitions the graph geographically, and treats tiles/CDN as a distinct read path — showing how graph algorithms and distributed systems combine.