Design Google Maps

Routing, ETA & Map Tiles System Design

Overview

Open Google Maps, and three things happen almost at once: the map renders under your finger as you pan and zoom, you type a place and it appears, and you tap "directions" and get a blue line from A to B with a time — "23 min, light traffic." Each of those is a separate hard problem at planet scale. Rendering the map is a precomputation and delivery problem — you cannot draw the whole world on demand, so you pre-slice it into map tiles and serve them from a CDN. Computing a route is a graph shortest-path problem over a road network with tens of millions of nodes. And the ETA on that route is a data problem — the travel time along each road depends on live traffic aggregated from millions of phones.

It is labeled "Hard" because the naive answers collapse at continental scale. Modeling roads as a road network graph and running plain Dijkstra from A to B works fine for a city but is far too slow across a continent — a single cross-country query would settle tens of millions of nodes and take seconds. Rendering every map view on request would melt any server farm. And treating the routing graph's edge weights as static ignores the entire point of live traffic. A strong answer separates the static road graph (which changes rarely) from the dynamic traffic weights (which change every minute), reaches for precomputation (contraction hierarchies) to answer routing queries in milliseconds, and serves precomputed tiles from a CDN.

In this walkthrough you'll scope the system, size it, model the data, design the API, draw the read and write paths, and then go deep on the three parts that matter: shortest-path routing with precomputation, ETA and live traffic, and map tiles and rendering.

Out of scope (say so): turn-by-turn voice navigation, multi-modal transit/walking/cycling routing, Street View, satellite imagery pipelines, indoor maps, lane-level guidance, and the place-search/ranking stack beyond a pointer to it. We keep the core: render the map, search a place, and route A→B with an ETA.

Functional requirements

• Render the map. Given a viewport (a bounding box and a zoom level), return the tiles needed to draw it. The client stitches them into a seamless map as the user pans and zooms.
• Search a place. Given a text query ("Blue Bottle Coffee") or an address, return matching locations with coordinates. (We treat this as a pointer to a search/geocoding subsystem, not the focus.)
• Route A→B. Given an origin and destination (lat/lng), return the fastest route as an ordered list of road segments, plus a total distance and an ETA.
• ETA with live traffic. The returned travel time reflects current traffic conditions, and can predict conditions for a future departure time.

Out of scope (state it): turn-by-turn navigation with rerouting mid-drive (mention it as an extension), transit/walking/cycling modes, Street View, and the full geocoding/place-ranking system.

Non-functional requirements

• Read-heavy, low-latency. Tile fetches and route requests vastly outnumber map-data updates. A route query must return in well under ~200 ms; tiles must stream instantly from an edge. This drives the whole design toward precomputation and CDN delivery.
• Routing must be fast at continental scale. A cross-country route touches a graph of tens of millions of edges. Plain Dijkstra settling millions of nodes per query is untenable. Precomputation (contraction hierarchies) must bring queries down to milliseconds.
• Static graph vs dynamic weights. The road topology changes rarely (new roads, closures) — days to weeks. Traffic changes every minute. The system must let live traffic update edge weights without rebuilding the expensive routing precomputation on every traffic tick.
• Freshness tolerance for traffic. An ETA that reflects traffic from ~1–2 minutes ago is fine. Sub-second traffic freshness is neither achievable nor necessary.
• Availability over perfection. A slightly suboptimal route, or an ETA that's a minute stale, is far better than an error page. Routing should degrade gracefully to free-flow (speed-limit) weights if the live-traffic feed is unavailable.
• Tile immutability and durability. Rendered tiles are content-addressed and immutable until the underlying map data changes; they must be durable in a blob store and globally available via CDN.

Estimations

State assumptions first; the point is to justify design choices, not to nail exact numbers.

Rounded assumptions

