Design maps and route planning

01Problem and scope

A routing service finds legal paths using the selected road graph, travel profile and traffic version. Displaying the map is a separate job: delivering map tiles. In the example, A-B-D costs 4+4=8 minutes and A-C-D costs 3+8=11. The route follows legal roads with the lowest travel-time cost, which may differ from the shortest geometric path. Its estimated duration is not a guaranteed arrival time.

Represent intersections as vertices and directed roads as edges with nonnegative travel-time costs. One-way restrictions remove reverse movements. Turns may need extra state recording the incoming road. On one server, store the graph and run a shortest-path algorithm; only then discuss regional distribution.

I clarify whether the interviewer means drawing a map, computing a route, or navigating a moving driver. We build map display and point-to-point driving routes for departure now, with an optional navigation session that refreshes after incidents. We do not claim the private design of a named map provider.

The product question is “fastest under the selected road and traffic model,” not “guaranteed arrival at exactly this time.” Traffic estimates can be wrong. Access restrictions and known closures, however, are hard constraints in that selected model. The route client should not be sent across a forbidden edge merely because its geometric path is shorter.

I ask about geographic scope and choose a large country with regional deployments and cross-region routes. That makes boundary routing and consistent map versions concrete requirements without pretending every street fits on one tiny server.

02Functional requirements

1. View a map. Versioned tiles for a bounding box and zoom.
2. Request directions. Legal road sequence, geometry, duration, distance, and data versions.
3. Avoid tolls. Search the permitted profile or clearly report no route.
4. Start away from a road. Snap to an accessible candidate within a bounded radius.
5. Refresh after an incident. Recompute under a newer compatible traffic/closure bundle.
6. Request a matrix. Bounded origin/destination set with explicit resource limits.

Scope and acceptance boundaries

Support background map tiles, driving directions, distance, estimated arrival time, avoid-toll preferences, and known closures. Geocoding addresses, transit schedules, offline routing, and lane guidance are separate extensions. State whether departure is now or a future time; future-time costs require stronger modeling than a single current-speed snapshot.

A tile is a visual map fragment, not the routing graph. Snapping connects a GPS point to plausible accessible roads. Map matching interprets a sequence of noisy GPS observations. Routing engines expose these operations separately; OSRM is one documented implementation. OSRM API.

A no-route result differs from a snapping failure. A point may have no plausible accessible road, or two valid snapped points may be disconnected under current restrictions. Those conditions receive separate codes and user guidance.

An alternative-route feature promises a small set of meaningfully different valid candidates, not every possible path. We keep it optional because finding diversity and ranking alternatives requires more work than one shortest-path result. Geometry simplification for display must not change the underlying legal road sequence used for directions.

03Non-functional requirements

1. Workload. Assume ten million route requests/day and a 2,000/s peak.
2. Latency. Target route p95 below 300 ms for ordinary regional trips and tile p95 below 100 ms from a nearby edge cache.
3. Availability. Target 99.9% routing availability. The sample algorithms do not supply this objective automatically.
4. Update freshness. Publish validated topology daily, normally refresh traffic weights within one minute, and target trusted urgent-closure ingestion within ten seconds.
5. Version consistency. Use one compatible immutable bundle of topology, turn restrictions, weights and acceleration structures. Return its versions and traffic freshness.
6. Closure validation. Before returning a route, check its roads and turns against the closure data available at final validation, then return that data's version and the validation time.

Safe degradation

An older estimate can still describe one consistent road model. Mixing versions can instead pair shortcuts with costs or roads that no longer match. Never invent a route to meet uptime. No service can guarantee knowledge of an unreported physical incident; an already returned route can be invalidated by a newly reported closure.

04Capacity estimates

The 50-millisecond CPU cost is a benchmark assumption, not an engine guarantee. Long rural/interregional routes may explore more graph than short city trips. Cache immutable tile versions separately from short-lived traffic-sensitive route results.

With a 60% planned CPU utilization ceiling, the assumed 100 cores of route work implies about 167 cores before redundancy. Surviving the loss of one of three equally sized zones while maintaining that utilization would require more reserved capacity. A worker may reach its memory-bandwidth limit first, especially if the search repeatedly fetches graph data that is not nearby in memory.

At an illustrative 20 KB route response, 2,000 routes/s yields 40 MB/s of response payload. Tile traffic is different: one billion 30 KB tiles/day is 30 TB/day, about 347 MB/s average, before peaks. A CDN is therefore justified by repeated immutable map content even if route computation stays regional.

