Technologies referenced in this case study: Redis · PostgreSQL · Kafka · Flink · Cassandra · Elasticsearch

Related case studies: Proximity Matching · Logistics & Delivery · CDN & Edge Caching · Stream Processing · Search Indexing

Related patterns: Scaling Reads · Data Pipelines · Degraded Mode · Database Indexing · Sharding

How to Use This Case Study#

Organized for interview use first, reference second.

Without live traffic in the routing cost function:
t=0:      Multi-car crash closes 3 of 4 lanes on a highway at 5:10pm
t=+2min:  Road speed on the segment drops from 100 km/h to 12 km/h
t=+2min:  Router still uses the historical Tuesday-5pm profile: 65 km/h
t=+10min: 40,000 drivers routed onto the jammed segment; ETAs off by 25+ min
t=+30min: Social media: "Maps drove me straight into the jam." Trust damage.

With a streaming traffic pipeline feeding routing weights:
t=0:      Same crash
t=+45s:   Probes from ~60 phones on the segment map-matched; speed estimate 15 km/h
t=+90s:   Segment weight published to routing (1-min window, min 5 probes)
t=+2min:  New queries avoid the segment; in-progress navigations get a reroute offer
t=+5min:  ETA error back within ±10%; the jam is shorter because we stopped feeding it

Executive Summary

If you only read one section, read this. Everything else in the case study elaborates the contrast below.

What This Interview Actually Tests#

Google Maps is not a geohash question. Everyone can draw a grid.

It is a freshness-vs-precomputation question across four subsystems that tests:

• Whether you decompose the product into tiles, search, routing, and traffic — and pick one to go deep on
• Whether you choose a spatial index for a specific query pattern rather than by reputation
• Whether you understand that the fastest routing algorithms depend on precomputation that live traffic invalidates
• Whether you own the data pipeline: who is paged when traffic data goes stale and ETAs silently drift

The key insight: The map changes on three clocks — the road network changes weekly, traffic changes every minute, and a user's position changes every second. Every component of the design is defined by which clock it runs on. Precompute what changes weekly; stream what changes per minute; never put per-second data on a path that expects weekly data.

The L5 vs L6 Contrast — Start Here#

The Staff Positions#

The Three Intents#

🎯 Staff Move: "I'll design routing plus live ETA, because it's where the freshness-versus-precomputation tradeoff is sharpest and where a silent failure hurts millions of drivers. I'll cover tiles as a CDN problem in two minutes and treat place search as a spatial index I'll reuse for map matching."

The Five Fault Lines#

In the Wild: Real Production Systems#

Why this section belongs here: These are the public anchors interviewers recognize.

Google — S2 Geometry and Crowd-Sourced Traffic#

Google open-sourced the S2 geometry library, which maps the sphere onto six cube faces and orders cells along a Hilbert curve across 31 levels, giving 64-bit cell IDs with strong locality. MongoDB's 2dsphere index is built on S2, which is a useful proof that it works as a database index. Google has publicly described using aggregated, anonymized location data from phones to estimate live traffic, and in 2020 Google and DeepMind published work applying graph neural networks to ETA prediction, reporting meaningful accuracy improvements (up to ~50% fewer inaccurate ETAs in some cities).

Staff insight: Google's traffic is a data-pipeline product, not a routing feature. Mentioning that ETA is "historical profile + live signal + learned correction" shows you know ETA is a prediction problem, not a shortest-path output.

Uber — H3 Hexagonal Grid#

Uber open-sourced H3 in 2018: a hierarchical hexagonal grid with 16 resolutions used for surge pricing, supply/demand forecasting, and aggregation. Hexagons have one kind of neighbor (all 6 equidistant), which makes smoothing and gradient calculations cleaner than square grids with edge-vs-corner neighbors.

Staff insight: Different cell systems for different jobs is a legitimate answer. H3 for aggregation and ML features; S2 or R-trees for exact containment and storage.

OSRM / Academic Routing — Contraction Hierarchies and Multi-Level Partitioning#

The open-source OSRM engine (on OpenStreetMap data) popularized Contraction Hierarchies — shortest paths on continental graphs in well under a millisecond — and later added a multi-level Dijkstra (MLD) mode inspired by Customizable Route Planning (Microsoft Research, Delling et al.), trading some query speed for the ability to update weights quickly.

Staff insight: The existence of two modes in one engine is the fault line in miniature: CH when weights are static, partition-based when traffic matters.

What Interviewers Probe#

System Architecture Overview#

Reading the diagram: Three clocks. Weekly: map data builds the road graph artifact (partitioned and preprocessed for hours), tiles, and the search index — rolled out like a code release. Per-minute: GPS probes stream through map matching and windowed aggregation into live segment weights, which the routing service folds into its metric every 1–2 minutes. Per-request: routing runs on the in-memory graph with current weights; the ETA model corrects the raw path time. Observability watches the age of traffic data, not just errors.

Quick-Reference: The 30-Second Cheat Sheet#

Key Numbers Worth Memorizing#

Interview Walkthrough

The most common mistake: Candidates try to design tiles, search, routing, traffic, Street View and offline maps in 45 minutes and go 2 inches deep on each. The phases below scope in 3 minutes, sketch in 10, and spend 25+ on the subsystem that decides your level.

Phase 1: Requirements & Framing (2–3 minutes)#

