Design maps and navigation

Show anyone a map of anywhere, find the fastest way from A to B across a continent in well under a second, and keep the arrival time honest as traffic changes. Three hard parts hide in that sentence: a graph with hundreds of millions of road segments, a stream of millions of location pings a second, and a prediction (the ETA) that users check against reality every time.

1. The prompt

"Design a maps app: people can look at the map, get driving directions with an arrival time, and be guided turn by turn, with the route updated when traffic changes."

What makes it hard:

• Routing is a graph search on a huge graph. The textbook algorithm explores millions of intersections for a long trip; users expect an answer in a fraction of a second.
• The graph's weights change every minute. Travel times depend on live traffic, which comes from the users themselves.
• The map itself is enormous and must load instantly at every zoom level, anywhere in the world.

2. Frame the problem

3. What it must do

1. A user can view the map anywhere, panning and zooming smoothly.
2. A user can get a driving route from A to B with an arrival time, using current traffic.
3. A user can navigate: follow the route turn by turn, with rerouting when they leave it or traffic changes.

Not now: public transport (a timetable problem), reviews and photos (a separate content system), Street View imagery (a blob pipeline), offline downloads of whole regions (a follow-up in section 10).

4. How well it must do it

5. Numbers that change the design

Skip estimating place-search traffic: it's an ordinary search index (Module 12) and won't change the design.

6. The nouns

• Road segment (an edge) and intersection (a node): the routing graph.
• Tile: a square of the map at one zoom level.
• Place: a named point (address, business).
• Route: a path, its geometry, steps and ETA.
• Trip: one navigation session.
• Location ping and segment speed: the raw input and the aggregate traffic.

segments      segment_id, from_node, to_node, length_m, road_class, speed_limit, one_way, cell_id
segment_speed segment_id, minute, avg_speed_kmh, sample_count               (live, per minute; history by time of week)
tiles         z, x, y, version → object key in blob storage                  (served through the CDN)
trips         trip_id, user_id, route_id, started_at, status                 (short-lived; no raw trace stored)

7. The contract

REST for one-off requests, a streaming connection for navigation. The user comes from the auth token.

GET  /v1/tiles/{z}/{x}/{y}.mvt?v={version}     → vector tile        (cached at the CDN for days)
GET  /v1/places?q=&near=lat,lng                 → [{place_id, name, lat, lng}]
POST /v1/routes  {origin, destination, depart_at?, avoid?}
     → {routes: [{route_id, polyline, distance_m, eta_s, steps: [...]}]}  (best + up to 2 alternatives)
POST /v1/trips   {route_id}                     → {trip_id}
WS   /v1/trips/{trip_id}/stream   client → {lat, lng, speed, heading, ts} every ~5 s
                                  server → {eta_s} | {reroute: {route}} | {alert}

Data flow for traffic: phones send pings → ingestion → a stream partitioned by region → snap each ping to a road segment → average speed per segment per minute → new edge weights for routing → better routes and ETAs.

8. First working version

A CDN and tile store, a place search index, one routing service holding a region's graph in memory, and a navigation service.

8.1 Viewing the map

The app asks for the tiles covering the screen. Tiles are pre-built and stored as objects (Module 10); the CDN answers almost every request. Vector tiles carry roads and labels as data, so the phone draws them at any rotation and style.

8.2 Getting a route

Geocode the destination, then run a shortest-path search on the road graph, where each segment's weight is its travel time. The first version runs A* (Dijkstra guided towards the destination) on the region's graph in memory.

8.3 Navigating

The phone downloads the route and the tiles along it, then guides the driver locally. Every few seconds it streams its position; the server compares it with the route and recomputes the ETA.

9. Make it hold up

9.1 Fast routes on a continental graph routes under 1 s

This is the move interviewers look for: trade offline preprocessing for fast queries, the same idea as an index. Open-source engines (OSRM, Valhalla) and the Customizable Route Planning work from Microsoft Research show it works at continental scale.

9.2 Splitting the world routes under 1 s · surviving failures

• Partition the graph into cells (cities or regions) with few boundary nodes between them. Inside each cell, precompute the travel time between every pair of its boundary nodes.
• A long route searches only the start cell, the destination cell, and the small overlay graph of boundary nodes in between.
• Routing servers are sharded by region and replicated; a request for a trip inside one region goes to that region's servers. Cross-region trips use the overlay, which is small enough to replicate everywhere.

9.3 Live traffic from location pings traffic within 2 minutes · privacy

• Ingest ~2 M pings a second into a stream partitioned by region (Module 18). Strip user IDs at the edge; keep only a short-lived trip token.
• Map matching: GPS is noisy (tens of metres); snapping a sequence of points to the most likely road segments uses a hidden Markov model (Newson and Krumm, 2009).
• Aggregate speeds per segment per minute in a stream processor (Module 23), dropping segments with too few samples so no single car is identifiable.
• Update weights without a rebuild: keep the partition fixed and only redo each cell's small boundary table ("customisation") when its speeds change: seconds, not hours.

9.4 Honest arrival times ETA within 10%

9.5 Navigation sessions and rerouting keeps working

• The phone navigates locally with the route and tiles it already has, so a tunnel or a server blip doesn't interrupt guidance.
• Off-route: the phone notices first and asks for a new route from its position.
• Better route: the server periodically re-checks active trips against new traffic and pushes a reroute only if it saves meaningful time (say 2+ minutes), to avoid flip-flopping.
• Spread the load: sending every car down the same side street creates the next jam; routing for many trips at once should account for the cars it's already sending.

9.6 Tiles for the whole planet tiles under 200 ms

• Vector tiles are small and styled on the device; one set serves light, dark and navigation styles.
• Pre-build zoom levels 0–14 for everywhere; build deeper zooms on first request and store them. The CDN absorbs nearly all reads.
• When map data changes (a new road), rebuild only the affected tiles and bump their version in the URL instead of purging caches.

9.7 The whole design after the deep dives

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• Heavy offline preprocessing for millisecond queries.
• A fixed partition with fast re-customisation, instead of rebuilding for every traffic change.
• Local navigation on the phone, with the server as an advisor.
• Aggregated, anonymised traffic instead of stored traces.
• Versioned tiles and graphs rather than in-place updates.

What we'd watch: route latency p99 · ETA error by region · traffic data age · tile error rate · reroute rate and acceptance · ping ingestion lag.

At 10×: more routing replicas per region; more stream partitions; tighter aggregation windows only where traffic is dense.

Common mistakes:

• Running Dijkstra over the world per request.
• Storing every ping in a database.
• Routing from live speeds alone for long trips.
• Making navigation depend on a live server connection.
• Rendering tiles on every request.
• Ignoring location privacy.

13. Try it, check yourself, read more

Route search lab. A small city as a grid of streets; every block takes one minute unless it's in the red jam. Pick a search and watch how much of the city it explores before finding the fastest route. Then switch the jam on and see the route bend around it.

A 30 × 17 grid (510 junctions). On a real continent Dijkstra would explore millions of junctions; precomputed shortcuts explore hundreds to a few thousand, which is why production routers use them.