A 100-by-100 travel-time matrix contains 10,000 pairs. A specialized many-to-many algorithm can reuse work, but the request is not equivalent to one route. Cap matrix dimensions and use estimated work, rather than HTTP request count, when deciding how many matrices to admit.

Version retention multiplies graph memory or disk. Three simultaneously loaded 3.2 GB raw edge sets require 9.6 GB before geometry, turns, shortcuts, indexes, and worker overhead. Retain only the bundles needed for active queries, rollback, and the declared replay window, with explicit query pins: records that prevent cleanup from deleting a graph bundle while a query is using it.

05APIs and contracts

Route request and response

POST /routes accepts {requestId:"q61",origin:[lon,lat],destination:[lon,lat],mode:"car",avoidTolls:true,departure:"now"}. The response includes snapped endpoints, durationSeconds=480, distanceMeters, turn steps, geometry, bundleId, closureVersion, and trafficObservedThrough. A retry is a fresh computation unless a client explicitly requests the same retained bundle; route calculation itself has no financial side effect requiring a persistent idempotency ledger.

Distinct error outcomes

Invalid coordinates, unsupported profiles, excessive matrix size, no accessible segment, and no connecting route are distinct errors. Returning straight-line distance as a driving route would misrepresent the product. If a matrix offers a fallback estimate, each such cell must be flagged as estimated rather than a valid road path.

Tile and route-cache identities

Tile URLs include style and immutable map version as well as zoom/x/y. Route-cache identity includes profile, snapped endpoints, avoidance preferences, departure assumptions, and compatible bundle version. Rounding endpoints too much can move them across a divided road or onto an overpass. Any cache-key simplification must preserve the chosen road connection.

Navigation session and privacy

A navigation session supplies a route ID, current location, and last accepted closure version. Position updates are authenticated and short-lived. They are not exposed through public cache keys or reused as another user's raw trace.

06Data model and access patterns

Store both the actual road connections and the built data structures that speed up search. A shortcut is a search edge summarizing an existing path; it must retain enough information to expand back into those roads. It does not create a new legal road connection. The bundle manifest identifies the road, turn, weight and shortcut versions built to work together; publication checks that they are compatible.

Raw map edits and consent-based observations are source inputs. Built routing graphs and tiles are derived artifacts. The bundle manifest is authoritative for which compatible artifacts are serving. A traffic update referencing removed edge IDs cannot be blindly applied to a new topology; builders map or reject incompatible observations before publication.

Location histories receive a separate short retention and access policy from public road geometry. Aggregated traffic should not allow a route query to retrieve an individual driver's trace.

A snapped point may lie partway along a road edge. Add temporary directed connectors or split that edge for the query. Use proportional or model-derived travel costs, while keeping its turn and access restrictions. On a one-way 1,000 m segment, an origin 200 m from its start and destination 900 m from its start imply a 700 m forward traversal, not a full 1,000 m edge or an illegal reverse shortcut. Candidate snapping also needs a bounded search policy: selecting one plausible candidate is not proof of the best route across all plausible candidates.

07Basic working design

The first server loads a directed, turn-aware graph and its spatial index into memory. For q61 it validates the car profile, chooses accessible snap candidates near A and D, and runs Dijkstra under fixed nonnegative travel-time weights. It relaxes tentative distances by checking whether each explored edge gives a cheaper known path, saving the predecessor edge whenever it does. When D is settled—its minimum cost is established—the server follows those saved edges backward to reconstruct the route.

In the example graph, A→C initially looks promising at three minutes, but its continuation to D costs eight, producing eleven total. A→B takes four and B→D four, so that path wins at eight. The server returns the real edge sequence, turn instructions, geometry, and the pinned data version. Map tiles can be served as simple static files separately.

This baseline supports a legitimate small routing product. It has no distributed graph transaction and no need to move a query between servers. A map refresh builds a second immutable graph and switches a local pointer only after validation, allowing in-flight queries to finish on their old version.

We deliberately begin with correct base search. Accelerating an incorrect access model only returns illegal answers faster. Turn restrictions, one-way roads, and unreachable endpoints are tested before adding hierarchy shortcuts or regional sharding.

08Find the baseline flaws

At the assumed peak, fifty milliseconds of CPU per query consumes one hundred cores. A single worker cannot provide that compute, and long interregional paths may explore far more state than the average. Map tiles additionally create repeated bandwidth load unrelated to route CPU. Separate tile bandwidth from route computation when sizing servers.