State the functional scope in one breath:

"Users see a map, search for places, get driving directions with an ETA, and get rerouted when traffic changes."

Then decompose and commit:

"That's four subsystems on three clocks. Tiles and search change when map data changes — weekly. Traffic changes every minute. A navigating user's position changes every second. I'll cover tiles quickly as a CDN problem and go deep on routing with live traffic and ETA, because that's where precomputation and freshness collide. Does that match what you want?"

Commit to non-functional targets:

"Route queries p99 under 200ms end to end, with the graph search itself under 10ms. Traffic reflected in routing within 2–3 minutes of a change. ETA within ±10% for 90% of trips. Global scale: ~1B monthly users, peak ~100K route requests/sec, ~1M GPS probes/sec from navigating devices. Map data changes must never route drivers through closed roads — that's the one correctness bar I'll treat as hard."

🎯 Staff Move: Naming the three clocks (weekly, per-minute, per-second) gives the interviewer a mental model for the rest of your answer. Every later decision — what's precomputed, what's streamed, what's cached — follows from which clock the data runs on.

Phase 2: Core Entities & API (1–2 minutes)#

• Node: road intersection or shape point — node_id, lat, lng, s2_cell
• Segment (edge): directed road piece — segment_id, from, to, length_m, road_class, speed_limit, restrictions, geometry
• Turn restriction: (from_segment, via_node, to_segment, allowed)
• SegmentSpeed: segment_id, window_start, speed_kmh, probe_count, age_s, source(live|historical)
• Place: place_id, name, category, lat, lng, s2_cell_l16, hours, rating
• MapRelease: release_id, graph_artifact_uri, tile_version, created_at

Routing API:

GET /v1/route?origin=lat,lng&dest=lat,lng&depart_at=now&mode=drive&alternatives=2
→ { routes: [{ polyline, distance_m, eta_s, eta_confidence, traffic_age_s, legs[] }], map_release }

Navigation session (streaming):

→ PROBE    { session_id, lat, lng, speed, heading, ts, accuracy_m }   every 1–5s
← REROUTE  { route, reason: 'faster_route' | 'off_route' | 'closure' }

Search:

GET /v1/places?q=coffee&near=lat,lng&radius_m=1500&open_now=true

🎯 Staff Move: "The route response carries traffic_age_s and the map_release it was computed on. When a user reports a bad route, support can reproduce it exactly. That's not a UX detail — it's how we debug the silent failures."

Phase 3: High-Level Architecture (≤5 minutes)#

Walk it in 60 seconds:

1. Tiles: vector tiles pre-built per map release, stored in object storage, served by CDN. Versioned URLs, so a release is a cache-key change, not a purge.
2. Map data → graph: weekly build partitions the road graph into nested cells and precomputes boundary shortcuts — hours of compute, output is an immutable artifact loaded by routing servers.
3. Traffic: navigating phones send probes to Kafka; Flink snaps them to road segments (map matching), aggregates per segment per minute, and publishes speeds with an age.
4. Routing: servers hold the graph for their region in memory; every 1–2 minutes they re-customize the metric using live weights; queries run bidirectional search across the partition overlay in ~1–10ms.
5. ETA: raw path time is corrected by a model trained on actual trip durations.

🎯 Staff Move: "That's the skeleton. The decisions that matter are: which routing precomputation survives live traffic, how we turn noisy GPS into trustworthy segment speeds, and how we keep a bad map release from routing a million drivers wrong. Which one first?"

Phase 4: Transition to Depth (1 minute)#

"I'd start with routing precomputation versus freshness, because it determines the fleet size and how fast traffic shows up in routes. Then the traffic pipeline — map matching and privacy thresholds. Then failure: stale traffic and bad map data."

If the interviewer wants spatial indexing specifically: "Happy to go there — I'd use S2 cell IDs for place search and map-matching candidate lookup. Let me show you how a radius query becomes a set of cell-ID ranges."

Phase 5: Deep Dives (25–30 minutes)#

Deep dive A: Routing — precompute vs freshness (8–10 min)

"A continental road graph has 10⁷–10⁸ nodes. Plain Dijkstra settles millions of nodes for a long route — seconds of CPU. At 100K QPS, that's hundreds of thousands of cores. So precomputation is non-negotiable. The question is what it costs us when weights change."

"Contraction Hierarchies: order nodes by importance, contract them, add shortcuts that preserve shortest paths. Queries are sub-millisecond. But every shortcut's weight is a sum of underlying edge weights computed under one metric. Traffic changes thousands of segment weights every minute; CH needs re-preprocessing, which takes minutes to hours for a continent. That's the freshness death."

"Partition-based customizable routing: partition the graph into cells at 2–4 nested levels using a balanced graph partitioner so each cell has few boundary nodes. Preprocessing — done weekly — computes the partition. Customization — done every 1–2 minutes — recomputes, for each cell, shortest distances between its boundary nodes under current weights. Customization is embarrassingly parallel per cell: seconds for a continent. Queries run bidirectional Dijkstra on the overlay: a few milliseconds. I'll take 5ms queries on 2-minute-old traffic over 0.5ms queries on 6-hour-old traffic."

"Who pays: the routing fleet pays ~5–10× more CPU per query than CH; users get fresh routes. For static-weight use cases — say walking directions — I can still use CH."

Deep dive B: Traffic pipeline (7–8 min)

