Design interviews / Intermediate / 6 min
Design Google Maps: routes and live traffic
Roads as a weighted graph. Watch Dijkstra and A* explore the city, then ignore live traffic and see routes drive into a jam.
Start the simulation → Change the load, break a part, watch what happens. Free, no sign-up.
In short
- What it is
- A maps service stores roads as a weighted graph and answers route requests with shortest-path search, using live speeds as the weights.
- Why it matters
- Billions of route requests must return in milliseconds and stay accurate while traffic changes.
- The trade-off
- Precomputing shortcuts (contraction hierarchies) makes queries fast but must be rebuilt as traffic changes; live data needs a big stream of phone speeds.
- Say it in an interview
- "Road graph partitioned into tiles, contraction hierarchies or A* for queries, live speeds from phones streamed in to update edge weights, and ETA models on top."
Check yourself
Why does A* explore fewer intersections than Dijkstra?
Answer: It adds an estimate of the remaining distance, so it searches towards the destination first. With a heuristic that never overestimates, A* still finds the fastest route but ignores directions that cannot help.
How does live traffic change routing?
Answer: It changes the edge weights (driving times), so a different route can become fastest. Weights come from current speeds; a jam makes its roads expensive and the search goes around.
What happens if the router ignores a traffic jam?
Answer: The route may go through the jam and the ETA shown is far too optimistic. The plan uses free-flow times, but the car experiences the real ones.