A correctness failure appears when a worker uses a shortcut A→D with cost 8 built from A→B→D, while a live update closes B→D. If it treats the shortcut as an independent legal road, it still returns eight minutes through a forbidden segment. The acceleration structure must be compatible with changed constraints or the query must fall back to a method that checks them correctly.

Another failure comes from naive regional partitioning. The fastest valid route between two points inside region X may leave X and reenter. Searching only X or selecting the nearest border misses valid candidates. Regional boundaries are deployment choices, not road-access restrictions.

Finally, a nearest geometric snap can place the route client on a motorway above a local street without an accessible ramp. Directions then begin with an impossible movement. Snapping uses mode, direction, road access, and a bounded set of candidates, not only Euclidean distance.

09Improve the design, step by step

The baseline already finds a valid shortest path; the scaling question is how to examine less graph or spread independent queries across machines. For the shortest-path guarantee used here, A* guides exploration with an estimate no greater than the remaining cost. Preprocessed methods instead build reusable path summaries before requests arrive. Those are different ways to reduce search work, with different update costs.

A routing hierarchy summarizes known subpaths as shortcuts with valid costs. If weights or restrictions change, update the affected shortcut data or use a search that does not rely on it. For regional shards, an overlay records connecting border routes; a valid path may leave and reenter a region. Do not assume one boundary crossing or blindly choose the nearest border. Bound matrix sizes because n origins×m destinations can multiply work far beyond one query.

First, split immutable tile delivery from route computation. The trigger is high repeated tile bandwidth. Put versioned tiles behind edge caches while route servers compute personalized paths. This reduces origin load and improves map rendering, at the cost of cache storage and style/version lifecycle. Direct static serving remains sufficient for a small geographic product. Tile freshness does not determine traffic-weight freshness.

Second, replicate in-memory routing workers. The trigger is the 100-core peak estimate. A region-aware router sends queries to warmed workers with a compatible graph bundle already loaded. This increases parallel route throughput without changing shortest-path semantics. Each replica needs graph memory and time to load it. A new worker must check checksums and bundle compatibility before accepting requests. One larger server is simpler while measured demand fits comfortably.

Third, preprocess a valid acceleration structure. The trigger is long-route search CPU. Shortcuts or hierarchical methods summarize subpaths while retaining expansion information and compatibility requirements. The search may examine far fewer edges, but building, storing and updating shortcuts takes extra work. A base Dijkstra/A* fallback remains useful for unusual profiles or changed restrictions that invalidate shortcuts. We do not assume every hierarchy supports arbitrary dynamic weights without rebuilding.

Fourth, partition very large graphs with a compatible overlay. The trigger is a bundle too large or expensive to replicate everywhere. Regional workers handle local detail while a border overlay represents valid interregional connections and costs under the same release. Each worker stores less graph data, but workers must coordinate how a route crosses their boundaries. The overlay must permit repeated region crossings, and its selected route must expand into valid local subpaths. Full-graph replicas remain preferable when affordable because they avoid these distributed boundary concerns.

Each optimization is accepted only after comparison with a trusted base search on representative and adversarial routes. Faster average latency is not evidence that the new routing method still respects restrictions.

10Detailed architecture

Validated build pipeline

The final system has a data pipeline and a serving path. Map editors and trusted feeds supply topology and restriction updates. A traffic pipeline validates and aggregates consent-based observations. Build workers produce compatible graph, turn, weight, shortcut, and snap artifacts, test them, and register immutable bundles. A manifest authority switches the active bundle only after the required serving regions can load it.

Tile and route serving

Clients fetch tiles from a CDN backed by immutable tile objects. Route requests instead pass through authentication and admission, then a regional query router. Warm routing workers pin one manifest bundle, use a graph cache or local memory, perform search, expand shortcuts, validate closure constraints, and return the versioned result. The route cache key includes all request choices that affect the path, plus the bundle version.

Urgent closures

Trusted urgent closures enter a versioned overlay and invalidate affected cached routes or trigger navigation recomputation under the stated freshness policy. Check that the overlay’s edge IDs and expanded shortcuts belong to the selected graph; closure data cannot be applied to an arbitrary graph version.

Artifact lifetime and implementation

Builds, traffic aggregation, tile generation, and deployment are asynchronous. Query routing, snapping, search, and final validation are synchronous. Old artifacts remain pinned for active queries and rollback. A cleanup transaction cannot mark an artifact deleting while a serving manifest or valid query pin references it; publication rejects deleting artifacts. This makes retention safe even during a release race.

