Route Planner
Weighted routing across a transport network with transfers, graph search with a bug → feature → scale arc.
Problem
A transport network has stations and directed, weighted connections (from → to with a cost). The starter code has a bug.
Phase 1 — Fix the bug
Edges are treated as undirected: the planner happily travels against the direction of a one-way connection. Edges must only be traversable from from to to.
Phase 2 — Feature
Implement lowestCost(from, to): the minimum-cost path, where each station belongs to a line, and changing lines costs a penalty added to the total. Return the path and its cost, or null if unreachable.
Phase 3 — Scale
The network grows to city size. Your chosen search must scale with a priority-queue-based approach.
What interviewers watch
Direction handling first, then the Dijkstra-vs-BFS call (edges are weighted), then how the transfer penalty is encoded — usually as an edge or a state, never a post-hoc patch.