Design maps and route planning

01Define what a route promises

A maps product has two different jobs. Map tiles draw the background the user sees; routing computes a legal sequence of roads from an origin to a destination. They can share source geography without sharing a serving system. We design driving directions for departure now, with map display and optional navigation refresh. Address geocoding, transit, lane guidance and offline navigation are separate extensions.

Before choosing an engine, ask: do we need driving directions for departure now or predictions for future departures, and how quickly must known closures affect answers? The worked scope below chooses departure now and an explicit closure-freshness target.

Represent intersections as vertices and permitted directed movements as edges. An edge carries a nonnegative travel-time cost. One-way streets remove reverse movements. A prohibited turn depends on the incoming road, so the search state must preserve that information rather than treating every intersection as an unrestricted connection.

Use one small graph throughout: A→B takes four minutes, B→D four, A→C three and C→D eight. The best permitted route is A-B-D at eight minutes, although A-C looks cheaper initially. Road snapping connects coordinates to plausible accessible road positions. The basic flow is coordinate validation → road snapping → search on one graph version → path reconstruction → closure validation → response. This is the complete product before any cache, hierarchy or regional shard is introduced.

02Functional requirements

Agree on what the service must do before choosing its components.

1. Display the map. Serve versioned map tiles for the requested area and zoom level.
2. Find driving directions. Accept origin, destination, a driving profile and avoidance preferences such as avoid-toll; return the road/turn sequence, geometry, distance and estimated duration. Connect coordinates to plausible accessible road positions: an overpass must not snap to the road underneath merely because it is close.
3. Refresh a route. Recompute after a reported incident, with optional refresh notices for active navigation.
4. Explain the result. Return data versions and freshness, distinguish an inaccessible endpoint from valid endpoints with no connecting route, and label historical-traffic fallback. Address geocoding, transit, lane guidance and offline navigation are outside the worked scope.

03Non-functional requirements

Use these hypothetical requirements for the worked interview. Confirm the assumptions with the interviewer; the numerical targets require testing and are not measured results. For latency, p95 and p99 mean that 95% and 99% of measured delays, respectively, are no greater than the reported value.

1. Workload. Plan for ten million route requests/day and a peak of 2,000/s. Size repeated map-tile bytes separately from route computation.
2. Latency and availability. Target route p95 below 300 ms and 99.9% routing availability under the admitted workload. Test long trips and incident spikes as well as short city routes.
3. Freshness. Publish validated topology daily, ordinary traffic within one minute and trusted urgent closures within ten seconds. Return observation and validation versions so callers can interpret freshness.
4. Route correctness. Every returned path must obey one compatible topology, turn and weight model, plus known closures checked at the stated final validation boundary. An estimated arrival time is an estimate under that model, not a promised physical arrival time.
5. Honest failure behavior. Missing traffic may permit labeled historical weights. Missing legal connectivity must produce no route; stale urgent restrictions can require refusal or an explicitly permitted degraded result. A successful search cannot reveal an unreported physical incident.
6. Access and privacy. Authenticate callers, bound expensive requests, restrict map/closure administration and keep navigation positions private with limited retention. Public tile caches must not expose private location history.

04Make one correct in-memory search work

One server loads the directed, turn-aware graph and spatial index. It validates the request, finds bounded accessible snap candidates and runs Dijkstra with fixed nonnegative costs. The algorithm keeps the cheapest currently known distance to each search state and repeatedly settles the smallest one. Settling means its minimum cost is established under these assumptions.

Dijkstra trace from A

Save predecessor edges whenever a distance improves, and follow them backward to reconstruct actual roads and turn instructions. Choosing C and committing to its entire continuation after the first cheap edge would be a greedy mistake.

An endpoint inside a road needs a permitted partial-edge connection with the appropriate cost; it does not require traversing the entire road or inventing a reverse movement. Use a bounded set of plausible candidates where necessary.

For updates, build a second complete graph, validate it, then switch an active pointer. Each query retains its selected graph until it finishes. Static tiles can initially be ordinary files. This baseline is useful and testable even without a specialized distributed routing system.

05Separate search CPU from repeated tile bytes

The average route rate is 10M/86,400 ≈ 116/s, much lower than the chosen peak. If a representative route costs 50 milliseconds of CPU, 2,000/s requires 100 busy cores. At a planned 60% utilization ceiling that suggests about 167 cores before failure headroom. Benchmark long and cross-region trips: a short-city average does not bound their search work.

Three loaded graph versions already require 9.6 GB for those raw edge records alone. Keep old versions for active requests and rollback, then release them safely. The dominant costs differ: tile reuse reduces network load, search acceleration reduces CPU, and version retention increases memory. More application servers cannot substitute for deciding which of these resources is exhausted.

06Name the graph and the result precisely

Route request

POST /routes

Route response

Validate coordinates and bound route alternatives and matrix dimensions. A request retry can be a fresh computation; if the client needs reproducibility, it explicitly requests a retained bundle.

Keep these model artifacts separate:

A shortcut speeds search by representing several real roads as one connection. Keep the list of those roads: a shortcut becomes invalid if a road it uses closes.

Cache identities

Rounding coordinates too aggressively can move a request across a divided highway. Navigation positions are private session data with short retention; they do not belong in public tile-cache keys or broadly readable request logs.

07Fix the measured bottleneck with the matching mechanism

First put immutable tiles behind a CDN. Their repeated bytes justify edge caching independently of route computation. This adds cache lifecycle and origin storage; it does not make traffic estimates fresher.

Next add warmed routing replicas. A query router sends each request to a worker that already loaded and verified the required bundle. Independent queries scale across workers while each search remains local. The cost is replicated graph memory and warm-up time. A cold process is not ready merely because its HTTP port responds.