"A GPS fix has 5–20m error in cities, worse in urban canyons. Snapping to the nearest road is wrong at interchanges and frontage roads. I use HMM map matching: candidate segments within ~50m of each fix are hidden states, emission probability decays with distance, transition probability favors routes whose network distance matches the straight-line distance between fixes. Viterbi over a sliding window of ~10 fixes. Candidate lookup uses the spatial index — segments indexed by S2 cell at ~level 16."

"Aggregation: per segment, 1-minute tumbling windows, median speed of matched traversals, require ≥5 distinct devices before publishing — below that, noise dominates and single trips become identifiable. Blend: speed = w·live + (1−w)·historical(segment, day_of_week, 15-min bucket) where w rises with probe count and falls with age. Every value is stored with age_s."

"Privacy: trim the first and last ~200m of each trip so home and work locations never enter the pipeline; rotate device IDs daily; drop raw probes after aggregation (e.g., 24h retention). Legal and privacy sign off on k and retention."

Deep dive C: Map data releases and failure (6–7 min)

"A road graph release is code. A wrong one-way flag on a bridge routes every driver the wrong way. So releases get validation — connectivity checks (no new unreachable islands > N nodes), route-diff tests on a fixed set of 100K origin-destination pairs (flag if >1% change by >20%), then canary: 1% of routing servers in one region, compare ETA error and reroute rates against control for an hour, then roll forward. Rollback is loading the previous artifact — the servers keep two in memory."

"Live closures can't wait for a weekly release, so there's an overlay: closure events (from authorities, user reports, or detected zero-flow segments) set segment weight to infinity in the live metric. That rides the per-minute customization path."

🎯 Staff Move: Every deep dive ends with an owner: "Map data team owns release validation and signs off canaries. Routing team owns the engine and query SLO. Traffic team owns freshness — they're paged on segment age, not on errors."

Phase 6: Wrap-Up (2–3 minutes)#

"Summary: three clocks. Weekly map releases build a partitioned graph artifact, tiles, and a search index, canaried like code. A per-minute streaming pipeline turns probes into segment speeds with ages and privacy thresholds. Per-request routing uses a customizable partitioned graph so traffic shows up in ~2 minutes, and an ETA model corrects the raw path time. Next I'd build: time-dependent routing for long trips so minute-40 uses predicted rather than current traffic; incident detection from sudden speed drops; and an ETA accuracy dashboard by region so we know where we're wrong before users tell us."

Common Timing Mistakes#

1. The Staff Lens#

1.1 Why This Problem Exists in Staff Interviews#

It's the canonical "too big to design" prompt. The first signal is whether the candidate decomposes and scopes, or drowns. The second is whether they understand that precomputation — the only way to answer routing at scale — creates a freshness debt, and that the most dangerous failure is a quietly wrong answer rather than an error. The third is organizational: map data, traffic, routing, and tiles are separate teams with separate clocks, and the contracts between them are where incidents happen.

1.2 The L5 vs L6 Contrast — Visual#

1.3 The Staff Question That Cuts Through Everything#

"How old is the data this answer was computed from, and who finds out when it's too old?"

It forces the three-clock model, the age-tagging of every traffic value, the fallback to historical profiles, the release versioning on routes, and the freshness metric that pages the traffic team. A candidate who asks it is designing for wrongness, not just outages.

2. Problem Framing & Intent#

2.1 The Three Intents — Explained#

Map display. A pure read-scaling problem. Tiles are immutable per release, so they cache perfectly at the CDN with versioned URLs. The interesting decisions are vector vs raster, zoom levels to pre-render, and how to avoid a cache stampede when a release flips versions. Victims: users on slow devices (vector rendering costs client CPU) and the CDN bill.

Place search. A spatial index plus text relevance. The spatial part — "within 1.5km" — is solved by covering the circle with S2 cells and scanning cell-ID ranges; the hard part is ranking (distance vs rating vs open-now vs ads) and freshness of business data. Victims: dense cells (Manhattan) where a coarse cell holds 50K places, and businesses whose hours are stale.

Routing + live ETA (default). A graph problem at massive scale fused with a streaming data problem. Victims of the design choices: the routing fleet's CPU (customizable routing costs more per query than CH), drivers when traffic is stale, and privacy if probe aggregation is careless.

2.2 When NOT to Use Heavy Geospatial Infrastructure#

🎯 Staff Move: "If we're a delivery company with 5M routes a day, we buy routing from a provider until the bill passes roughly the cost of a 6–8 person routing team. Building a routing engine is a multi-year commitment, not a sprint."

2.3 What the Interviewer Leaves Underspecified#

2.4 Precise Terminology#

3. The Five Fault Lines#

3.1 Fault Line 1: Precompute vs Freshness (Routing)#

The Staff default: partitioned graph with customizable metric for driving; CH for modes with static weights (walking, cycling).

When to deviate: a small single-city deployment can run A* with live weights — 50K-node graph, queries in ~10ms. A logistics optimizer running millions of many-to-many matrix queries overnight may prefer CH on historical weights.

3.2 Fault Line 2: Spatial Index Choice#

The Staff default: S2 cell IDs as the storage key for places and road segments (range scans on a sorted key), H3 for traffic/analytics aggregation, R-tree inside the map-data authoring pipeline where polygons live.

