Non-Vertex Locations

In one line: this is a small problem with a general lesson — your graph model does not match reality at the boundary, and handling that mismatch is often where real systems get their correctness.

The trick is that you do not change the algorithm. You change the graph — temporarily — so the algorithm's assumptions hold again.

The worked example

                    B
                   / \
        2         /9  \3
source ---- D ---+     +---- Destination
       \                    /
        \8                7/
         +------- E ------+

Possible paths                     Distance
source -> E -> Destination         8 + 7      = 15
source -> D -> B -> Destination    2 + 9 + 3  = 14

Since 14 is less than 15, we choose source -> D -> B -> destination

The nearest vertex is not necessarily the right one — that is the whole point

The obvious approach is "snap the user to the closest intersection and route from there." The example shows why that fails.

D is 2 away and E is 8 away, so D is far closer. But the decision cannot be made on that alone, because what matters is the total to the destination:

• Via the near vertex D: 2 + 9 + 3 = 14
• Via the far vertex E: 8 + 7 = 15

Here the near vertex happens to win — but only by one. Change B-to-destination from 3 to 5 and the far vertex E becomes better despite being four times further away.

So the rule is evaluate both ends of the edge against the full route, not snap to the nearest. A greedy local decision does not produce a globally optimal path.

This is a small instance of a general principle worth carrying: local optimality does not compose into global optimality. It is the same reason Dijkstra explores by cumulative distance rather than by nearest neighbour.

Practical consequence: a route can begin by driving away from your destination

The example explains a behaviour every driver has experienced — the app tells you to turn away from where you are going.

If you are on a one-way street or a divided highway, the only legal exit from your current edge may point backwards. The system evaluates both endpoints, finds that the "wrong direction" endpoint gives a shorter total, and routes you that way.

Worth mentioning in an interview because it demonstrates you have thought about what the model implies for users rather than only about the algorithm. It is also where one-way streets enter the picture: on a directed edge, only one endpoint is reachable, so the choice collapses and the detour can be substantial.

Finding which edge the user is on is a separate problem the design does not address

The lesson assumes you already know the user is on the edge between D and E. Getting there is map matching, and it is genuinely hard.

GPS gives a coordinate with error — often tens of metres, worse among tall buildings. That coordinate frequently falls between roads, or nearer a parallel road than the one you are actually on. A highway and its service road may be metres apart.

Real systems solve this with map matching: taking a sequence of positions and finding the most probable path through the road network, rather than snapping each point independently. Using history is what disambiguates the highway from the service road — your previous positions were on the highway, so you probably still are.

The design does not mention it, and it is a fair gap to raise: the graph model assumes you know your edge, and determining that from noisy GPS is its own inference problem.

This is also why precomputed paths need supplementing at query time

Lesson 5 precomputed shortest paths between vertices. But a real query starts and ends at arbitrary points on edges, which are not vertices and were never precomputed.

So a live query is a small composition:

1. From the user's point to each endpoint of their edge   <- computed live (short)
2. Between vertices                                        <- LOOKED UP (precomputed)
3. From an endpoint of the destination edge to the point   <- computed live (short)

Only the middle step is a lookup; the two ends are short live computations over a handful of metres.

That is the right division. The expensive part — traversing the road network — is precomputed, while the cheap part that cannot be precomputed because it depends on exact user position is done live. Precompute what is stable and enumerable; compute live what is arbitrary.

Interview signal by level

Next: routing between segments.