• Users: ~1B monthly, ~100M+ daily active. A user opens the map several times a day.
• Route requests: assume ~1B route requests/day → ~12K routes/sec average, call it ~50K/sec at peak. This is the query rate the routing engine must serve.
• Tile requests: each map view fetches a grid of ~10–20 tiles, and users pan/zoom constantly → easily hundreds of thousands to millions of tile fetches/sec at peak. This is why tiles must come from a CDN, not an origin.
• Road network graph: the global road network is on the order of ~100M+ nodes (intersections) and a few hundred million directed edges (road segments). Each edge stores endpoints, length, road class, and a traffic-time weight. Order-of-magnitude storage for the raw graph is tens to low hundreds of GB — it fits in memory on a fleet of routing servers when partitioned.
• Map tiles: a full raster pyramid from zoom 0 to ~20 is roughly a quadtree where level z has 4^z tiles. The deep zoom levels dominate; summing 4^z from z=0 to 20 puts a full planet raster pyramid on the order of a trillion-plus tiles / tens of petabytes, which is why you render popular areas eagerly and rare deep-zoom tiles on demand, then cache.
• GPS probes: ~100M active devices reporting location every few seconds → on the order of millions of probe points/sec flowing into the traffic pipeline. This is the raw material for edge-weight updates.

How the numbers affect the design

Core entities / data model

Five things are stored: the road graph (nodes + edges, the static topology), the edge weights (travel time, split into a static free-flow part and a dynamic live-traffic part), the routing precomputation (contraction shortcuts / partition data), the map tiles (rendered images/vectors keyed by tile coordinate), and the place index (for search — pointer only).

The Edge stores a static free_flow_time_s (length ÷ speed limit — the time with no traffic) as part of the topology. The dynamic live travel time lives separately in EdgeWeightLive, keyed by edge_id, so a traffic update is a small write to a fast store and never touches the multi-hundred-GB static graph. This separation is the backbone of the whole design.

The RoutingIndex is a derived structure, partitioned by region_id — the contraction-hierarchy shortcuts and node ordering (or partition overlay) are computed offline from the static Node/Edge topology. If it's lost, you rebuild it from the graph (an expensive batch job, but always possible). It is never the source of truth. A shortcut summarizes a path through contracted intermediate nodes, so unpacking one at the end of a query recursively expands it back into its underlying real edges and their polyline geometry — that's how a route of shortcuts becomes a drawable segment list.

The Tile table maps a tile coordinate (z, x, y) — the quadtree address — to a blob key and a version hash. The tile bytes live in a blob store; the DB holds only the pointer and version, exactly like storing a CDN URL instead of media bytes.

Where each lives. The static Node/Edge graph and the RoutingIndex are partitioned by region_id and held in memory on a fleet of routing servers (loaded from a durable blob/columnar store on startup). EdgeWeightLive lives in a fast in-memory store (Redis or a purpose-built key-value layer) keyed by edge_id, updated by the traffic pipeline. Tile bytes live in a blob store served through a CDN; the (z,x,y)→blob map is a small KV lookup. Place lives in a search index (Elasticsearch-style) — the pointer we don't design here.

API design

A handful of operations carry the system: fetch tiles, search a place, request a route, get an ETA for a future departure, and — on the write side — ingest GPS probes.

Fetch a map tile

GET /api/tiles/{z}/{x}/{y}.png        (raster)   or  .mvt (vector)
200 OK  (Cache-Control: public, max-age=86400, immutable-ish + version)
Returns: the tile bytes (served from CDN edge)

The client computes which (z, x, y) tiles cover its viewport and requests each. Served almost entirely from the CDN. z is the zoom level (quadtree depth); x/y are the tile's column/row at that level. The version/ETag lets the client revalidate cheaply when map data changes.

Search a place

GET /api/search?q=blue+bottle+coffee&near=37.77,-122.41
200 OK
Returns: { results: [ { place_id, name, lat, lng, node_id } ] }

Resolves text to coordinates (and the nearest graph node, so a route can start there). Backed by the place/geocoding index — a pointer, not the focus.

Request a route