The final interview design keeps each search local and scales requests with these warmed replicas. If long searches later dominate CPU, A* is a possible follow-up: it uses an estimate of remaining cost to explore promising paths first. That estimate and the implementation must preserve the shortest-path guarantee. Precomputed shortcuts are another extension, with their own update cost; neither is necessary to explain the working design.

Geographic partitioning is also optional. It becomes relevant when a full graph no longer fits economically on a worker. A route can cross several boundaries, so simply choosing the nearest border is incorrect. Keep this as a clearly separate expansion discussion; the main capacity plan uses full graph replicas and does not depend on a regional routing protocol.

08Publish traffic as a coherent release

A build pipeline accepts trusted map edits and consented traffic observations. Map matching associates a sequence of observations with plausible directed roads; one noisy GPS point is weak evidence. Reject implausible jumps, aggregate speeds and use historical estimates where current samples are sparse. Trusted closures remain hard restrictions, rather than merely very slow travel weights.

A candidate bundle contains topology, turn rules, weights, spatial indexes and any compatible shortcut structures. Check connectivity, access restrictions, checksums and representative routes against the reference search. Stage it on required workers before publishing its manifest. Failed uploads or half-built indexes must not become a serving release.

After validating compatibility, atomically change the active pointer to the new bundle. In-flight requests keep their old bundle, so cleanup waits until they finish. Requests may use different complete versions during rollout, but one request never mixes them. Retained releases also stay available.

Urgent closures additionally invalidate affected cached routes or prompt navigation recomputation. Validate their edge identities against the selected topology. A bundle name alone is not a correctness proof: the build and serving checks establish that its components can actually be used together.

09Trace the final request and its cache boundary

Request q61 asks for A to D while bundle g12/w8 is active. Follow the request in order:

1. Admit the request. Authenticate and apply a work budget.
2. Choose one model. Capture the bundle reference, then snap the endpoints under the car profile.
3. Search. Find A-B-D = 8.
4. Reconstruct the roads. Build the real-road sequence before turns and geometry, because access checks concern those roads. An optional accelerated variant first expands shortcuts into their underlying roads.

Before releasing the response:

1. Validate known closures. Check the expanded path against available closure data; record its version and validation time.
2. Recompute if necessary. If B-D is closed, reject that path and search a compatible updated model, choosing A-C-D = 11 if permitted.
3. Respect the remaining budget. If recomputation cannot finish in time, return an explicit retry/degraded outcome. Never label a forbidden old path as a successful current route.

A route-cache hit follows the same closure policy. Immutable bundle keys prevent accidental version mixing, but they do not override a deliberate urgent-closure invalidation. Return traffic freshness and whether historical weights were used. Release the graph reference after response construction.

An incident reported after the stated validation boundary can invalidate an already returned route. An active navigation session receives a refresh notice and requests another route. The service can act only on information it has received; it cannot recall an answer already sent.

10Check legal movement, search and version consistency

Check three things: the graph represents legal movements, the search finds the right path, and the request uses compatible data throughout. Each item addresses a different source of bad directions. A fast algorithm cannot compensate for a missing one-way restriction, and an accurate map cannot compensate for greedy path selection.

Dijkstra works here because the selected costs stay fixed and nonnegative while the query runs. Once the cheapest unsettled state is selected, reaching it through another unsettled state cannot make it cheaper. In the example, C is explored first without committing to C-D; B then supplies the better route to D. Include disconnected destinations and zero-cost edges in tests.

For ordinary updates, build the replacement separately and let a query finish on its captured graph. New requests can select the replacement. Retaining the old object while a query references it prevents an update from changing the meaning of a path halfway through its calculation. Memory management details belong to implementation review.

Known closures require a separate response check because avoiding a prohibited road matters even when the search began earlier. This does not guarantee awareness of incidents never reported to the service. Future departures, continuously changing edge costs and specialized acceleration have additional assumptions; they are optional follow-ups, not hidden dependencies of this baseline.

11Recover service without inventing safe roads

A routing-worker crash loses an in-flight calculation, so the client retries, potentially on a newer bundle. A build crash leaves unadvertised artifacts. A bad release can roll back to a retained compatible bundle, while closure enforcement still follows its explicit freshness policy. If urgent restrictions are too stale to satisfy the contract, refuse affected requests or disclose the permitted degraded mode.

Measure route latency by length and region, CPU/query, snapping distance, no-route rate, traffic age, expanded-path restriction violations and ETA error. Aggregate ETA error can hide a poorly modeled road class, so inspect cohorts and compare predicted with observed trips carefully. Preserve only the location history actually needed and restrict administrative map/closure updates.

Test one-way roads, forbidden turns, overpasses and disconnected islands. Optional regional or accelerated variants also need region exit/reentry and closure-under-shortcut tests. Compare candidate engines with a trusted base search before a limited rollout. Load tests include matrices and long routes, not only easy urban paths. Reserve reroute capacity for active navigation during incident spikes.

The next scaling decision follows measurements: lower query CPU is of little value if a ten-minute rebuild cannot meet one-minute traffic freshness. Explain both serving and update cost before recommending an acceleration method.

12Check the design against its requirements

Before closing, check the final design against the agreed requirements. FR means functional requirement and NFR means non-functional requirement; the numbers refer to the lists above. These are proposed validation checks, not test results.

13Rapid revision

Rehearse the numbered functional requirements and non-functional targets first. Use this table to recall the mechanisms, then close with the requirements check above.

Remember: One road model; check closures before replying.

A concise closing is: “I start with a correct local road search, separate tile delivery, and replicate warmed graph workers. Acceleration is justified by measured CPU and validated against the base search. Each request keeps one compatible bundle and checks known closures before release. I accept explicit freshness and recomputation limits rather than returning an invented legal path.”

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.