When to deviate: if the only store is Redis, geohash (Redis GEO commands use 52-bit geohash under the hood) is pragmatic. Name the neighbor-scan cost.

🎯 Staff Move: "A 1.5km radius query becomes an S2 covering of ~8–20 cells at mixed levels, which becomes ~8–20 contiguous key ranges. Hilbert ordering means most ranges are long and contiguous, so it's a handful of range scans per shard, not a scatter of point lookups."

3.3 Fault Line 3: Traffic Freshness vs Accuracy vs Privacy#

The Staff default: 1-minute windows with k ≥ 5 distinct devices, blended with historical profiles weighted by probe count. Minor roads rarely hit k — they use historical profiles, which is fine because they rarely drive route choice.

When to deviate: incident detection can use a separate, faster signal (e.g., sudden multi-device stop on a highway) that sets a closure/slowdown flag without publishing individual speeds.

3.4 Fault Line 4: Pre-rendered vs On-demand Tiles#

The Staff default: vector tiles pre-rendered through ~z14, overzoom on client, versioned URLs per release, pre-warm the top ~5% of tiles (which serve the large majority of requests) in the CDN before flipping the version.

3.5 Fault Line 5: Global Graph vs Regional Partitions#

The Staff default: regional graphs sized to fit comfortably in memory, overlapping at borders, plus a coarse highways-only global overlay for inter-region routes (rare — most driving routes are <100km).

4. Failure Modes & Operational Reality#

4.1 Silent Staleness — The Traffic Pipeline Stalls#

t=0:       Flink job checkpoint fails; aggregator stuck, not crashed
t=+1min:   Live weights stop updating; routing keeps using last values
t=+20min:  Evening rush builds; routes still see 3pm speeds
t=+40min:  ETA error p50 rises from 7% to 22%; no 5xx, no alerts on errors
t=+55min:  Social media reports; on-call notices from ETA dashboard

Detection: traffic_segment_age_p95 > 5 min pages; traffic_publish_lag_seconds; eta_abs_error_pct by region (computed from completed trips, ~15–60 min delay — a lagging indicator).

Mitigation: Routing treats weights older than 10 min as absent and falls back to historical profiles per segment — degraded but not wrong-by-hours. Restart the aggregator from the last good checkpoint; skip backlog older than 5 min (stale traffic has no value).

Prevention: Age-based fallback built into the metric; a heartbeat segment set (major highways) whose age is checked every 30s. Owner: traffic pipeline team.

4.2 Bad Map Release — The Wrong-Way Bridge#

t=0:       Release R-2291 flips a one-way flag on a major bridge
t=+15min:  Canary skipped (holiday freeze exception); rollout to 100%
t=+30min:  Routes send drivers against traffic direction onto bridge approach
t=+45min:  Reroute rate on region spikes 6×; driver reports flood in
t=+50min:  Rollback to R-2290 (servers keep previous artifact in memory)

Detection: reroute_rate by region; off_route_rate; route-diff test failures; user "wrong route" reports per segment.

Mitigation: Instant rollback to the in-memory previous artifact. Live-closure overlay blocks the segment within 2 minutes while the fix ships.

Prevention: Route-diff tests on 100K canonical OD pairs; connectivity and direction-flip audits on high-traffic segments; canary with metric comparison is non-skippable. Owner: map data team (release), routing team (rollback mechanism).

4.3 Hot Cell — Search Meltdown at an Event#

Scenario: A stadium concert ends; 60,000 people search "parking" and "restaurants" within the same few S2 cells.

Detection: search_qps_by_cell top-K; search_shard_cpu; p99 latency on the shard holding that cell range.

Mitigation: Cache search results per (cell, category, rounded-radius) for 60s; replicate hot cell ranges to more replicas; shard by S2 cell at a level where dense areas split into more shards.

Prevention: Shard boundaries by load, not by equal cell counts — split Manhattan finer than Montana. Owner: search team.

4.4 Probe Flood — A Bad Client Release#

Scenario: App v9.3 sends probes every 100ms instead of every 1s. Probe volume 10×.

t=0:      v9.3 rolls out to 20% of Android
t=+2hr:   Kafka ingest 3× normal; Flink map-matching lag rising
t=+3hr:   traffic_segment_age_p95 crosses 5 min → page

Detection: probe_ingest_rate per app version; mapmatch_consumer_lag.

Mitigation: Server-side sampling per device (keep 1 probe/sec); config-pushed client rate limit; per-version quotas at the gateway. See Rate Limiting.

Prevention: Probe rate is a server-controlled config, not a client constant. Owner: traffic team + mobile team.

4.5 Tile Release Stampede#

Scenario: New tile version flips at 00:00 UTC; CDN has 0% hit rate on new URLs; origin sees 20× load.

Mitigation/Prevention: Pre-warm popular tiles before flip; flip per-region gradually; request coalescing at CDN shield tier. See CDN & Edge Caching. Owner: tiles team.

4.6 Operational Reality Matrix#

5. Evaluation Rubric#

5.1 Level-Based Signals#

5.2 Strong Hire Signals#

5.3 Lean No-Hire Signals#

5.4 Common False Positives#

• Knowing geohash bit interleaving ≠ spatial index judgment. Ask when they'd not use it.
• Reciting CH ≠ understanding traffic. Ask what happens when 5,000 segment weights change.
• An ML ETA model ≠ an ETA system. Ask how they detect it's wrong in one city.
• "We use PostGIS" ≠ a design. PostGIS is great for the authoring pipeline and weak at 100K QPS serving.

