04QuestionsGoogle Maps

04 · Worked prompt

Google Maps

Design geospatial indexing, tile delivery, live traffic ingestion, and route computation.

40 minInterview blueprint

INTERVIEW RUBRIC

What a passing answer must show

100 points · 45 minutes

20pts
Scope the problem
0–5 min
Prioritize the core flows, state the scale, and name the non-goals.
15pts
Define contracts
5–10 min
Identify durable entities, APIs, idempotency, and the source of truth.
30pts
Complete the diagram
10–25 min
Trace one write path and one read path. Label the commit boundary and async work.
20pts
Lead one deep dive
25–38 min
Choose the highest-risk trade-off and explain the mechanism, alternative, and cost.
15pts
Prove reliability
38–45 min
Walk a failure, recovery, metric, bottleneck, and evolution path.

DRAW THIS FIRST

One complete box-and-arrow design

Design geospatial indexing, tile delivery, live traffic ingestion, and route computation.

Google Maps system architecture. A versioned road graph is truth; traffic overlays and route caches are freshness-bounded derivatives. Request path: Maps clients to Geo edge to Traffic ingestion to Road graph store. Asynchronous path: Probe stream to Traffic processors. Read path: Route service to Traffic overlay/cache. External dependency: Tile/object storage. — Google Maps · system architecture

DEFEND THE DIAGRAM

Explain every boundary before adding more boxes.

A versioned road graph is truth; traffic overlays and route caches are freshness-bounded derivatives.

INTERVIEW CONTRACT

Design geospatial indexing, tile delivery, live traffic ingestion, and route computation.

CAPACITY QUESTIONS TO QUANTIFY

Global graph · viewport-heavy reads · sub-second routes · continuous traffic. State average and peak load, stored bytes, bandwidth or open connections, and the growth horizon before choosing a partitioning strategy.

End-to-end walkthrough

Trace the architecture in this order.

01
Enter and classify the request
Maps clients → Geo edge
Route + live probes enters over HTTPS / RPC. Geo edge handles identity, admission, routing, and request context; it deliberately does not own domain truth.
02
Validate, then cross the commit boundary
Geo edge → Traffic ingestion → Road graph store
Traffic ingestion receives the command, checks invariants and retry identity, then uses publish graph version to update Road graph store. The user-visible mutation is accepted only after this boundary succeeds.
03
Move replayable work off the request path
Traffic ingestion → Probe stream → Traffic processors → Traffic overlay/cache
Traffic ingestion emits publish after commit; Traffic processors uses consume and project / update to build Traffic overlay/cache. Consumers must tolerate duplicate delivery and stale retries because this path is asynchronous.
04
Serve reads from the right authority
Geo edge → Route service → Traffic overlay/cache / Road graph store
Route service uses overlay weights for the common, read-optimized path and strong read when correctness or repair requires authoritative state. The API must state the freshness promise instead of hiding it.
05
Contain the dependency boundary
Route service → Tile/object storage
dependency call crosses into Tile/object storage. Treat timeouts as ambiguous, use a deadline and idempotent retry or reconciliation, and keep the core state recoverable when the dependency is unavailable.

Ownership ledger

Why each box exists—and what it must defend.

Component	Owns	Why it exists	Interviewer probe
Geo edgeRegion route + rate limits	Identity, admission, routing	Protects the system edge and attaches trusted context before domain work begins.	Timeout budgets, quotas, regional routing
Traffic ingestionMap-match + validate probes	Write invariants and retry identity	Serializes or conditionally applies state changes before acknowledging success.	Concurrent writes, deduplication, hot ownership
Road graph storeVersioned topology	Authoritative durable state	Provides the one record used to resolve disputes, recover, and rebuild projections.	Partition key, replication, consistency
Probe streamRegion/road partitions	Durable asynchronous handoff	Absorbs bursts and lets slow or optional work retry independently of the request.	Ordering key, lag, retention, dead letters
Traffic processorsWindow speeds + confidence	Replayable processing	Runs expensive, fan-out, or side-effecting work with leases and bounded retries.	Idempotency, poison work, autoscaling
Traffic overlay/cacheEdge weights + route cache	Rebuildable query state	Shapes data for the dominant reads without weakening the write-side invariant.	Freshness, versioning, rebuild time
Route serviceGraph search + alternatives	Read composition and freshness policy	Chooses authoritative or derived state and returns a stable client contract.	Fan-out, cache policy, partial results
Tile/object storageVector tiles + map assets	External capability, not local truth	Keeps a specialized or third-party concern behind a replaceable contract.	Ambiguous timeout, circuit breaking, fallback

Physical design

Name the database, shard key, indexes, and guarantees.

