Design Google Maps: the system design interview walkthrough

Design Google Maps: the system design interview walkthrough

The request to design Google Maps sounds like one line — type a start and a destination, get the fastest route — and that one line hides the whole interview. Do it for one city and you reach for a single Dijkstra call over a modest graph; do it for the whole planet, over a road network of hundreds of millions of edges, returning a route in well under a second while live traffic keeps changing the weights, and it becomes a graph-representation-plus-precomputation problem with a dozen sharp edges. This is one of the most revealing maps system design prompts because it forces the thing most candidates skip: the moment you say "just run shortest path," the interviewer asks over what graph, how big, and how fast.

The round turns on one structural insight. "Find a route from A to B" sounds like one Dijkstra call, but the road network is a weighted graph — intersections are nodes, road segments are edges weighted by travel time — and naive Dijkstra explores far too much of a continent-sized graph to answer in time. So you partition the graph and precompute long-haul routes, and you overlay live traffic as dynamic edge weights that keep the answer honest. Get that one reframe — this is a routing-plus-precomputation-plus-real-time-traffic problem, not one clever algorithm call — and the rest of the system design interview is deciding how to represent the map, how to make the routing system fast at planet scale, and how fresh traffic reshapes both the route and the ETA. This walkthrough follows the path a strong candidate draws on the whiteboard — requirements, estimate, API and data model, high-level design, then the deep dives — and at each step it names the follow-up the interviewer uses to tell a memorised answer from an engineer who understands the tradeoff.

How the maps round is actually run

A maps round runs about 45 minutes on a shared canvas — you draw the boxes and arrows while you talk, and the interviewer interrupts. It is a favourite because the one-line problem opens onto deep water fast: the moment you draw "user asks for a route, service returns one," the question becomes what is the graph and how do you search it quickly, and every answer after that (scale, freshness, ETA) compounds from how you represented the map. The clock is a touch tighter here than a 60-minute round, so the premium on getting to the graph reframe early is even higher.

The interviewer rarely lets "just run Dijkstra" stand. "A route from one coast to the other crosses hundreds of millions of edges — how do you answer in well under a second instead of exploring half a continent?" That question — routing at planet scale — is the one a copied answer can never rehearse, and the one this round is really testing.

The rounds here are modelled on how the loop runs, not scraped from any candidate's recall. What matters for prep is the shape: a blank canvas, a clock, and a follow-up after every decision you make.

The five-step framework for any HLD round

Every high-level design answer fits the same spine. Say it out loud at the start so the interviewer knows you have a plan, then walk it:

1. Clarify requirements — functional and non-functional, and what you are explicitly not building.
2. Estimate — graph size, routing QPS and latency, GPS ping volume and tile load, to justify every later choice.
3. High-level design — the boxes and arrows: client, location service, routing service, traffic pipeline, tile service.
4. Deep dive — the two or three decisions that actually decide this system.
5. Follow-ups — bottlenecks, failure modes, and what you would change at ten times the scale.

What the debrief measures

The score is not "right or wrong design." A good HLD debrief reads on four dimensions, and every move below maps to one: problem solving (did you reach a weighted graph plus a spatial index, partitioned and precomputed, with traffic as dynamic weights), communication (did you say why the edge weight is travel time, not distance, in a sentence), technical execution (graph partitioning, contraction hierarchies, geohash/S2 cells, map matching, dynamic edge weights), and time management (did you spend your 45 minutes on representation, routing, and traffic, not on the tile cache). Reading a walkthrough teaches the design; it does not teach you to deliver it on the clock while someone pushes back.

Step 1 — Requirements: what a maps and navigation system must do

Spend the first few minutes here. Jumping to boxes before you have scoped the problem is the fastest way to design the wrong system.

The sentence that earns points: "The hard part isn't the shortest-path algorithm, it's running it over a planet-scale weighted graph in under a second while the weights keep changing — so the core of the design is how I represent and partition the graph, what I precompute, and how live traffic feeds back as dynamic edge weights." Say that and you have framed the entire design before drawing a box.