OSRM offers a concrete build/serve option with extraction plus either contraction-hierarchy preprocessing or multi-level partition/customization. Select the pipeline for update frequency and supported profiles, then verify its update capabilities against the one-minute traffic objective. PostgreSQL with PostGIS/pgRouting is useful for smaller graphs, spatial preprocessing and a reference shortest-path implementation. Neither product name automatically supplies this chapter’s bundle publication, urgent-closure boundary or arbitrary per-request restriction support; those contracts must be verified in the selected deployment.

11Write path and acknowledgement

Topology, restrictions and traffic changes produce tested compatible artifacts. Activate a version only when the required serving workers can use the complete bundle.

GPS observations collected with consent are noisy. Use movement and direction to match a sequence to roads, reject implausible samples, aggregate speeds over time, and supplement sparse observations with historical profiles. Do not expose raw traces through route caches. Known closures remain access constraints even when live-speed updates fail.

Publish topology builds after connectivity/restriction checks and sample-route tests; switch a version manifest atomically. Keep older compatible snapshots for in-flight queries and rollback. For future departures, evaluate time-dependent edge costs at arrival to each edge. Algorithms require explicit assumptions, such as whether leaving an edge later can ever produce earlier arrival; do not reuse a static proof without those conditions.

1. Each accepted observation records where it came from, when it occurred and which location use was permitted. The pipeline rejects impossible jumps and stale or malformed samples before aggregation.
2. Map matching associates a sequence with plausible directed edges under a known topology. One isolated noisy point does not establish a vehicle's road or speed.
3. Aggregation estimates travel time and confidence for each edge, using historical profiles when there are too few reliable samples. Trusted closure events remain hard restrictions rather than inferred low speeds.
4. A build or customization job creates a candidate bundle g12/w9 with compatible turns and shortcut data. It runs connectivity, access, expansion, and sample-route comparisons against a verified reference.
5. Workers stage and checksum the immutable artifacts. The manifest authority atomically publishes the compatible bundle and its serving policy, while retaining references for active old-version queries.
6. Cache entries keyed to w8 are no longer selected as w9 results. Active navigation may receive a refresh notice. A failed publication leaves the previous manifest intact; uploaded candidate artifacts alone never make a release live.

The relevant time-dependent condition is called FIFO, for first in, first out: entering the same edge later cannot produce an earlier arrival at its end. This matters because a shortest-path search must know whether arriving sooner can ever be worse than arriving later. The algorithm section returns to the precise condition and what changes when waiting can help.

For departure in the future, an edge's cost depends on when the path reaches it. The static eight-minute example does not prove correctness for arbitrary non-FIFO time-dependent travel, so that extension requires a matching algorithm and explicit waiting assumptions.

12Read and delivery path

Each route keeps one compatible graph, weight set and profile while it runs. It connects endpoints to accessible roads and expands shortcuts into the actual road sequence.

1. q61 validates locations/profile and pins g12/w8.
2. The snap index finds accessible candidates A and D; nearby overpass geometry alone cannot imply access.
3. Search evaluates A-B-D=8 and A-C-D=11 under those versions.
4. Expand any shortcut edges into actual roads, then construct turn steps and geometry.
5. Return the eight-minute estimate with freshness/version context; tiles load independently.

Include profile, endpoints, preferences, departure assumptions, and graph/weight versions in route-cache identity.

6. The worker checks the expanded edge and turn sequence against the closure version at its final validation boundary. If a newly known closure invalidates B→D, it recomputes or returns a retryable update condition according to the latency budget; it does not return a route whose actual expanded path fails the selected constraints.
7. It returns the bundle, validation time, traffic freshness, estimate confidence and any fallback used. The route client can distinguish current observed traffic from historical estimation.
8. The query releases its artifact pin after response construction. A navigation session retains route identity and listens for relevant incident changes; it does not keep the entire old graph version alive indefinitely merely because the user has not closed the app.

A cache hit still obeys closure freshness policy. The cache key protects against accidental version mixing, but an urgent incident may deliberately invalidate an otherwise valid older cache entry. The routing product must choose that policy explicitly rather than assuming a short TTL makes every cached route safe.

13Correctness deep dive

Dijkstra repeatedly settles the unsettled vertex with the smallest known accumulated cost. From A, tentative B=4 and C=3. Settle C first: D becomes 11. Settle B next: D improves to 8. Then settling D establishes the eight-minute route for this nonnegative-cost graph. pgRouting’s Dijkstra explanation.