6. Interview Flow & Pivots#

6.1 Typical 45-Minute Shape#

6.2 How Interviewers Pivot — And What They're Testing#

6.3 What to Deliberately Skip#

• Map rendering styles and label placement
• Street View, satellite imagery pipelines
• Transit schedule ingestion (GTFS) unless asked
• Exact HMM math — name emission/transition and move on

6.4 Follow-Up Questions to Expect#

1. "How do you answer 'find within 2km' if the user is on a geohash cell boundary?"
2. "Why not just use A* with a better heuristic?"
3. "How quickly does a new traffic jam affect routes?"
4. "How do you know GPS pings are on the highway and not the parallel street?"
5. "How do you roll out a new road network without breaking routes?"
6. "How do you prevent the traffic data from revealing where individuals live?"
7. "What happens to ETAs if the traffic pipeline dies?"

7. Active Drills#

Drill 1: The Opening#

Prompt: "Design Google Maps."

Drill 2: Radius Search with a Spatial Index#

Prompt: "Find all coffee shops within 1km of the user. Walk me through the index."

Drill 3: Why Not A*?#

Prompt: "A* with a straight-line heuristic is optimal. Why do you need anything more?"

Drill 4: Traffic Changes Every Minute#

Prompt: "You chose Contraction Hierarchies. A major highway jams. What happens?"

Drill 5: Map Matching#

Prompt: "A phone reports a point 15m from a highway and 10m from the frontage road next to it. Which road is the car on?"

Drill 6: Hot Region — Stadium Letting Out#

Prompt: "70,000 people leave a stadium. They all request routes and search simultaneously."

Drill 7: Build vs Buy#

Prompt: "We're a food-delivery company. Build routing and ETA or buy?"

Drill 8: Shipping a Map Release Safely#

Prompt: "A new map release is ready. How do you ship it?"

Drill 9: Cost#

Prompt: "The routing fleet costs $4M/month. Cut it 30%."

Drill 10: Multi-Region and Cross-Border Routes#

Prompt: "Routes cross from France to Germany. Your graphs are regional."

8. Deep Dive Scenarios#

Deep Dive 1: Rush-Hour ETA Collapse#

Context: It's 5:30pm Friday. ETA error in one metro jumped from 8% to 25% over 40 minutes. No service is erroring. On-call escalates to you.

Questions to Surface First:

• Is traffic data fresh in that metro? (traffic_segment_age_p95)
• Is it one metro or many? One region's aggregator or the whole pipeline?
• Did a map release or ETA model deploy today?
• Is there a real-world event (storm, closure) the system hasn't absorbed?

Typical L5 Approach: Look at routing service latency and errors; find nothing; check the ETA model for recent changes. Competent, but it starts where errors would be, not where staleness is.

Staff Approach: Check data age first. Found: the metro's Flink partition is stuck on a poison message; segment ages are 40 minutes. Routing kept using 4:50pm speeds. Immediate: force historical fallback for the metro (ages > 10 min should have triggered it — why didn't it?), skip the poison message to a DLQ, restart. Then fix the fallback threshold that was misconfigured at 60 minutes.

Principal Approach: Freshness is a product SLO, not a pipeline detail. Publish "traffic freshness" per region as an SLO (p95 age < 3 min, 99.5% of minutes) with an error budget; put ETA accuracy by region in the weekly business review. Build a synthetic probe canary per metro — fake trips on known roads whose speeds must appear within 2 minutes — so staleness is detected in minutes, not by users.

Metrics to Watch: traffic_segment_age_p95{region}, flink_partition_lag, eta_abs_error_pct{region}, historical_fallback_ratio.

Organizational Follow-up: Safety thresholds (fallback age) require two-person review. Traffic team on-call gets region freshness dashboards.

Ownership Question: Who's paged when ETAs are wrong but nothing errors? The traffic team, on freshness — because freshness is the leading indicator and ETA error lags by 30+ minutes.

Key Takeaway: "In Maps, the dangerous outage is the one with zero errors. Page on data age."

What clears the Staff bar:

• Checks data freshness before service health
• Fixes the fallback that should have contained the blast
• Converts a threshold misconfig into a review process

Deep Dive 2: The Phantom Closure#

Context: For 3 hours, routing avoided a major bridge that was open. Traffic on alternative routes doubled. Users complained about 20-minute detours.

Questions to Surface First:

• Where did the closure come from — authority feed, user reports, or auto-detection?
• How long do closures live without confirmation?
• Could live probes on the bridge have contradicted the closure?

Typical L5 Approach: Remove the bad closure; add validation on the closure feed.

Staff Approach: Closures are the one live input that can set weight to infinity — they need the strongest guardrails. Found: auto-detection flagged zero flow during a 5-minute probe gap caused by a cellular outage, and closures had no expiry. Fix: auto-detected closures require ≥2 independent signals and expire in 30 minutes unless reconfirmed; any probe traversal of a "closed" segment auto-lifts the closure. Authority-fed closures keep their stated duration.

Principal Approach: Define a trust model for all live map inputs — authority feeds, user reports, auto-detection — each with confidence, expiry, and a contradiction rule, owned by one team. Report "false closure minutes" as a quality metric next to ETA error.

