Google Maps
Serve map tiles, place search and traffic-aware routes while separating geographic data versions from rapidly changing traffic.
Serve map tiles, place search and traffic-aware routes while separating geographic data versions from rapidly changing traffic. This worked design targets SDE-3; the scale figures below are exercise assumptions, not claims about a named company's implementation.
Clarify the prompt
| Ask the interviewer | Decision to record |
|---|---|
| Map browsing, navigation, place search or all three? | Start with one route request and tile browsing. |
| Driving, walking and transit? | Each has different edge restrictions and costs. |
| Which regions, traffic freshness and offline requirements? | They influence partitioning and download policy. |
Requirements and scope
The core deliverable is: Serve map tiles, place search and traffic-aware routes while separating geographic data versions from rapidly changing traffic. The first design implements the APIs below and the state constraints in the data model. Agree the latency, freshness, retention and failure policy before adding infrastructure. Every successful acknowledgment must have an explicit meaning: accepted intent, committed state or completed external work. These are separate milestones.
Capacity and bottleneck reasoning
Assume 100 million users with 20 tile loads/day: two billion tile requests/day, about 23,148/s average. At 50 KB/tile this is 100 TB/day before caching. One million route requests/day with a 20x peak is about 231/s peak; route search cost depends on graph size and algorithm.
Keep average and peak demand separate. Add replication, indexes, retries and safety headroom to raw arithmetic before selecting capacity. Load-test the busiest ownership key and recovery traffic as well as uniform happy-path throughput.
APIs and data model
- GET /tiles/{mapVersion}/{z}/{x}/{y} -> cacheable tile
- GET /routes?origin=...&destination=...&mode=drive -> route,graphVersion,trafficAge
- GET /places?q=...&near=... -> authorized public place candidates
road_graph(version,node_id,edge_id,geometry,allowed_modes,base_cost)
traffic(edge_id,observed_at,travel_time,confidence)
tile(z,x,y,map_version,style_version); place(id,location,tokens,version)Authorize resource ownership at the API boundary; do not trust IDs or state supplied by a client. Bind retry identity to the caller and payload for mutating operations. Reject an incompatible replay instead of returning an unrelated stored result.
Component relationships
Read the diagram
Follow the labeled relationship panels; they are separate directed paths, not one global timeline.
Step-by-step design
1. Establish the authority
Ingest road edits and validate connected topology, one-way rules and turn restrictions before publishing a graph version. Generate versioned vector/raster tiles and distribute them through caches independently from route workers.
2. Make retries and concurrent work safe
Map-match GPS traces before estimating edge speeds, remove outliers and aggregate with privacy protection. Combine base edge costs with freshness/confidence-weighted traffic; stale traffic should degrade to historical or free-flow estimates explicitly.
3. Scale and recover the critical path
Snap route endpoints to eligible edges and compute a legal path using graph search plus preprocessing/hierarchical shortcuts as appropriate. Stitch cross-region paths through boundary nodes and revalidate restrictions; proximity search alone cannot find a navigable route.
Worked request and concurrency example
A rider requests a driving route across two map partitions. Both workers pin graph version G12, so a road exists consistently on either side of the boundary. Fresh traffic makes one highway edge slower and another legal route wins. If traffic updates stop for ten minutes, the route response marks traffic age and uses historical speeds. Cached tiles may remain on G11 briefly without being treated as the source of navigation restrictions.
Failure and recovery walkthrough
A road closure must invalidate or penalize the relevant graph edge promptly; deleting a tile label does not stop routing over that road. A bad graph publish is rolled back with a version pointer while urgent closure overlays remain enforced.
Read the diagram
This numbered trace follows one scenario; explain the durable evidence at each transition.
Decisions and alternatives
| Decision | Trade-off |
|---|---|
| Alternative 1 | Preprocessed routing accelerates long trips but dynamic traffic and turn costs complicate shortcuts. Less preprocessing simplifies updates at greater request-time CPU cost. |
| Alternative 2 | Tile caches tolerate longer staleness than safety-relevant restrictions. Give the paths separate refresh and rollback contracts. |
Operational contract
Track route latency, no-route rate, closure propagation, map-version skew and traffic age. Test disconnected roads, cross-partition routes, stale GPS and graph rollback. Limit retention and resolution of raw location traces.
Choose alert thresholds from the agreed user-facing objective. Assign an owner for stuck work and a replay/repair procedure that preserves the original business identity. Bound queue depth, concurrency and recovery throughput so an outage does not produce an uncontrolled catch-up burst.
Foundation, senior and staff depth
- Foundation: explain the user action, model, first complete request and the correctness constraint without relying on a list of technologies.
- Senior: defend this lesson's partition/coordination boundary, capacity estimate and failure recovery; explain the cost of the rejected alternative.
- Staff: identify failure domains and operational ownership, stage a rollout with measured guardrails, and state when rollback stops being safe.
Practice before revealing the answer
Spend 45 minutes: 5 clarifying scope, 7 on capacity/APIs/state, 12 on the first architecture, 15 on the concurrency and failure examples, and 6 on trade-offs and operations. Draw your own design before comparing it with this chapter.
Question: Why does a geohash index not solve navigation?
Show answer and explanation
Answer: It finds nearby candidates. Navigation requires graph connectivity, direction, mode/turn restrictions and path cost; two adjacent points may be separated by a river or inaccessible road.
Verification and rollout
Reproduce the worked example using two concurrent actors or a repeated request where applicable. Inject the stated failure between the durable transition and its acknowledgment; verify the resulting state and user-visible outcome. For read/ML paths, test missing or stale dependencies and verify the documented fallback still enforces permissions. Use a small canary, compare correctness and user-facing latency with the baseline, and roll back when those guardrails regress. Do not use an average throughput number as evidence that a tail-latency target is met.
Primary technical reference
Official documentation for the mechanism used in this exercise. This lesson is an original interview design, not a description of undisclosed company internals.
Related study
Before this design, review these mechanisms and identify which owns the critical state transition:
Use the Interview Playbook to adapt the depth and timing, then return to the question breakdown overview.