The whole course ▾

System Design · Mock interview 16 of 20

Design Google Maps: routes and ETAs

Updated 22 Oct 2026 · By Akshay, software engineer, India · 9 min read

Design Google Maps, its routes and arrival times.

Try it first

Before you read the interview, answer the question yourself. Give yourself 10 minutes: say your design out loud, or sketch it on paper. What would you ask? Which numbers matter? Which boxes, and what's the hard part? Then read on, and score yourself with the feedback at the end.

The video for this mock interview is coming soon.

New System Design videos go up at 6 pm. Subscribe on YouTube so you don't miss it.

Got a doubt? Ask in the comments under the video.Subscribe

Requirements

Requirements
Clarifying questions
->
Which parts? -> Map, driving routes, ETAs
->
Scale? -> 50,000 route requests/s at peak
->
Traffic data? -> Anonymous speeds from phones
->
How fresh? -> Within a minute or two
Functional requirements
Show the map, smoothly, at any zoom
Fastest driving route, A to B
Arrival time with live traffic
Reroute if traffic changes
Non-functional requirements
->
A route in well under a second
->
Smooth panning: tiles load instantly
->
ETAs accurate to a few minutes
->
Private: no one tracked
Out of scope
Searching places
Walking and public transport
Street View and satellite images
interviewer
Hi. Ready to start?
candidate
Ready. I'll draw as I go.
interviewer
Design Google Maps: the map itself, routes from A to B, and arrival times, with live traffic.
candidate
Okay. That's huge, so I'd like to narrow it down. I already suspect the map, the routes and the traffic are three very different problems. A few questions?
interviewer
Sure.
candidate
Which parts?
interviewer
Showing the map, driving routes, and arrival times.
candidate
What scale?
interviewer
Worldwide, with around fifty thousand route requests a second at peak.
candidate
Where does live traffic come from?
interviewer
Anonymous speed reports from phones driving with navigation on.
candidate
And how fresh must it be?
interviewer
A jam should show up within a minute or two.
candidate
So, what it does. Show the map smoothly at any zoom, from the whole world down to one street. Find the fastest driving route from A to B. Give an arrival time using live traffic. And during navigation, reroute if a faster way appears.
candidate
And how well. A route in well under a second, even across a country. Smooth panning, with tiles appearing instantly. Arrival times accurate to within a few minutes. And private: the traffic comes from people's phones, so no one's trip can be tracked.
interviewer
Good that you raised privacy.
candidate
I'll leave out searching for places, walking and public transport, and Street View and satellite images. Does that match what you had in mind?
interviewer
Yes. Routing is the heart of it.

Estimation

Estimation
Back of the envelope
Tiles: millions/s, nearly all from the CDN
Routes: ~50,000 a second at peak
Road graph: hundreds of millions of segments
Traffic: millions of speed reports a second
WHAT THE NUMBERS DECIDE
Tiles:static,cachethem
everywhere.Routes:agraphsearch,
madefastbyprecomputing.Traffic:
astreamthatupdatesroadspeeds.
candidate
Let me size the three parts separately, because they have nothing in common.
interviewer
What load does each part carry?
candidate
Tiles, routes, and traffic, one by one.
candidate
Map tiles, the small squares the map is drawn from, are requested millions of times a second, but they're the same for everyone, so nearly all come from a CDN. Routes: about fifty thousand a second at peak, each a search through a road graph of hundreds of millions of segments, which in a compact form fits in tens of gigabytes of memory. And traffic: millions of speed reports a second, from phones on the move.
interviewer
How often do roads change?
candidate
A few thousand edits a day, worldwide. Tiny next to the reads.
candidate
So, three designs. Tiles are static: build them ahead, and cache them everywhere. Routing is a search through a huge graph, fifty thousand times a second, which is only possible if most of the work is done in advance. And traffic is a stream that keeps updating how fast each road is.
interviewer
Good split. I'd like to go deep on routing.

API and data

API and data
Intersections
graph nodes
Road
segments
length, limit,
direction
Live
speeds
segment ->
speed now
Tiles
pre-built, per
zoom
connect
travel time
Endpoints
1
GET /tiles/{zoom}/{x}/{y}
2
GET /route?from&to -> path,
ETA, steps
3
Navigation: position every few
seconds
4
<- reroute suggestions, pushed
candidate
Next, the API, and the road graph.
interviewer
What does the API look like?
candidate
Map, route, and navigation.
candidate
GET a tile, by zoom level and its x and y position on the grid at that zoom: a small file of roads, labels and shapes, which the app draws. GET a route from A to B, with the path, the arrival time, and turn-by-turn steps. During navigation, the app sends its position every few seconds, which also feeds traffic. And the server pushes reroute suggestions when a faster way appears.
candidate
The road network is a graph. Intersections are its nodes. Road segments are its edges, each with a length, a speed limit and a direction, because one-way streets matter. Live speeds, in memory, say how fast traffic is moving on each segment right now, which turns length into travel time. And tiles, pre-built for every zoom level, live in object storage, built from the same road data.
interviewer
Why the same data?
candidate
So the route drawn always matches the map.