A* adds a lower bound for remaining cost to guide exploration. Straight-line distance divided by a genuine maximum possible speed can be admissible; an arbitrary ETA guess may not be. If optimality is promised, pruning must preserve it. Road closures represent forbidden edges, not merely a tiny speed penalty.

The key algorithm invariant is that, with nonnegative costs, the smallest unsettled tentative distance cannot be improved through a later unsettled vertex. In the example, settling C at 3 produces D11; settling B at 4 improves D8; D is then settled at 8. Choosing C greedily and committing its entire path at the first step would be wrong. A* may guide the queue with a lower bound, but its exact correctness conditions still matter.

Publication can also race a query. Query Q must select its graph bundle as one unit while publisher P switches the active bundle:

beginRoute():
  transactionally read active bundle B
  require B status == ready and artifacts not deleting
  acquire query pin on B
  return immutable B

publish(candidate C):
  verify compatible topology/turns/weights/shortcuts
  require all artifacts ready and not deleting
  atomically change active bundle to C with references

For a time-dependent edge, FIFO means departing later cannot produce an earlier arrival on that edge: t + travelTime(t) is nondecreasing. Under the appropriate FIFO assumptions, a label-setting time-dependent search can remain valid. If FIFO does not hold, waiting may improve arrival and the algorithm/state model must represent that possibility; a static Dijkstra implementation cannot simply read changing costs mid-search.

14Failure and recovery

15Operations, security, and cost

Location data is sensitive. Authenticate navigation sessions, minimize raw trace retention, aggregate traffic, and restrict access to individual coordinates. Public tiles can be broadly cached, but personalized origin/destination pairs should not leak through shared logs or cache inspection. Trusted closure feeds require provenance and auditability so an unverified report cannot block an entire city automatically.

Track route p95/p99 by distance and region, snap distance, no-route rate, expanded-path restriction violations, traffic age, ETA error, and candidate-bundle validation failures. Compare ETA to completed trips with awareness of selection bias and detours; an aggregate error metric alone can conceal severe underestimation on one region or road class.

Before publication, test one-way streets, turn prohibitions, overpasses, disconnected islands, toll avoidance, border exits/reentries, and shortcut expansion after a closure. Run copies of representative queries against the candidate, previous release and a trusted base search, then compare their results without returning the candidate's answers to users yet. A canary rollout pins a fraction of traffic to the candidate and permits immediate manifest rollback.

At 167 assumed compute cores before redundancy, reducing mean CPU from 50 ms to 20 ms would reduce the same 2,000/s work from 100 to 40 core-seconds/s. That benefit must be weighed against preprocessing time and memory. If a traffic update requires rebuilding for ten minutes, a faster query engine may fail the one-minute freshness objective. Measure both sides of the tradeoff.

16Decision ledger and limitations

Start by replicating full regional bundles. Fetching individual graph vertices from remote servers would add many network waits and make the route depend on more servers staying available. When graph size forces partitioning, an overlay summarizes cross-boundary work instead of making every edge relaxation a network request.

The remaining limit is the accuracy and timeliness of input data. More cores cannot infer an unreported closure, and a mathematically shortest path under inaccurate travel times may not be fastest in reality. The product therefore returns estimates and freshness while preserving legal constraints in its known model.

Future departures, transit, and offline navigation are substantial extensions. Each changes the time model, access model, or update availability and deserves a fresh requirement discussion.

17Interview closing

“I separated map tiles from route computation. A route is a shortest legal path under the chosen cost model in a directed, turn-aware graph. I begin with a correct nonnegative-cost search and accessible endpoint snapping, then scale tiles through a CDN and route work through warmed replicas. Add precomputed shortcuts only when their versions match and they can be expanded back into valid roads.

“The hard serving guarantee is one coherent graph bundle per query. Topology, turns, weights, and shortcuts are pinned together, with final closure validation under a stated version. A release cannot make one query mix old shortcut costs and new restrictions. A route affected by a newly enforced closure must be recomputed against a compatible bundle before release, rather than retaining an invalid shortcut. Already returned routes can be refreshed through navigation notices.

“The tradeoffs are preprocessing versus freshness, graph memory versus regional boundaries, and current traffic versus labeled historical estimates. I would benchmark long and cross-border routes and test closures, overpasses, and turn prohibitions before optimizing average latency. The next measurement is whether query CPU or update-to-serving delay limits the product.”

If the interviewer adds future departures, I would use time-dependent costs evaluated at arrival to each edge and verify the relevant FIFO or waiting assumptions. The static proof would not be reused unchanged.

Recall the key ideas

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