Metrics to Watch: active_closures{source}, closure_contradicted_total, closure_age_minutes, detour rate.

Organizational Follow-up: Closure sources catalogued with owners; high-impact closures on major segments page a human reviewer.

Ownership Question: Who can close a bridge in our graph? Only sources with an owner and an expiry — and a high-traffic closure pages the map-ops reviewer.

Key Takeaway: "Infinity is the most dangerous weight. Anything that sets it needs an expiry and a contradiction check."

What clears the Staff bar:

• Treats closures as a high-risk input class
• Uses live probes as contradiction evidence
• Expiry by default

Deep Dive 3: Onboarding a Ride-Hailing Partner#

Context: A large ride-hailing company wants our ETA and routing API: 20K QPS peak, a 99.95% availability SLA, and ETA accuracy guarantees per city.

Questions to Surface First:

• Is their traffic shape (airport pickups, driver repositioning) different from ours?
• Do they need route polylines or only ETAs (matrix queries are much more expensive)?
• What does "accuracy guarantee" mean contractually, and in which cities are we weak?
• Will they send us probe data? Under what terms?

Typical L5 Approach: Provision 20K QPS more routing capacity and give them an API key.

Staff Approach: Clarify query shape: ride-hailing uses many-to-many ETA matrices (10 drivers × 1 rider = 10 routes per request), so 20K QPS may mean 200K route computations/sec — 2× our consumer peak. Use a matrix-optimized path (one-to-many search on the overlay). Isolate their traffic on dedicated capacity with its own quota so their surge can't degrade consumer Maps. Accuracy SLA only in cities where our measured error is already within target.

Principal Approach: This is the moment routing becomes an external product. It needs a product owner, pricing, a separate SLA tier, and legal terms on data exchange. Decide deliberately whether we want to be a routing vendor — it changes the roadmap.

Metrics to Watch: partner_route_qps, partner_eta_error_pct{city}, partner_quota_rejections, consumer latency during partner peaks.

Organizational Follow-up: Routing API product owner; partner on-call escalation path.

Ownership Question: Who decides which cities get an accuracy SLA? The routing product owner, using the ETA team's measured error by city — never sales alone.

Key Takeaway: "A partner's '20K QPS' is a matrix. Size the computation, not the request."

What clears the Staff bar:

• Uncovers matrix amplification
• Isolates partner capacity
• Refuses SLAs where data says we'd miss

Deep Dive 4: Post-Mortem — Privacy Audit Finding#

Context: An external researcher shows they can reconstruct individual commutes from our public traffic API on rural roads at 3am.

Questions to Surface First:

• What's the minimum probe count per published segment-window, and is it enforced everywhere?
• Are trip ends trimmed?
• What granularity does the public API expose — segment-level per minute?

Typical L5 Approach: Raise k from 3 to 5 for public output.

Staff Approach: Found: k was enforced for internal routing weights but the public API served per-segment speeds without the threshold — and on rural roads at night, k=1 speeds leaked single trips. Fix: public outputs only publish segments meeting k ≥ 10 over a 15-minute window, coarsened to H3 res 8 in low-density areas; add noise per published value; audit job fails deploys if any published row violates thresholds.

Principal Approach: Privacy thresholds are a company standard, not per-API choices. Write the location data standard (k, retention, trimming, coarsening), put it in a shared library all location outputs must use, and give privacy engineering veto on new location-derived outputs.

Metrics to Watch: published_rows_below_k_total (must be 0), raw_probe_retention_hours, trip-end trim ratio.

Organizational Follow-up: Privacy review required for any new location-derived API.

Ownership Question: Who owns k? Privacy engineering sets it; the traffic team implements it through the shared library.

Key Takeaway: "A privacy threshold enforced in one code path is a threshold enforced in zero code paths."

What clears the Staff bar:

• Finds the enforcement gap rather than tweaking k
• Centralizes enforcement
• Deploy-time audit

Deep Dive 5: Expanding to a New Country#

Context: Launch Maps with navigation in a large country with sparse official map data and few current users (so few probes).

Questions to Surface First:

• Where does map data come from — OSM, licensed, imagery-derived, local partners?
• Without probes, what powers traffic and ETA at launch?
• Any residency or mapping regulations (some countries restrict map data export or precision)?

Typical L5 Approach: Import map data, deploy routing, launch.

Staff Approach: Launch with honest capability: routing on licensed + OSM data, ETA from road class and speed-limit defaults calibrated with any available trip data, no live traffic claims until probe density reaches k in major cities. Stage by city. Measure ETA error from early trips and publish internal accuracy by city before marketing claims "live traffic."

Principal Approach: Country launch is a repeatable playbook: data sourcing, legal review (map regulations), cold-start ETA, probe density thresholds for enabling features, and a regional ops team. Price the data licensing against expected users before approving.

Metrics to Watch: probe_density_per_segment{city}, eta_abs_error_pct{city}, map-edit report rate.

Organizational Follow-up: Regional map ops team; local partner for corrections.

Ownership Question: Who decides when a city gets "live traffic" in the UI? The traffic team, gated on measured probe density and error — not the launch calendar.

Key Takeaway: "Features gate on data density. Launch dates don't create probes."

What clears the Staff bar:

• Cold-start plan for ETA without traffic
• Feature flags tied to data thresholds
• Legal/regulatory as a first-class launch input

