Daily bit(e) of C++ | Bus routes
Daily bit(e) of C++ #156, Common interview problem: Bus routes
Today we will look at a common interview problem: Bus routes.
Given a list of bus routes, where route[i] = {b1,b2,b3} means that bus i stops at stops b1, b2 and b3, determine the smallest number of buses you need to reach the target bus stop starting at the source.
Return -1 if the target is unreachable.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/ThToveWP8.
Solution
We could approach this problem by doing a simple breadth-first search across the bus stops; however, we have two problems. First, we don’t have a convenient way to determine which bus stops we can reach. And while we could construct a data structure for that, our second problem is a bit more fundamental. Breadth-first search scales with the number of edges in the graph; therefore, if we work with buses that stop at many stops, the number of states would grow quickly.
Therefore, let’s think about buses instead of bus stops. We will need a data structure to map the “connections”, i.e. busses that we can change to on each line. However, once we have it, our breadth-first search will scale based on the number of bus lines.
To build our connections data structure, we can sort each line and look for overlaps between each two bus lines. This will take us O(s*log(s)) for the sorting and then O(b*b*s) for the construction (where s is the number of stops and b is the number of buses).
The breadth-first search will take O(b*b) (b nodes, each with b-1 edges).
