Google Maps

Map tiles, routing and live traffic

Design a maps service that draws the map at any zoom, finds driving routes on a continental road network in milliseconds, and predicts arrival times from live and historical traffic.

Overview

A maps product is several systems that share one picture of the world. Tiles draw the map. A road graph answers 'how do I get there'. A traffic pipeline turns phones' location reports into speeds on each road. An ETA model predicts how long the trip will take. Place search and geocoding turn names and addresses into points.

The organizing idea for the interview is to split the static from the dynamic. Roads, names and the drawn map change slowly: precompute them, version them and cache them at the edge. Traffic changes every minute: keep it in a separate, fast-moving layer that feeds routing and ETAs without rebuilding the static parts.

Google has written about some of this (its traffic and ETA work with DeepMind, its tile coordinate system, the S2 library) and not about the rest, including its routing algorithm. This topic uses Google's sources where they exist and published research (contraction hierarchies, customizable route planning, HMM map matching) for the general techniques, and says which is which.

Questions to ask first

Which features? — Map display, driving directions, live traffic, ETA, place search, navigation
How many users? — 300 million a day; 30 billion tile requests and 100 million route requests a day
How fresh must traffic be? — A few minutes from the road to the ETA
Routing latency? — Under 200 ms per route at p99, including alternatives (a target we chose)
Offline? — Downloaded areas work without a network, without live traffic
Where does map data come from? — An existing map-making pipeline publishes versioned map data

What you will be able to do

Compute which tile covers a point at a zoom level, and size the tile pyramid.
Explain Dijkstra, A*, contraction hierarchies and customizable route planning, and when each fits.
Turn noisy phone locations into per-road speeds with map matching.
Build an ETA from segment times predicted for the moment the driver reaches them.
Keep navigation working through lost signal and changing traffic.

Key concepts

Tile pyramid
Vector tiles
Road graph
Contraction hierarchies
Customizable route planning
Map matching
Probe data
ETA prediction
S2 cells

Functional requirements

Show the map at any zoom level, in several styles (day, night, satellite overlay)
Return driving directions with two or three alternatives, a travel time and a route line
Show live traffic colors on roads and use them in routes and ETAs
Search for places by name or category near a point; convert addresses to coordinates and back
Guide a driver turn by turn, update the ETA, and reroute when a faster route appears
Let users download an area for offline maps and routing

Non-functional requirements

Tiles load from a nearby cache in under 100 ms for most requests (a target we chose)
Routes answer in under 200 ms at p99 (a target we chose)
Traffic is reflected in routes and ETAs within a few minutes of it happening
Location reports are used only in aggregate; individual trips are not exposed
A failure of the traffic pipeline degrades routes to historical speeds, never to no routes

Interview questions

How do map tiles work, and how many are there?
Dijkstra is too slow for a continent. What do you do?
How do you use live traffic in routing when preprocessing assumes fixed costs?
How do you turn phone locations into traffic speeds?
How would you predict an accurate ETA?
How does a search for coffee near me work?
What still works when the phone loses signal?
How do you roll out a new version of the map safely?