Bounding the Search

In one line: segmentation made each piece small and exit points made traversal cheap. This is the step that decides how many pieces to look at at all, and without it the high-level graph is still global.

The mechanism

For example, if the aerial distance is 10 kilometres, we only consider segments within a 10-kilometre radius (or bounding box) of the design and destination. This drastically reduces the graph size.

Once we filter the segments, we construct a graph with the exit points of the selected segments as vertices and the pre-calculated paths between them as edges. We then run the shortest path algorithm on this simplified graph.

The worked sequence:

1. Source S and destination D lie in two different segments.
2. The aerial distance between S and D is 5 miles, calculated using the haversine formula.
3. Include the segments within 5 miles of S and D in all directions.
4. Include the exit points of the new segments in the graph.
5. Find the possible exits for S and D from their respective segments, and the shortest path (already calculated) to all exit points.

Step 2: haversine gives aerial distance = 5 miles

Step 3: include every segment within 5 miles

        +----+----+----+
        |    |    |    |
        +----+-S--+----+     <- S's segment plus neighbours
        |    |    |    |
        +----+----+-D--+     <- D's segment plus neighbours
        |    |    |    |
        +----+----+----+

Everything outside this region is never considered.

Aerial distance is a lower bound on road distance — and that is what makes this safe

The reasoning is worth making explicit, because it is what separates a sound pruning rule from a guess.

Straight-line distance between two points is always less than or equal to the distance by road — you cannot drive a shorter path than the one a bird flies. So if S and D are 5 miles apart as the crow flies, the actual route is at least 5 miles.

That gives a principled bound: a route wandering more than a few miles off the direct line is almost certainly not optimal, so segments far outside that corridor can be safely ignored.

This is exactly the admissible heuristic that makes A* work, which Lesson 5 named alongside Dijkstra. A* uses straight-line distance to steer exploration toward the target precisely because it never overestimates. Here the same property is used one level up — to prune whole segments rather than individual vertices.

Same idea, two scales: an optimistic estimate of remaining distance lets you rule things out without examining them.

A radius equal to the aerial distance is generous, and it is not strictly safe

The rule as stated — "if the aerial distance is 10 km, consider segments within a 10 km radius" — is a heuristic rather than a guarantee, and it is worth being honest about that.

Generous because a search region roughly twice the direct distance wide includes a great deal of area that no reasonable route would use.

Not strictly safe because geography can force long detours. A route around a bay, a mountain range, or a national border may leave the corridor entirely — the road distance can be several times the aerial distance, and the optimal path might pass through a segment the bound excluded.

So the design is trading optimality for tractability, and that is the right trade for a service returning a route in 2–3 seconds. Real systems handle the pathological cases by widening the search when no route is found, or by keeping a separate long-distance graph of major highways.

Worth naming in an interview: this prunes soundly in the common case and can miss in the presence of large geographic obstacles. Claiming it is always optimal would be wrong.

Haversine rather than Euclidean, because the Earth is not flat

The haversine formula computes great-circle distance between two latitude/longitude points — distance over a sphere.

Using plain Euclidean distance on raw latitude and longitude would be wrong in a way that grows with distance and latitude. A degree of longitude is about 111 km at the equator and roughly half that at 60° north — so treating coordinates as a flat plane distorts east-west distances severely away from the equator, and the error compounds over long routes.

For a system operating globally, that matters. Getting the bound wrong means either over-pruning (missing routes) or under-pruning (searching too much).

It is a small correctness detail that signals familiarity with geospatial work — the same category as knowing that latitude and longitude are not interchangeable with x and y.

The bound is sound rather than a guess: straight-line distance is always ≤ road distance, so a corridor sized by the aerial distance cannot exclude the true optimum by much. It is the same admissible-heuristic reasoning that makes A* work — an optimistic estimate of what remains lets you rule things out without examining them.

Summary of the scalability solution

We partition the road network into segments. Local queries run on the detailed segment graph, while long-distance queries use a simplified graph of connected segments.

Three techniques stacked, each addressing a different part of the problem

It is worth seeing how Lessons 5, 7, and 8 compose, because each alone is insufficient:

Without segmentation the graph does not fit in memory. Without exit points, crossing many segments still means traversing all their roads. Without bounding, the high-level graph still spans the world.

Together they take an infeasible global shortest-path query and reduce it to a small in-memory graph over a handful of segments — which is what makes the 2–3 second requirement achievable.

That layering is the chapter's real answer to its scalability challenge, and being able to state all three and what each contributes is the strongest version of the answer.

The three compose, and each is useless without the others. Segmenting without precomputing still traverses every road. Precomputing without bounding still considers every segment on Earth. Bounding without segmentation has nothing to prune.

Interview signal by level

Next: computing the ETA.