Step 2 — Capacity estimation (back of the envelope)

Estimation here is about proving one thing: the hard axis is fast routing over a huge, changing graph, not a single algorithm call.

Two conclusions fall out, and you should say both out loud. First, the graph cannot be searched end to end per query — hundreds of millions of edges and a sub-second budget mean you precompute long-haul routes and only do a short local search at query time. Second, traffic is a stream, not a store — millions of pings per second are aggregated into per-segment speeds and discarded; you keep the aggregate, not the firehose. You have now pointed the interview at the real deep dives — representation, precomputed routing, and live traffic — before anyone asked.

Step 3 — API and data model

The API is deliberately small: ask for a route, ask what is nearby, ask for a tile.

The data model is thin. The graph is the spine; the spatial index and the traffic samples hang off it:

Step 4 — High-level design: routing, traffic and tiles

Now the boxes. A client asks for a route, a nearby lookup, or a tile; three distinct back-end paths answer those three asks over the same underlying map. Around that sit the pieces that make scale and freshness work:

• Location / API service: handles geocoding (turning an address into a coordinate) and the nearest-road lookup, resolving a raw lat/long to a node on the graph via the spatial index.
• Routing service: owns the road graph, sharded by region, with precomputed shortcuts between regions; it stitches a short local search to the precomputed long-haul segments and returns a path plus ETA.
• Traffic service: a write-heavy pipeline that ingests GPS pings, map-matches each to a road segment, aggregates per segment, and continuously updates edge weights on the graph.
• Tile service: serves pre-rendered map tiles at each zoom level from a CDN, a pure read path independent of routing.

Say explicitly that routing and tiles are two separate read paths over the same map data, and that the traffic pipeline is a write-heavy stream that continuously mutates the routing graph's weights — the graph is not static. Naming that unprompted — that the map is read in two ways and written by a firehose at the same time — is a signal the interviewer is listening for.

Deep dive: the map as a graph and a geospatial index

This is the first decision that actually decides the round. What is the map, in data-structure terms, and why does that shape everything else?

The road network is a weighted graph: each intersection is a node, each road segment is a directed edge, and each edge's weight is its travel time, not its raw distance. Alongside the graph, the world is indexed spatially — carved into cells by a scheme like geohash, Google's S2 cells, or a quadtree — so you can answer "what is near this lat/long" without scanning the planet. The spatial index does two distinct jobs:

Storing the graph sharded by region falls straight out of its size: no single machine holds hundreds of millions of edges, so each shard owns a geographic area and the spatial cells tell you which shard a coordinate belongs to.

"Why is the edge weight travel time, not distance — and how do you find the nearest road to a raw GPS point?" Because the user wants the fastest route, and a longer motorway often beats a shorter congested street, so time is the honest weight. For the nearest road, you take the point's geohash / S2 cell, search only the segments in that cell and its neighbours, and snap to the closest one — a bounded local search instead of scanning the whole map.

System Design
HLD · Search & discovery · 45 min
Design Google Maps out loud, with follow-ups

Practise on Zynter →

Deep dive: routing at planet scale

This is the decision most candidates under-think. Representing the map as a graph is easy; the follow-up is always "now the graph has hundreds of millions of edges and I want an answer in milliseconds — how?"

Plain Dijkstra or A* is too slow globally. Dijkstra explores outward from the origin until it reaches the destination, so a cross-continent query touches a huge fraction of the graph; even A* with a straight-line heuristic still expands far too many nodes when the two points are a continent apart. You cannot pay that per query under a sub-second budget. So you precompute:

In practice you combine them: a query stitches a short local search at each end with precomputed long-haul segments (boundary paths or shortcuts) across the middle, and uses A* with a good heuristic for whatever local remainder is left. That is what cuts a coast-to-coast route from seconds of frontier exploration to milliseconds.

"A route from one coast to the other crosses hundreds of millions of edges — how do you answer in well under a second?" You never search the whole graph. The graph is partitioned and you precompute boundary-to-boundary paths (and contraction-hierarchy shortcuts), so a query is a short local search at each endpoint plus a hop across precomputed long-haul segments, with A* filling the small remainder — milliseconds instead of exploring half a continent.