Database + storage: Versioned graph files plus an in-memory graph engine serve roads; Cassandra/Scylla or stream state stores live traffic; object storage/CDN serves tiles.
Partitioning / sharding: Partition traffic and graph ownership by S2/H3 cell or region. Hierarchical arterial graphs handle routes crossing many regions.
Indexes: Spatial cell→edge, edge_id/version, traffic (region, edge_id, event_time), and tile (zoom, x, y, version) indexes.
Replication + consistency: A route stays on one graph version. Traffic is a freshness-bounded overlay; stale traffic hurts ETA, not topological correctness.
Cache, queue + recovery: Event-time stream processors publish confidence-scored weights. Cache tiles globally and routes by cell pair plus graph/traffic version.
Capacity math: Estimate route QPS, probes/sec, graph/tile TB, overlay freshness, dense-metro skew, and route CPU per alternative.
Alternative rejected: Relational shortest-path queries do not meet large-graph latency; a versioned memory graph plus overlays earns specialization.

Deep-dive candidates

Pick one risk and explain the mechanism, alternative, and cost.

Routing algorithm

Use hierarchical routing or precomputed shortcuts for the stable graph, then customize edge weights

Plain Dijkstra over a continent misses the scale target

Version consistency

Pin one graph version across geocoding, routing, and returned geometry

Mixed versions create impossible turns

Traffic quality

Weight observations by age, coverage, and confidence and cap abrupt changes

Fresh data is not automatically trustworthy

Failure pressure test

Show detection, containment, recovery, and evidence.

Traffic stream late

Fall back to historical or base weights with freshness label

traffic coverage and age

Bad graph release

Roll back version pointer while immutable tiles and graph remain available

route error regression

Hot metro region

Partition and replicate regional routing data

regional CPU saturation

Before you finish, explicitly cover

Functional requirements and non-goals
Peak traffic, storage, bandwidth, and growth
Entities, APIs, idempotency, and pagination
Source of truth and consistency promise
Partition key, replicas, caches, and hot spots
Retries, backpressure, failover, and reconciliation
Latency, saturation, correctness, and recovery metrics
Security, migration, cost, and multi-region evolution

SAY THIS WHILE YOU DRAW

A four-part talk track

Scope
“I’ll prioritize render map viewports globally and geocode places and search nearby pois.”
Scale
“The design changes around global graph · viewport-heavy reads · sub-second routes · continuous traffic.”
Decision
“Precompute stable structure; preserve live search for traffic and constraints.”
Risk
“The first failure I want to pressure-test is: Version mismatch and bad traffic data can create unstable or impossible routes.”

Reference details

Open these only after you can explain the diagram above without reading.

01Requirements and state lifecycle4 requirements

Render map viewports globally
Geocode places and search nearby POIs
Compute routes under constraints
Incorporate live traffic without destabilizing results

Google Maps · state lifecycle

state lifecycle

Each transition must be durable, observable, and safe to retry.

candidate graph

validated

published

retired

02Data model and APIs4 entities · 3 interfaces

Core entities

RoadGraphVersionversion, region, published_atOwner: Map pipeline

RoadEdgeedge_id, nodes, geometry, base_costOwner: Graph store

TrafficWeightedge_id, speed, observed_at, confidenceOwner: Traffic service

RouteResultrequest_id, graph_version, path, costOwner: Route service

External interfaces

GET /v1/tiles/{z}/{x}/{y}?version={v}

Serve immutable vector or raster tiles

POST /v1/routes

Compute route for origin, destination, mode, and constraints

GET /v1/search?query={q}&near={lat,lng}

Return geocoded and ranked places

03Deep dives and trade-offsChoose one

Routing algorithm

Use hierarchical routing or precomputed shortcuts for the stable graph, then customize edge weights

Plain Dijkstra over a continent misses the scale target

Version consistency

Pin one graph version across geocoding, routing, and returned geometry

Mixed versions create impossible turns

Traffic quality

Weight observations by age, coverage, and confidence and cap abrupt changes

Fresh data is not automatically trustworthy

04Failures, recovery, and evidence3 scenarios

Traffic stream late

Fall back to historical or base weights with freshness label

traffic coverage and age

Bad graph release

Roll back version pointer while immutable tiles and graph remain available

route error regression

Hot metro region

Partition and replicate regional routing data

regional CPU saturation

05What makes the answer seniorInterviewer signals

Separate offline map building from online routing
Name the graph version in the request path
Discuss route quality and stability, not only raw latency
Primary trade-off: Precompute stable structure; preserve live search for traffic and constraints.

BEFORE THE NEXT QUESTION

Can you redraw it from memory?

Name the source of truth.
Trace the write and read paths.
Defend one trade-off.
Recover from one failure.

Scope the problem

Define contracts

Complete the diagram

Lead one deep dive

Prove reliability

Write

Propagate

Read

Trace the architecture in this order.

Enter and classify the request

Validate, then cross the commit boundary

Move replayable work off the request path

Serve reads from the right authority

Contain the dependency boundary

Why each box exists—and what it must defend.

Name the database, shard key, indexes, and guarantees.

Pick one risk and explain the mechanism, alternative, and cost.

Routing algorithm

Version consistency

Traffic quality

Show detection, containment, recovery, and evidence.

Traffic stream late

Bad graph release

Hot metro region

Reference details

Core entities

External interfaces

Routing algorithm

Version consistency

Traffic quality

Traffic stream late

Bad graph release

Hot metro region

Can you redraw it from memory?