Designing Google Maps

The problem

Design Google Maps (the routing/navigation core): compute the best route between two points over the world’s roads, with live traffic, turn-by-turn navigation, ETAs, map display, and place search. The crux is fast shortest-path on a continent-sized graph that naive Dijkstra can’t handle interactively.

Step 1 — Requirements

Functional: render the map (pan/zoom); search/geocode places (address ↔ coordinates); compute routes (fastest/shortest) with live traffic; ETAs and turn-by-turn nav; reroute on the fly.

Non-functional: low-latency routing (a route over millions of road segments in milliseconds), massive scale, fresh traffic, global, available.

Step 2 — The road network as a graph

Model roads as a weighted graph: nodes = intersections, edges = road segments, edge weight = travel time (length / speed, adjusted by traffic, turn restrictions, road type). Routing = shortest path on this graph.

Step 3 — Why naive shortest-path fails (the core)

Plain Dijkstra over a continent’s graph explores far too many nodes for an interactive response. The key idea is precomputation:

• A* — Dijkstra with a heuristic (straight-line distance to target) to explore toward the goal. Helps, but still slow continent-scale.
• Contraction Hierarchies (CH) — precompute shortcuts that skip over unimportant nodes, building a hierarchy of “important” roads (highways). Queries then explore only a tiny fraction of the graph — orders of magnitude faster — at the cost of an expensive offline preprocessing step. This is how real routing engines hit millisecond queries.
• Other precomputation (hub labeling, transit-node routing) pushes it further.

The trade is offline preprocessing + storage for fast online queries — exactly the recurring “precompute to make reads cheap” pattern.

Step 4 — Live traffic

Edge weights must reflect current conditions:

• Aggregate GPS from users’ phones (anonymized) → current speed per segment, streamed in real time.
• Update edge weights with live speeds; predict near-future traffic for ETAs.
• Live traffic complicates pure CH (weights change), so production systems use customizable variants (CRP) that re-weight without full re-preprocessing.

Step 5 — Map rendering with tiles

The map is served as pre-rendered tiles at multiple zoom levels (a quadtree of image/ vector tiles). Pan/zoom fetches the visible tiles from a CDN — the same edge-caching of static, immutable content as the media systems. Vector tiles render client-side for crisp zoom.

Step 6 — Geocoding and place search

• Geocoding — address ↔ coordinates, via an index of places (and the geo/spatial index from Yelp for “nearby”).
• Search — an inverted index over places/addresses (Chapter 4 search), with geo ranking.

Step 7 — Architecture

client → tiles (CDN)  |  search/geocode (index)  |  routing service
routing service: road graph (+ CH shortcuts) + live traffic weights → shortest path → ETA
traffic pipeline: phone GPS → stream → per-segment speeds → edge weights

Trade-offs to raise

• Precompute (CH: fast queries, heavy preprocessing/storage, hard with changing weights) vs on-the-fly Dijkstra/A* (no preprocessing, too slow at scale). Precompute wins; use traffic-aware variants.
• Tile pre-rendering (fast, storage) vs render-on-demand.
• ETA accuracy vs cost — more live data and prediction = better ETAs, more compute.

The interview cue

“Model roads as a weighted graph; route with precomputed Contraction Hierarchies (highway shortcuts) for millisecond queries instead of plain Dijkstra; edge weights from live GPS-aggregated traffic (with CRP-style re-weighting); the map is pre-rendered tiles on a CDN; geocoding/search via spatial + inverted indexes.” Graph + precomputed shortest path + live traffic is the heart; implementation next.