Minimum Transfers Between Stops | Dataford Interview Questions

Your question is Minimum Transfers Between Stops. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Snap operates shuttle routes between Snap offices and event venues. Given the stops served by each shuttle route, a starting stop, and a destination stop, return the minimum number of transfers needed to reach the destination. A passenger may board any route serving the current stop and may ride it to any of its stops. Return -1 if the destination is unreachable.

A direct ride requires 0 transfers. If reaching the destination requires boarding two different routes, the answer is 1. If start_stop == end_stop, return 0.

Formal Specification

Implement min_transfers(routes, start_stop, end_stop).

routes is a list of routes, where routes[i] is a list of integer stop IDs served by route i.
start_stop and end_stop are integer stop IDs.
Return an integer representing the minimum number of route changes, or -1 when no route sequence can connect the stops.
A route may contain many stops, and stops can be shared by multiple routes.

Constraints

1 <= len(routes) <= 10^5
The total number of stops across all routes is at most 2 * 10^5
0 <= start_stop, end_stop <= 10^9
Each route contains no duplicate stop IDs
A stop can be served by multiple routes

Function Signature

def min_transfers(routes, start_stop, end_stop):