System Design
HLD · Search & discovery · 45 min
Defend planet-scale routing out loud

Practise on Zynter →

Deep dive: real-time traffic and ETA

Representation and routing decide how you find a path; this decides whether that path and its ETA match the road right now. The follow-up is always the live case.

Traffic is a feedback loop that continuously rewrites the graph's weights. The pipeline is short and each stage matters:

• Ping: drivers' phones send GPS pings — a lat/long and a timestamp — millions per second.
• Map-match: each ping is snapped to a road segment (the same nearest-road lookup the spatial index serves), turning a noisy coordinate into "this car is on this edge, moving this fast."
• Aggregate: pings are aggregated per segment into a current speed estimate; you keep the aggregate and discard the raw firehose, because storing every ping is neither affordable nor useful.
• Update weights: the aggregated speed is written back as the segment's dynamic edge weight (live_weight) on a near-real-time cadence — seconds to a couple of minutes — so the graph the router reads reflects reality.
• Reroute: the very next routing query reads the updated weights, so new routes avoid the jam and the ETA is computed from live speeds, not free-flow ones.

Where live data is thin — a quiet road, a brief gap — historical patterns (typical speed for this segment at this time of day and day of week) fill in, so an ETA is never guessing blind. And because precomputed long-haul segments were built on weights that just changed, the system recomputes or adjusts the affected precomputation incrementally — you re-run only the shortcuts and boundary paths that the changed edges touch, not the whole planet.

"A highway jams at 5pm — how does the very next person's route and ETA reflect it?" The cars already on that highway are sending slow GPS pings; those get map-matched to the segment, aggregated into a lower current speed, and written back as a heavier edge weight within seconds to minutes. The next routing query reads that heavier weight, so it either routes around the jam or returns an ETA computed from the real, slower speed — no manual intervention, just the feedback loop closing.

The follow-ups that decide the maps round

Scan the probes from each deep dive and they rhyme. Master these five and you are ready for a version of the question that is not drawn exactly like this one.

• "Why is the edge weight travel time, not distance?" → Because the user wants the fastest route, and a longer motorway often beats a shorter congested street; weighting by time is what makes the route match how people actually drive. (communication)
• "A cross-continent route touches hundreds of millions of edges — how do you answer in milliseconds?" → You never search the whole graph: partition it, precompute boundary-to-boundary paths and contraction-hierarchy shortcuts, and stitch a short local search at each end to precomputed long-haul segments. (problem solving)
• "A highway jams — how does the next route and ETA reflect it?" → Slow GPS pings are map-matched, aggregated into a lower current speed, and written back as heavier edge weights within minutes; the next query reads them and reroutes, and the ETA uses live speeds. (technical execution)
• "How do you find the nearest road to a raw GPS point?" → Bucket the world into geohash / S2 / quadtree cells; look up the point's cell and search only that cell and its neighbours, snapping to the closest segment in roughly constant time. (technical execution)
• "Millions of pings a second — do you store them all?" → No — you aggregate per segment on the fly into a current speed and discard the raw pings, keeping the aggregate plus historical patterns, because the firehose is a stream, not a store. (problem solving)

Each maps to a debrief dimension. Reading this list teaches you the answers; it does not teach you to deliver them while someone interrupts — that only comes from saying them out loud.

How to prepare: a one-week plan

You do not need fifty systems. You need this one cold and the framework automatic, so the next "design X" is just new nouns in the same five steps.

• Days 1–2: Learn the five-step framework until it is reflex. Do the maps system end to end on paper — requirements, estimate, API, data model, the routing-traffic-tiles boxes.
• Days 3–4: Drill the representation and routing deep dives: the weighted graph, the spatial index's two jobs, why naive Dijkstra is too slow, and how partitioning and contraction hierarchies make it milliseconds. Say each tradeoff in one sentence.
• Days 5–6: Own live traffic and ETA — the ping → map-match → aggregate → update → reroute loop, dynamic edge weights, historical fallback, and incremental recomputation. Answer each of the five follow-ups out loud.
• Day 7: A full timed round of about 45 minutes, narrating the whole way, with someone (or something) interrupting. This is the rep that counts.