POST /api/route
Body: { "origin": {lat, lng}, "destination": {lat, lng}, "depart_at": "now" }
200 OK
Returns: {
  "segments": [ { edge_id, geometry, name } ],
  "distance_m": 41234,
  "eta_seconds": 1380,
  "traffic": "light"
}

The core routing call. The service snaps origin/destination to their nearest graph nodes, runs the shortest-path query over the contraction hierarchy using current live edge weights, and returns the ordered segments plus a distance and a live-traffic ETA. depart_at may be a future time, in which case predicted (historical-pattern) weights are used (deep dive 2).

Get an ETA for a future departure

GET /api/eta?origin=...&destination=...&depart_at=2026-07-11T08:00:00Z
200 OK
Returns: { "eta_seconds": 2040, "confidence": "high" }

Same routing engine, but weights are drawn from the predicted traffic model for that time-of-day/day-of-week rather than the live feed. The split is deliberate: /api/route returns the full path plus ETA (the navigation call), while /api/eta returns only a travel time — cheaper when the caller wants a duration estimate and not a drawable route.

Ingest GPS probes

POST /api/probes
Body: { "device_token": "...", "samples": [ { lat, lng, ts, heading, speed } ] }
202 Accepted

The write endpoint for the traffic pipeline. Devices bulk-upload batches of anonymized GPS samples (many samples per call to amortize overhead), authenticated by a rotating device token and rate-limited per device to bound abuse. Identifiers are stripped at this boundary (see the privacy note in deep dive 2); the body feeds the map-matching stage.

High-level architecture

There are two families of paths: high-volume read paths (tile fetch, route query) served from precomputed structures and caches, and a continuous write/update path (GPS probes → aggregated speeds → live edge weights; and offline map-data builds → routing index + tiles). We'll draw the routing read path first because it's the hardest.

1. Read path — a route query

flowchart LR
    Client["Client"] -->|"POST /route\n(origin, dest)"| RouteSvc["Routing Service"]
    RouteSvc -->|"snap to nearest\ngraph nodes"| Snap["Node snap\n(spatial lookup)"]
    RouteSvc -->|"shortest path over\ncontraction hierarchy"| CH[("Routing Index\n(in-memory:\nstatic graph + shortcuts)")]
    RouteSvc -->|"read current\nedge travel times"| LW[("Live Edge Weights\n(Redis / KV)")]
    RouteSvc -->|"segments + distance + ETA"| Client

1. The Routing Service snaps origin and destination to their nearest graph nodes. This is a nearest-neighbor lookup over a spatial index: each Node carries a cell_id (geohash / quadtree cell), so snapping means computing the point's cell, then k-NN over the handful of nodes in that cell and its neighbors — the same spatial primitive used for proximity search in the Yelp breakdown.
2. It runs the shortest-path query over the in-memory contraction hierarchy — a bidirectional search that settles only a few thousand nodes instead of millions (deep dive 1).
3. For each edge it considers, it reads the live travel-time weight from the dynamic weight store — the static graph gives topology and free-flow time; the live layer supplies current traffic (deep dive 2).
4. It returns the ordered segments, total distance, and the summed ETA.

2. Read path — tile fetch

flowchart LR
    Client["Client"] -->|"GET /tiles/z/x/y"| CDN["CDN edge"]
    CDN -->|"cache hit\n(most tiles)"| Client
    CDN -.->|"miss: fetch origin"| TileStore[("Tile Blob Store")]
    TileStore -.->|"tile missing\n(deep zoom / rare area)"| Render["On-demand Renderer"]
    Render -.->|"render + store"| TileStore

1. The client computes covering (z,x,y) tiles for its viewport and requests them.
2. The CDN serves the vast majority from the edge cache — tiles are immutable per version, so hit rates are extremely high.
3. On a miss, the edge fetches from the tile blob store origin.
4. For rare deep-zoom tiles that were never pre-rendered, an on-demand renderer generates the tile, stores it, and serves it — subsequent requests are cache hits (deep dive 3).

3. Write path — traffic pipeline (GPS probes → live weights)