9. Level Expectations Summary#

After studying this case study, you should be able to:

• Decompose "Design Google Maps" into tiles, search, routing, and traffic, and scope to one in under a minute
• Explain the three clocks (weekly, per-minute, per-second) and place every component on one
• Choose between geohash, S2, H3, quadtree, and R-tree for a stated query, and walk a radius query through an S2 covering
• Explain why CH is fast and stale, and how partition-based customizable routing gets traffic into routes in ~2 minutes
• Design a traffic pipeline: map matching, windows, k-anonymity, historical blend, age tagging
• Treat map data releases like code: validation, canary, rollback, live closure overlay
• Detect silent staleness and wrong closures with named metrics and owners
• Frame geo as a platform with SLAs and privacy standards (L7)

The Bar for This Question#

Mid-level (L4): Stores places with lat/lng and a geohash, runs Dijkstra/A* for directions, serves tiles from a CDN. Works for a city.

Senior (L5): Covers all four subsystems competently: geohash with neighbor scan, CH or A*, averaged GPS speeds, vector tiles. Gaps: no scoping, no freshness model, no answer for traffic invalidating precomputation, no silent-failure detection.

Staff+ (L6): Scopes and commits. Uses the three-clock model. Chooses a customizable partitioned routing engine and explains the precompute/freshness trade in numbers. Designs the traffic pipeline with map matching, privacy thresholds, and age-based fallback. Treats map data as code. Names owners for data, routing, traffic, and tiles. The interviewer should learn something from the answer.

10. Staff Insiders: Controversial Opinions#

10.1 "Geohash Is a Legacy Choice"#

The Staff position: Use geohash only when the store forces string prefixes. Otherwise S2 for storage, H3 for aggregation.

Why this matters in interviews: "Geohash" is the default L5 answer; knowing its failure modes is the upgrade.

10.2 "The Fastest Routing Algorithm Is the Wrong One"#

The Staff position: Pay 5–10× query CPU for a customizable metric. Freshness is worth more than microseconds.

Why this matters in interviews: Shows you optimize for the user outcome, not the benchmark.

10.3 "ETA Is a Prediction Product, Not a Graph Output"#

The Staff position: ETA = time-dependent path cost + learned correction, measured against actual trip durations by region.

Why this matters in interviews: Moves ETA from "divide distance by speed" to a measured, owned model.

10.4 "Map Data Bugs Cause More Incidents Than Code Bugs"#

The Staff position: Map data changes are deploys. They get validation, canaries, and rollbacks — and a dedicated owner who is paged.

Why this matters in interviews: Demonstrates operational scars, not textbook knowledge.

10.5 "Privacy Thresholds Are Architecture"#

The Staff position: k-anonymity, trip-end trimming, and raw-probe retention change window sizes, coverage, and freshness. Decide them in the design, with privacy engineering in the room.

Why this matters in interviews: Candidates who treat privacy as a checklist item miss that it changes the data pipeline's shape.

11. The Principal Lens (L7)#

Why L7 Sees This Problem Differently#

At Staff, Maps is a product with four subsystems. At Principal, location is a company-wide asset: the road graph, traffic feed, place database, and ETA model are consumed by consumer Maps, delivery, ride-hailing partnerships, ads (store visits), and local search. Each consumer wants different freshness, accuracy, and privacy guarantees. The L7 job is to decide which of these are platforms with SLAs, which stay product-specific, and how privacy standards are enforced uniformly — because one leaky API is a company-level incident.

The Org-Level Fault Line#

Geo platform with SLAs vs per-product geo stacks.

The L7 default: central platform for the road graph, traffic, and privacy-enforced aggregation; product teams own their ranking, UX, and domain-specific ETA corrections (delivery prep time, pickup walking time).

Cost Model#

Assumptions: route query ~5ms CPU on customizable routing; customization cluster runs every 2 min; probes ~200 bytes; tiles CDN-served at 95%+ hit rate; cloud list prices, rough.

Where money goes: map data acquisition and quality (people) usually exceeds infrastructure. The largest infra line is routing CPU, driven by reroute polling frequency — a product knob.

The 3-Year Evolution Path#

One-Way Doors vs Two-Way Doors#

The Standard I'd Write#

RFC: Location Data & Geo Services Standard (v1)

Scope: Any service that stores, aggregates, or publishes data derived from user location.

MUST:

• Use S2 cell IDs (storage) or H3 (aggregation) via the shared geo library — no bespoke grids.
• Aggregate location-derived outputs through the privacy library: k ≥ 5 internal, k ≥ 10 external; trip ends trimmed ≥200m.
• Retain raw probes ≤24h unless an approved exception exists.
• Tag every derived value with source and age; consumers MUST handle stale values.
• Ship map data changes through validated, canaried releases with instant rollback.

SHOULD:

• Consume routing and ETA via platform APIs rather than embedding engines.
• Report ETA accuracy by region to the platform dashboard.

Exceptions: Privacy engineering + geo platform council; time-bounded.

Success metrics: 0 published rows below k; traffic freshness p95 < 3 min in 99.5% of minutes; ETA ±10% for 90% of trips in top-100 metros; one road graph company-wide.

What I'd Tell the VP#