This post is the deep walkthrough behind one row of the broader Top 25 system design interview questions — once the maps design is automatic, the same spine carries the rest of the list.

Frequently asked questions

How do I design Google Maps step by step?

Follow the five-step HLD framework. Clarify requirements (route plus ETA between two points, render tiles at many zoom levels, nearby lookup, reflect live traffic); estimate to show the hard axis is fast routing over a huge, changing graph, not one clever algorithm; define the small API (route, nearby, tiles) with a thin node/edge/spatial-cell/traffic-sample model; draw the design (client to a location service for geocoding and nearest-road lookup, a routing service over a region-sharded graph with precomputed shortcuts, a traffic pipeline that ingests GPS pings and updates edge weights, and a tile service on a CDN); then deep-dive the decisions that matter — the graph and spatial index, planet-scale routing, and real-time traffic. Finish on the follow-ups about latency and freshness.

Why is the road network modelled as a weighted graph?

Because routing is a shortest-path problem, and the natural data structure for shortest path is a graph: intersections become nodes and road segments become directed edges. The key choice is the edge weight — it is travel time, not raw distance, because the user wants the fastest route, and a longer motorway segment often beats a shorter congested side street. Weighting edges by time (and letting that time change with traffic) is what makes the computed route match how people actually drive, rather than just the shortest line on the map.

How does Google Maps return a route so fast at planet scale?

It never searches the whole graph per query. A plain Dijkstra or A* search over a continent-sized graph of hundreds of millions of edges would explore far too much to answer in under a second. Instead the graph is partitioned into regions with precomputed shortest paths between boundary nodes, and/or contraction hierarchies add shortcut edges that let a query skip over unimportant nodes. A query then does a short local search at each endpoint and stitches precomputed long-haul segments across the middle, with A* filling the remainder — turning seconds of exploration into milliseconds.

What is a geospatial index and why does Google Maps need one?

A geospatial index carves the world into cells using a scheme like geohash, Google's S2 cells, or a quadtree, and buckets points and road segments into those cells. It does two jobs. First, nearest-point lookup: a GPS fix is a raw lat/long, so you find its cell and search only that cell and its neighbours to snap it to the nearest road in roughly constant time, instead of scanning the planet. Second, tile serving: the same cell hierarchy lets you fetch exactly the pre-rendered map tiles a viewport covers. It is the index that connects raw coordinates to the graph and to the map image.

How does real-time traffic change routes and ETAs?

It is a feedback loop that rewrites the graph's weights. Drivers' phones send millions of GPS pings a second; each ping is map-matched to a road segment, pings are aggregated per segment into a current speed, and that speed is written back as the segment's dynamic edge weight within seconds to minutes. The next routing query reads the updated weights, so it routes around jams and computes the ETA from live speeds rather than free-flow ones. Where live data is thin, historical speed patterns for that segment and time of day fill the gap, and only the precomputation touching changed edges is recomputed incrementally.

How do I practise a system design interview out loud?

Reading a walkthrough is not the same as defending a design while someone interrupts. On Zynter, the HLD track runs live voice rounds modelled on how real system design loops run — you talk through a shared design on the canvas, and a voice interviewer pushes with the follow-ups above one at a time, then gives you a debrief on problem solving, communication, technical execution, and time management. The score is a practice signal, not a hiring decision.

Practise it on Zynter

You can read the whole design. The round is won on routing at scale and live traffic.

Pick the Maps and Navigation round, draw the routing-traffic-tiles design on the canvas, and defend it out loud to a voice interviewer that keeps asking "a cross-continent route — how do you answer in milliseconds?" and "a highway jams at 5pm — how does the next ETA reflect it?" — then read the debrief. Zynter.ai is on-demand mock interviews modelled on real company loops, with 150+ rounds across 20 companies including the HLD system design track (Sep 2026).

Practise the Maps round →
Browse all interview tracks