High-level design

High-level design
Maps
app
CDN
tiles
cached
Tile
storage
rebuilt
when
roads
change
tiles in
view
on a miss
API
gateway
Routing
service
graph in
memory,
by
region
Traffic
service
live
speed
per
segment
route
home
1
2
speeds,
every minute
path +
ETA
3
Why memory, by region
->
A route search touches thousands
of segments
->
Disk reads would take seconds
->
Split by region; copy for more
capacity
TWO HARD PARTS
Across-countryroutein
milliseconds.AndGPS
reportsturnedinto
accuratearrivaltimes.
interviewer
Okay. Show me the design.
interviewer
Walk me through opening the map, and then asking for a route home.
candidate
Two very different paths. The map first, because it's easy.
candidate
The maps app works out which tiles cover the screen at the current zoom, and fetches them from the CDN, which goes back to tile storage only on a miss. Popular cities' tiles are cached everywhere. And they're vector tiles: road shapes, not pictures, so the phone draws them crisply at any size, and they're small to download.
interviewer
How many zoom levels?
candidate
About twenty. Each level has four times as many tiles as the one above it.
candidate
Now a route. The request goes through the API gateway to the routing service. Each routing server holds a region's whole road graph in memory, so a search never waits on a database. Every minute, the traffic service sends it fresh speeds for each segment. The routing service searches for the fastest path, adds up the travel times, and returns the path and the arrival time.
interviewer
What if a routing server dies?
candidate
Each region has several identical copies, so the next request simply goes to another one.
interviewer
Why in memory?
candidate
One route search touches thousands of road segments, often hundreds of thousands, and reading each from disk would take seconds. So each server keeps a region's graph in memory, regions are split across servers, and a busy region gets another identical copy, or several.
interviewer
What are the hard parts?
candidate
Two. Finding the fastest route across a country in milliseconds, in a graph with hundreds of millions of edges. And turning millions of raw GPS reports into road speeds and arrival times people trust.
interviewer
The algorithm first.

Deep dive: fast shortest paths

Deep dive: fast shortest paths
Plain Dijkstra
Explores outwards in every direction
Millions of segments for a long trip
Seconds per route
Precomputed shortcuts
Shortcuts added in advance
A query touches only thousands
Milliseconds per route
THE CHOICE
Contractionhierarchies,ora
similarshortcutmethod:
heavyworkonce,inadvance;
eachquerytakesmilliseconds.
interviewer
Let's talk about shortest paths.
interviewer
How do you find the fastest route in milliseconds?
candidate
Let me start with the textbook answer, and say why it isn't enough.
candidate
Dijkstra's algorithm explores outwards from the start in every direction, always taking the nearest unexplored point next, until it reaches the destination. Across a city it touches hundreds of thousands of segments; across a country, millions. Seconds per route. Precomputed shortcuts change that. In advance, add shortcut edges that jump over unimportant roads, like one edge for a stretch of highway. A query climbs quickly to important roads, travels along shortcuts, and comes down near the end, touching only thousands of nodes.
candidate
So, a shortcut method like contraction hierarchies. The trade-off: hours of precomputation, done once and repeated when roads change, for queries a thousand times faster.
interviewer
When is that trade worth it?
candidate
When reads vastly outnumber changes. Here, they do.
interviewer
But traffic changes road speeds every minute. Doesn't that break shortcuts computed hours ago?
candidate
It would, done naively. Modern methods split it in two: the structure, which roads connect to which, is computed rarely, since roads rarely change. The costs on top of it are recomputed in seconds, whenever traffic changes. So we get fast queries and live traffic.
interviewer
Good.
interviewer
A route from Delhi to Mumbai crosses many regions, on different servers. Which one answers?
candidate
Every routing server also keeps a small graph of only major highways and the borders between regions. A long route uses detailed local graphs near the start and end, and the highway graph in between. The same climbing to big roads, at the scale of a country.
interviewer
How small is that highway graph?
candidate
A tiny fraction of the full one. Small enough to sit on every server.

Deep dive: live traffic and ETAs