sequenceDiagram
    participant D as Devices
    participant ING as Probe Ingest
    participant MM as Map Matcher
    participant AGG as Speed Aggregator
    participant LW as Live Edge Weights

    D->>ING: GPS probe points every few seconds
    ING->>MM: batch of anonymized probes
    MM->>MM: snap each probe track to road edges
    MM->>AGG: per-edge speed samples
    AGG->>AGG: aggregate + smooth vs historical
    AGG->>LW: write updated travel_time_s per edge
    Note over LW: routing reads these live weights per query

Phones report anonymized location probes. A map-matching stage snaps each noisy track onto road edges, a stream aggregator computes a smoothed current speed per edge, and the result is written to the live edge-weight store. Routing reads those weights per query.

4. Write path — map-data build

The other write path is slow and rare: the road network itself changes. A new road opens, a bridge closes, a street is renamed. Fresh source data (OSM, government feeds, partner/field data) is validated, then a differential build computes just the delta against the current map rather than rebuilding the planet.

flowchart LR
    Src["Source data\n(OSM, partners,\nfield edits)"] -->|"validate + conflate"| Build["Differential\nmap build"]
    Build -->|"topology changed"| Route["Re-partition +\nre-customize routing"]
    Build -->|"geometry changed"| Tiles["Re-render +\nversion affected tiles"]
    Route --> CH[("Routing Index")]
    Tiles --> TileStore[("Tile Store / CDN")]

A topology change flows to the routing side — re-run the expensive partition/precompute phase for the affected region, then re-customize — and to the tile side — re-render only the tiles whose area intersects the change, under a new version. This is the answer to "what happens when a new road opens": it is a build-and-publish, not an online write, and it touches only the affected region and tiles.

5. Combined architecture

flowchart LR
    Client["Client"] --> GW["API Gateway + CDN"]
    GW -->|"GET /tiles"| CDN["CDN / Tile Store"]
    GW -->|"POST /route"| RouteSvc["Routing Service"]
    GW -->|"GET /search"| SearchSvc["Place Search"]
    RouteSvc --> CH[("Routing Index\n(static graph + CH,\nin memory)")]
    RouteSvc --> LW[("Live Edge Weights\n(Redis)")]
    Probes["GPS Probes"] --> Ingest["Probe Ingest"]
    Ingest --> MapMatch["Map Matcher"]
    MapMatch --> SpeedAgg["Speed Aggregator"]
    SpeedAgg --> LW
    SpeedAgg -.->|"roll up over time"| HistDB[("Historical\nTraffic Model")]
    MapBuild["Offline Map Build\n(topology changes)"] -->|"rebuild"| CH
    MapBuild -->|"re-render"| TileStore[("Tile Blob Store")]
    TileStore --> CDN

The routing read path, the tile read path, the live-traffic update path, and the offline map build are decoupled. A surge of GPS probes never slows a route query; re-rendering tiles after a map update never blocks routing. The static graph and the dynamic weights meet only at query time, where routing reads both.

Deep dives

1. Shortest-path routing with precomputation

This is the heart of the design and where the interview is won or lost. The setup is clean: model the road network as a directed weighted graph — nodes are intersections, edges are road segments, and each edge's weight is its travel time. Routing A→B is then a shortest-path search. The trap is stopping there and reaching for plain Dijkstra.

The options, worst to best for planet scale:

Dijkstra explores ~all nodes closer than the destination
settled nodes:   on the order of 10^6 to 10^7
per query time:  hundreds of ms to seconds
at 50K routes/sec: hopeless — CPU melts

flowchart TD
    Pre["Static graph\n(nodes + edges)"] -->|"order nodes by importance\ncontract one by one\nadd shortcut edges"| CHgraph["Augmented graph\n(+ shortcuts)"]
    Origin["origin node"] -->|"forward search\nupward only"| Meet["meeting node"]
    Dest["dest node"] -->|"backward search\nupward only"| Meet
    CHgraph --> Origin
    CHgraph --> Dest
    Meet -->|"unpack shortcuts\nto full segment list"| Route["final route"]

