Requirements and the Two Challenges

In one line: the two challenges named here are the chapter. Scalability is solved by segmentation, ETA accuracy by live data — and everything in the remaining lessons serves one or the other.

Requirements

Functional:

Non-functional:

Note: we assume road data is provided by external sources. Road networks are modeled as a graph where intersections are vertices and roads are weighted edges.

Accuracy as a non-functional requirement is unusual — and it cannot be tested the way the others can

Availability, scalability, and latency are all measurable properties of the system. You can observe uptime, throughput, and response time directly.

Accuracy is different. "The predicted ETA must closely match the actual travel time" can only be evaluated after the journey happens — you compare a prediction against an outcome that arrives an hour later.

That has three consequences:

It requires a feedback loop. You cannot know whether your ETA model is good without collecting actual arrival times, which is exactly why Lesson 9's live location ingestion exists. The system that serves predictions must also measure them.

It degrades silently. A latency regression shows up on a dashboard immediately. An accuracy regression looks like nothing — the system responds fast and returns a plausible number that happens to be wrong.

It depends on the world, not on you. Construction, weather, and an accident on the highway all change the right answer without anything in your system changing.

This is the same shape as ranking quality in the Quora and YouTube chapters — a requirement that needs a model and continuous evaluation rather than an implementation. Recognizing it as that class of problem is the useful move.

The graph assumption is the most consequential line in the lesson

"Road networks are modeled as a graph where intersections are vertices and roads are weighted edges."

That single modelling decision determines the whole design:

• Routing becomes shortest-path, so Dijkstra and A* are the relevant algorithms.
• Edge weights carry the semantics — distance, time, or traffic — which is what lets one graph answer "shortest" and "fastest" differently, and what makes Lesson 9's traffic updates a matter of changing weights rather than restructuring anything.
• A graph database becomes the natural store, which is the building-block choice Lesson 1 flagged.

Also note what is scoped out: "we assume road data is provided by external sources." Building the map — surveying roads, reconciling sources, handling one-way streets and turn restrictions — is an enormous problem the design deliberately does not take on.

That is a good scoping move to imitate. State the input you are assuming, because otherwise an interviewer may take the design somewhere you did not intend.

Challenge 1: scalability

The road graph contains billions of nodes and edges distributed across multiple countries. Naïve shortest-path algorithms such as Dijkstra's are not sufficient to serve millions of concurrent queries at this scale without preprocessing or optimization. The system requires preprocessing and query-acceleration techniques to handle high query throughput while maintaining low latency.

Dijkstra on a global graph is the wrong complexity class — and no amount of hardware fixes it

Dijkstra's algorithm visits vertices in order of distance from the design, so on a graph with billions of vertices a long route could touch a large fraction of them.

Two problems, and the second is the fatal one:

A single query is too slow. Even at nanoseconds per vertex, exploring hundreds of millions of them blows a 2–3 second budget.

The graph does not fit in memory. Lesson 12 states this directly — the global graph "was too large to fit in memory, rendering query processing impossible." Once you are hitting disk during traversal, per-vertex cost rises by orders of magnitude.

And you cannot solve it by adding machines, because the algorithm is inherently sequential — Dijkstra explores outward from one source, and there is no obvious way to split that across servers without splitting the graph.

Which is exactly the answer: split the graph. Lessons 4 through 7 partition the world into segments small enough to hold in memory, precompute paths inside them, and stitch results together.

The transferable point: when the bottleneck is algorithmic complexity, the fix is preprocessing, not provisioning. You trade offline computation and storage for online latency.

The two challenges pull against each other, which is what makes the chapter interesting: precomputation is what makes scale tractable, and changing edge weights is exactly what invalidates precomputation.

Challenge 2: ETA computation

Travel time depends on dynamic factors like traffic density, road conditions, construction, and other such factors, not just distance and speed. Accurately quantifying these variables to predict arrival times is a significant design challenge.

Distance is static and travel time is not — that is the whole difficulty

The distinction is worth stating precisely, because it explains why the design needs two very different mechanisms.

Distance is a property of the road network. It changes when roads are built, which is rare. Precompute it once and it stays correct — which is exactly what Lesson 5 does.

Travel time is a property of the road network plus the current state of the world. The same five-mile stretch takes eight minutes at 3 a.m. and thirty-five at 8 a.m. Nothing about the road changed.

So the system needs both:

• Static precomputation for the graph structure and distances (Lessons 5–7).
• A live data pipeline continuously updating edge weights from observed traffic (Lessons 9 and 11).

That split is why Lesson 11 has a graph preprocessing service that recomputes paths after weights change — the precomputation is not a one-off, it is a continuously refreshed cache whose inputs keep moving.

It also explains Lesson 11's dual-data refinement: transitory conditions like a red light should not trigger a graph rewrite, while persistent congestion should.

Two challenges, two completely different kinds of solution

Worth holding these apart, because interviews often conflate them:

Neither is a provisioning problem, which is what makes this chapter different from the previous three. The first is solved by doing work in advance; the second by observing reality continuously.

Interview signal by level

Next: sizing the system.