Deep dive: live traffic and ETAs
From GPS to traffic
1
Phones send position and speed, anonymously
2
Snap each point to a road segment
3
Average speeds per segment, per minute
4
Blend with history for that hour
PRIVACY BY DESIGN
Anonymousreports,trip
endsdropped,andonly
averagesstoredperroad.
High-level design
Maps
app
CDN
tiles
cached
Tile
storage
rebuilt
when
roads
change
tiles in
view
on a miss
API
gateway
Routing
service
graph in
memory,
by
region
Traffic
service
live
speed
per
segment
route
home
1
2
speeds,
every minute
path +
ETA
3
Phones
navigating
Speed
stream
Kafka
+
stream
job
position,
speed
speed per
segment
Why memory, by region
->
A route search touches thousands
of segments
->
Disk reads would take seconds
->
Split by region; copy for more
capacity
TWO HARD PARTS
Across-countryroutein
milliseconds.AndGPS
reportsturnedinto
accuratearrivaltimes.
interviewer
Now, the numbers people actually see.
interviewer
How do millions of raw GPS reports become live road speeds, and arrival times people trust?
candidate
Through a stream.
candidate
Phones with navigation on send their position and speed every few seconds, anonymously, into Kafka. A stream job snaps each point to the road segment it's most likely on, which is harder than it sounds near flyovers and parallel roads. It averages the speeds on each segment every minute. And where few phones are reporting, it blends in history: how fast that road usually is, at this hour, on this day.
candidate
So phones navigating feed a speed stream, which produces a speed per road segment every minute for the traffic service, which feeds the routing service. An arrival time is the sum of travel times along the route, plus time for turns and traffic lights, corrected by a model trained on millions of past trips.
interviewer
What does the model add?
candidate
Things like how long the school-run slowdown really lasts.
interviewer
You mentioned privacy. How exactly?
candidate
Reports carry no account ID, just a random ID that changes regularly. The first and last stretch of every trip is dropped, so no one's home or office can be found. And what's stored long-term is only the average speed per road segment, never anyone's journey.
interviewer
A crash blocks the road ahead of someone already navigating. What happens?
candidate
Within a minute or two, phones on that road report crawling speeds, and the segment's speed collapses. The server re-checks active routes that use it, and if a faster way exists now, it pushes a reroute suggestion. Re-checking only the routes through changed segments keeps it affordable.
interviewer
And if the driver ignores the suggestion?
candidate
We keep guiding them on their road, and update the arrival time honestly.

Wrap-up

Wrap-up
Next steps
1
Predicted traffic for trips later today
2
Walking, cycling and transit graphs
3
Offline maps: tiles and a graph on the phone
4
Watch ETA error and route time
INTERVIEWER'S FEEDBACK
Strong:threeparts,threedesigns,a
graphinmemorywithshortcuts,streamed
traffic,privacybuiltin.Nexttime:size
thegraphperserver.Verdict:stronghire.
interviewer
A few minutes left.
interviewer
What would you improve with more time?
candidate
A few things.
candidate
First, predicted traffic, for trips planned later in the day, from history and patterns. Second, walking, cycling and transit, each with its own graph and rules. Third, offline maps: tiles and a small routing graph on the phone, for places with no signal. And fourth, I'd watch how far arrival times are from real arrivals, and how long route searches take, per region.
interviewer
Which would you do first?
candidate
The watching. The arrival time is the number everyone judges us by.
interviewer
Okay, let's stop there. Very strong. You split tiles, routes and traffic early, kept the graph in memory with precomputed shortcuts, and explained how live traffic updates the costs without breaking them. The GPS stream and the privacy rules were well thought out. One small thing: say how much memory a region's graph needs on one server. I'd say a strong hire.
candidate
Thank you. I'll size the graph next time.
Interviewer's feedback

Strong: three parts, three designs, a graph in memory with shortcuts, streamed traffic, privacy built in. Next time: size the graph per server. Verdict: strong hire.

Score yourself

Interviewers score these seven things. Give your own attempt a tick for each one you did.

  • Asks before drawing. Agrees what the system does, and how well: scale, speed, consistency.
  • Turns users into requests a second and bytes a day, and says what the numbers decide.
  • A small, clear contract, and a data model that fits how the data is read.
  • A working path end to end before any detail. Every box has a reason.
  • Picks the hard parts, compares two options, and chooses one with a trade-off said out loud.
  • What breaks, what happens then, and how users notice. Retries, duplicates, limits.
  • Thinks out loud, checks in with the interviewer, and takes a hint without losing the thread.

0 of 7

Your progress stays on this device.
New System Design videos at 6 pm

Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.