plain Dijkstra:  ~10^6 to 10^7 settled nodes
with CH:         ~10^3 settled nodes  (unpack shortcuts at the end)
query time:      low single-digit ms

The live-traffic problem with CH — and the fix. Because CH bakes weights into shortcuts, and traffic changes weights every minute, you cannot rebuild the full hierarchy per traffic tick. The standard resolution is Customizable Route Planning (CRP) — a different algorithm from CH, with no contraction and no shortcuts. CRP splits work into two phases over a multilevel graph partition:

1. Metric-independent phase (rare). Partition the graph into cells (a multilevel partition), and from the topology alone precompute the structure of each cell's overlay graph: which of the cell's boundary nodes connect to which other boundary nodes. No weights are involved yet — this depends only on the road layout, so it is run only when the road network itself changes.
2. Customization phase (cheap, frequent). Given a fresh set of edge weights (live traffic), recompute only the weights of those overlay arcs — the shortest boundary-to-boundary distance across each cell under the current weights. This is fast (seconds), embarrassingly parallel per cell, and incremental: only cells whose interior edges changed need re-customizing.

flowchart LR
    Topo["Static topology"] -->|"partition into cells\nbuild overlay structure\n(expensive, rare)"| Overlay["Overlay graph\n(boundary-to-boundary arcs)"]
    Live["Live edge weights\n(every minute)"] -->|"customization:\nrecompute overlay arc weights\n(cheap, per changed cell)"| Custom["Weighted overlay"]
    Overlay --> Custom
    Query["route query"] -->|"search over\noverlay + local cells"| Answer["fast route + ETA"]
    Custom --> Answer