"Location data powers five of our products, but today three teams maintain their own maps and routing, which costs us about 25 engineers of duplicated effort and gives customers different arrival times in different apps. I'm proposing one geo platform that owns the road map, live traffic, and arrival-time predictions, with privacy rules built in so no team can accidentally expose where people live. It takes about a year and pays back in the second year through consolidation. The biggest risk we're addressing is silent wrongness — routes based on stale data — which we'll now measure and alert on like an outage."

Principal Interview Signals#

Staff answers that L7 interviewers find insufficient:

• "The traffic team owns freshness" — true for Maps, but ignores the three other consumers who each re-derive traffic.
• "We use k ≥ 5" — a number, not an enforced company standard.
• "We'll canary map releases" — for one product; not a release governance model across many data sources.

🧭 Principal Move: "Before we optimize our routing engine, let's decide who else needs it. If delivery and ads will consume ETAs within a year, the right unit of design is a geo platform with a privacy boundary, and consumer Maps is its first customer."

Appendices

Appendix A: Spatial Indexing in Depth#

A.1 Geohash#

encode(lat, lng, precision):
  bits = interleave(bisect(lng, -180..180), bisect(lat, -90..90))   # lng first
  return base32(bits)[0:precision]       # 5 bits per char

radius_query(lat, lng, r):
  p = precision_for(r)                   # cell ≥ r in both dims
  cells = [cell(lat,lng,p)] + neighbors8(cell)
  return [x for c in cells for x in prefix_scan(c) if haversine(x) <= r]

Why it's wrong at edges: the Z-order curve jumps; adjacent points on opposite sides of a major boundary share no prefix. Neighbor scans fix correctness at the cost of 9× scans.

A.2 S2#

Cube-face projection → (face, i, j) → Hilbert position → 64-bit ID with level encoded in trailing bits. Children of a cell occupy a contiguous ID range: [cell.range_min(), cell.range_max()]. Region coverer parameters: min_level, max_level, max_cells — trade precision (fewer false positives) against number of ranges.

A.3 H3#

Icosahedron-based hexagonal grid, 16 resolutions, aperture 7 (each parent ≈ 7 children). k_ring(cell, k) gives all cells within k steps — ideal for smoothing traffic speeds or surge. Not exactly hierarchical; don't use for exact containment.

A.4 Quadtree for Moving Objects#

In-memory, split leaf at >N points (e.g., 100), merge below N/4. Good for drivers updating every 4s (Proximity Matching); not for durable storage.

A.5 Quick Comparison#

Appendix B: Routing Mechanics#

B.1 Contraction Hierarchies#

preprocess:
  order nodes by importance (edge difference, contracted neighbors, ...)
  for v in order:
    for each pair (u, w) of uncontracted neighbors via v:
      if shortest u→w goes through v: add shortcut(u, w, d(u,v)+d(v,w))
query(s, t):
  bidirectional Dijkstra, forward only to higher-ranked nodes, backward likewise
  meet at the highest node on the path; unpack shortcuts for the polyline

B.2 Partition-Based Customizable Routing#

preprocess (weekly): multi-level balanced partition; each level's cells have few boundary nodes
customize (every 1–2 min), per cell, bottom-up, in parallel:
  for each pair of boundary nodes (a, b): overlay_edge(a, b) = shortest path inside cell
query: bidirectional Dijkstra using fine edges near s and t, overlay edges elsewhere

B.3 Time-Dependent Routing#

For trips >45 minutes, edge weight = f(arrival time at edge). Use live speeds for edges reached within ~15–20 minutes, then blend toward historical profiles for the predicted arrival bucket.

B.4 Reroute Policy#

Active sessions re-query every 1–2 min or when a traffic change touches segments on the current route (push invalidation by segment → session index). Offer reroute when savings ≥ max(2 min, 10%) to avoid flapping.

Appendix C: Traffic Pipeline#

Key rules: trim trip ends; rotate device IDs daily; drop raw probes after 24h; blend w = min(1, probe_count / 20) × freshness_decay(age).

Appendix D: API Contract and Client Behavior#

• Route responses include map_release, traffic_age_s, eta_confidence for reproducibility.
• Clients batch probes (5–15s batches) to save battery and connections; server controls sampling rate by config.
• Tile URLs: /tiles/{release}/{z}/{x}/{y}.mvt — immutable, Cache-Control: max-age=31536000.
• Retry with jitter on route failures; show cached last route if routing is unavailable during navigation.

Appendix E: Observability#

E.1 Core Metrics#

route_latency_ms{p50,p99}
traffic_segment_age_seconds{p50,p95}{region}
historical_fallback_ratio{region}
eta_abs_error_pct{region}          # from completed trips
reroute_rate, off_route_rate {region, map_release}
mapmatch_consumer_lag
published_rows_below_k_total       # must be 0
cdn_tile_hit_rate

E.2 Critical Alerts#

E.3 Debugging the Silent Failure#

Start with data age by region, then release version, then model version. Errors are the last place to look.

Appendix F: Scale Evolution#

What You Don't Build on Day One#

• Your own routing engine (buy or open source)
• ML ETA models before you have trip-duration ground truth
• Global graph stitching before cross-region demand exists
• Raster tiles in any form

Appendix G: Multi-Tenancy and Cost#

• Partner isolation: dedicated routing pools and quotas for API customers.
• Matrix pricing: bill per element, not per request (a 25×25 matrix is 625 routes).
• Reroute frequency is the biggest product-controlled cost lever; expose it in cost dashboards.