How should I practice Fewest Buses with the Full Route?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Fewest Buses with the Full Route associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Fewest Buses with the Full Route

Microsoft● HardNEW GRADONSITE INTERVIEW

Problem statement

Source note: The interviewer asked: "You are given source, destination and a list routes. Each routes[i] is all the stops one bus route passes. Two routes that pass the same stop allow a transfer. Find the fewest buses needed to get from source to destination." The follow-up asked for the full route, with the transfer stops.

The report does not say which plan to return when several tie, or how to show a plan. Here the answer is a list of rows: the bus count first, then one row per bus with the route, where you board, and where you get off. Ties go to the smallest list of routes, and a transfer uses the smallest shared stop. A bus connects any two of its stops in either direction. The size limits are practice choices too. The other follow-ups, why BFS gives the fewest buses and how to state the complexity, are in the editorial and are not judged.

The judged task matches the report at about 85%.

You are given two stops, source and destination, and a list routes. Each routes[i] lists all the stops one bus route passes. A bus connects any two stops on its route, in either direction. Two routes that pass the same stop let you transfer there. Each route you ride counts as one bus.

Find the fewest buses from source to destination, and return the full plan as a list of rows:

The first row holds one number: the fewest buses. It is 0 when source equals destination, and -1 when destination cannot be reached.
When you ride at least one bus, one more row follows for each bus, in riding order: [route, boardStop, getOffStop], where route is the index in routes. The first boardStop is source, the last getOffStop is destination, and each other getOffStop is where you transfer.

Several plans may use the fewest buses. Return the one chosen by these rules:

Compare the plans' lists of route indexes from left to right, and take the smallest list.
Between two routes in a row, transfer at the smallest stop they share.

Function

fewestBusesWithRoute(source: int, destination: int, routes: int[][]) → int[][]

Examples

Example 1

source = 10destination = 70routes = [[10,20,30],[25,30,40,50],[50,60,70],[20,80]]return = [[3],[0,10,30],[1,30,50],[2,50,70]]

Stop 10 is only on route 0, and stop 70 is only on route 2. Those two routes share no stop, so at least three buses are needed.

Ride route 0 from 10 to 30, the only stop it shares with route 1. Ride route 1 from 30 to 50, the only stop it shares with route 2. Ride route 2 from 50 to 70. Route 3 is not needed.

Example 2

source = 10destination = 70routes = [[10,20,30],[40,50],[60,70]]return = [[-1]]

Stop 10 is only on route 0, stop 70 is only on route 2, and no two routes share a stop. The destination cannot be reached, so the only row is [-1].

Example 3

source = 1destination = 9routes = [[1,4,2],[1,3],[9,4,2],[3,9]]return = [[2],[0,1,2],[2,2,9]]

No single route has both 1 and 9. Two plans use two buses: routes [0, 2] and routes [1, 3]. The list [0, 2] is smaller.

Routes 0 and 2 share stops 4 and 2, so the transfer is at the smaller stop, 2. Ride route 0 from 1 to 2, then route 2 from 2 to 9.

Constraints

1 <= routes.length <= 500
1 <= routes[i].length <= 5000
The total number of stops across all routes is at most 5000.
0 <= routes[i][j] <= 10^6
0 <= source <= 10^6
0 <= destination <= 10^6
All stops in one route are different.