This is the crux insight interviewers want: separate the topology precomputation (slow, rare) from the dynamic weight customization (fast, frequent), so live traffic updates queries in seconds without touching the expensive structural phase. (If you prefer to keep contraction, CCH — Customizable Contraction Hierarchies — is the separate customizable variant of CH: it fixes the contraction order from topology alone, then re-derives shortcut weights per customization. CRP partitions; CCH contracts. Don't blend the two.)

Partitioning for scale and updates. The cell partition also keeps long-distance routing cheap: a coast-to-coast route travels boundary-to-boundary across the overlay, only descending into full detail inside the origin and destination cells. And a traffic change in one city only forces re-customization of that city's cells — not the planet.

2. ETA and live traffic

Routing gives you the path; the ETA is the sum of the current travel time along its edges. That travel time is exactly the dynamic edge weight — so this deep dive is about where those weights come from and how they stay fresh.

The two ingredients of an edge weight. Each edge's travel time blends:

• A historical model — the typical speed on this edge for this time-of-day and day-of-week, learned from months of probe data. This is the fallback and the basis for predicted future-departure ETAs.
• A live signal — the current speed from recent GPS probes, when enough probes are available. Live overrides historical when the road is currently anomalous (an accident, a jam).

The written live weight is a smoothed blend: travel_time = f(live_speed, historical_speed) weighted by how many recent probes support the live number. On roads with sparse probe coverage you fall back to historical or free-flow (speed-limit) time.

The probe pipeline. Millions of phones report anonymized location every few seconds. The pipeline:

flowchart LR
    Probes["GPS probes\n(millions/sec)"] -->|"anonymize + batch"| Ingest["Ingest\n(stream)"]
    Ingest -->|"snap tracks to edges"| MapMatch["Map Matching"]
    MapMatch -->|"per-edge speed samples"| Agg["Windowed Aggregation\n(e.g. 1-min windows)"]
    Agg -->|"blend with historical"| Blend["Speed Blender"]
    Blend -->|"write travel_time_s\nper edge"| LW[("Live Edge Weights")]
    Agg -.->|"roll up daily"| Hist[("Historical Model")]

1. Ingest anonymized probes as a stream (privacy: drop identifiers, aggregate; never store an individual's raw trajectory tied to identity).
2. Map-match each noisy track onto the correct edges — a phone on an overpass must be attributed to the highway, not the surface street beneath it.
3. Aggregate speeds per edge over a sliding window (~1–2 minutes) so the ETA reflects near-current conditions without reacting to a single anomalous sample.
4. Blend with the historical model to smooth sparse-coverage edges, and write the resulting travel_time_s to the live edge-weight store.

How updates reach routing. The live weights are read at query time and fed into the customization phase of deep dive 1. There are two coupling points:

• Query-time read. For the origin/destination local search, routing reads live edge weights directly — always current.
• Customization refresh. For the precomputed overlay, the customization phase re-derives overlay-arc weights from the fresh live weights each cycle — incrementally, re-customizing only the cells whose interior edges changed this cycle — so long-distance routing also reflects traffic without re-touching quiet regions.

Predicting a future departure. For "leave at 8am tomorrow," there is no live signal yet. Use the historical model: the predicted speed for each edge at that time-of-day/day-of-week. A long route may span an hour of driving, so a good ETA advances the clock as it traverses edges — using the predicted weight for the time you'll actually be on that edge, not the departure time. This time-dependent routing is a refinement worth naming.

3. Map tiles and rendering

Rendering is a precomputation-and-delivery problem. You cannot draw an arbitrary view of the planet on demand at scale, so you pre-slice the world into tiles arranged as a quadtree and serve them from a CDN.

The tile quadtree. The world is projected (Web Mercator) into a square, and each zoom level z divides that square into a 2^z × 2^z grid of quadtree tiles. Zoom 0 is one tile for the whole world; each step down splits every tile into four. A tile is addressed by (z, x, y). The client, given its viewport, computes exactly which (z, x, y) tiles cover the screen and requests them — then stitches the grid into a seamless map. Panning fetches the next column of tiles; zooming jumps to the next level.

flowchart TD
    Z0["z=0\n1 tile (world)"] --> Z1["z=1\n4 tiles"]
    Z1 --> Z2["z=2\n16 tiles"]
    Z2 --> Zdots["...\neach tile splits into 4"]
    Zdots --> Zdeep["z=~20\nstreet level"]
    View["viewport\n(bbox + zoom)"] -.->|"compute covering (z,x,y)"| Grid["tile grid\nclient stitches"]

Raster vs vector tiles.

Rendering strategy — eager vs on-demand. A full planet pyramid at every zoom is astronomically large, and most deep-zoom tiles (the middle of an ocean at z=19) are never viewed. So:

• Eagerly pre-render popular areas and all shallow zoom levels (z=0 through ~z=12), which cover the bulk of real traffic. Store them in the blob store, front them with the CDN.
• Render rare deep-zoom tiles on demand, then cache: first request for an obscure tile triggers a render, stores the result, and warms the CDN, so the second request is a cache hit. This bounds storage to what people actually look at.

Serving via CDN. Tiles are static bytes, requested millions of times per second — the textbook CDN workload. Set long cache lifetimes and rely on versioned tile URLs: each tile carries a version derived from the underlying map-data build, so a tile URL is effectively immutable. When map data changes, you don't invalidate — you publish a new version.

Updating tiles when map data changes. A new road, a renamed street, a closed bridge — the offline map build re-renders only the affected tiles (the ones whose geographic area intersects the change) at every affected zoom level, writes them under a new version, and lets the CDN pick them up as clients request the new version. You never re-render the whole planet for a local change; you re-render the intersecting tiles.

Tradeoffs & bottlenecks

• Precomputed contraction hierarchies vs on-the-fly A.* CH gives millisecond queries but bakes weights into shortcuts, so live traffic demands a customizable approach — CRP (partition into cells + cheap overlay-weight customization) or its contraction-based cousin CCH. A* / ALT is slower per query but far cheaper to keep fresh when weights change constantly. Real systems lean on the customizable-precompute approach to get both speed and freshness.
• Static topology vs dynamic weights. The central split: precompute the expensive structure (CRP overlay / CCH order) on the stable graph; overlay fast-changing traffic weights via a cheap, per-cell customization. Rebuilding the structure on every traffic tick is the canonical failure.
• Raster vs vector tiles. Raster is simple and client-trivial but huge and inflexible; vector is compact and restylable but needs a client renderer and per-zoom geometry simplification. Vector wins at scale.
• Eager vs on-demand tile rendering. Pre-rendering everything wastes petabytes on never-viewed tiles; rendering everything on demand makes the renderer a bottleneck. Pre-render shallow zooms + popular areas, render rare deep tiles lazily and cache.
• Live-traffic freshness vs cost. Tighter aggregation windows and more frequent customization give fresher ETAs but cost more compute and react to noise. A ~1–2 minute window is the sweet spot.
• Graph partition granularity. Finer partitions localize traffic re-customization (a jam in one city touches one partition) but add cross-boundary routing overhead. Coarser partitions do the reverse. Tune to update frequency and query length.
• Availability degradation. If the traffic pipeline stalls, routing degrades to historical then free-flow weights rather than failing — a deliberate, graceful fallback.

Extensions if asked

• Turn-by-turn navigation with rerouting. Continuously map-match the driver's live position and re-run the (cheap, local) route query when they deviate or when traffic ahead changes. Reuses the routing engine plus a streaming position channel.
• Multi-modal routing (transit, walking, cycling). Different graphs and weights — transit adds a time-dependent schedule graph (departures at fixed times) layered on the road/foot graph. A separate but analogous shortest-path problem.
• Ride-share ETA. The same ETA engine feeding driver-to-rider and trip-duration estimates; the routing/ETA core is shared infrastructure.
• Place search and geocoding. Resolving "coffee near me" or an address to coordinates is a separate read-path system — an inverted index with a geo field, closely related to the proximity-search design in the Yelp proximity-search breakdown; cross-reference rather than re-derive.
• Reverse geocoding. Coordinates → nearest address/place, a spatial lookup against the place index.
• Toll/eco/shortest-vs-fastest alternatives. Swap the edge-weight function (time, distance, fuel, avoid-tolls) and re-customize — the same graph, different weights.

What interviewers look for & common mistakes

What interviewers usually reward:

• Modeling roads as a weighted graph and naming the shortest-path problem — nodes = intersections, edges = road segments, weight = travel time — then immediately recognizing that plain Dijkstra doesn't scale.
• Reaching for precomputation — contraction hierarchies (or ALT/A* with landmarks) to bring continental queries down to milliseconds, and explaining why (shortcuts let the search skip whole stretches).
• The static-topology vs dynamic-weight split — the single most important insight: don't rebuild the routing precomputation on every traffic change; overlay live weights via a cheap customization phase.
• The traffic pipeline — GPS probes → map-matching → windowed aggregation → blend with historical → live edge weights, plus the degradation ladder (live → historical → free-flow).
• Tiles as a quadtree served from a CDN — precomputed, versioned, immutable tiles; eager for popular/shallow, on-demand-then-cache for rare deep zooms; raster vs vector tradeoff.
• Separating ETA from routing conceptually while sharing the mechanism — the ETA is the sum of the same edge weights, kept fresh by the traffic pipeline.

Before you finish, do a quick mistake check:

• Did you model the road network as a directed weighted graph and reject plain Dijkstra at continental scale?
• Did you introduce precomputation (contraction hierarchies or ALT) and explain the query speedup?
• Did you separate the static routing graph from the dynamic traffic weights, and avoid rebuilding the precomputation on every traffic tick?
• Did you describe the GPS-probe → map-match → aggregate → blend pipeline that produces live edge weights?
• Did you cover predicting a future-departure ETA from a historical model, and the live→historical→free-flow degradation ladder?
• Did you tile the map as a quadtree, serve it from a CDN, and version tiles instead of invalidating them?
• Did you weigh raster vs vector tiles and choose eager-vs-on-demand rendering deliberately?