How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Pinterest.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Pinterest during technical interviews.

Find minimum shuttle transfers | Pinterest Coding Question

Quick Overview

Find minimum shuttle transfers evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Find minimum shuttle transfers

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

You are given a collection of shuttle loops, each represented by a list of stop IDs that the loop visits in perpetuity. You may board a shuttle at any stop it serves and remain on it until any later stop on the same loop. Transferring from one shuttle loop to another counts as boarding a new shuttle. Given a source stop s and a target stop t, determine the minimum number of shuttles you must board to travel from s to t; return -1 if it is impossible. Describe the data structures you would use, outline the algorithm step by step, and analyze time and space complexity for inputs with up to 100,000 total stops across all loops. Discuss edge cases such as s == t, isolated loops, and multiple loops sharing the same stop. Follow-ups: how would you output an actual sequence of shuttles taken; how would you handle weighted transfer penalties or restricted operating hours; how can you reduce memory and avoid building an explicit route-to-route graph when the number of loops is very large?

Quick Answer: Find minimum shuttle transfers evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given a collection of shuttle loops, each represented by a list of stop IDs that the loop visits in perpetuity. You may board a shuttle at any stop it serves and ride it to any later stop on the same loop. Transferring from one shuttle loop to another counts as boarding a new shuttle. Given `routes` (a list of loops), a source stop `source`, and a target stop `target`, return the minimum number of shuttles you must board to travel from `source` to `target`, or `-1` if it is impossible. Note that being at `source` initially costs no boardings: if `source == target`, the answer is `0`. Example 1: Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6 Output: 2 Explanation: Board loop 0 at stop 1 and ride to stop 7, then transfer to loop 1 and ride to stop 6. Example 2: Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 Output: -1 Explanation: No sequence of loops connects stop 15 to stop 12. Constraints: - 1 <= routes.length <= 500 - 1 <= sum(routes[i].length) <= 100000 - All stop IDs within a single loop are distinct. - 0 <= source, target, stop IDs.

Constraints

1 <= routes.length <= 500
1 <= sum(routes[i].length) <= 100000
All stop IDs within a single loop are distinct.
0 <= source, target, and all stop IDs.

Examples

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6

Expected Output: 2

Explanation: Board loop 0 at stop 1, ride to stop 7, transfer to loop 1, ride to stop 6. Two boardings.

Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12

Expected Output: -1

Explanation: Loops containing 15 ({4,5,15} and {15,19}) share no stop with any loop reaching 12, so the target is unreachable.

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 1

Expected Output: 0

Explanation: Source equals target, so no shuttle needs to be boarded.

Input: routes = [[1,2,3]], source = 1, target = 3

Expected Output: 1

Explanation: A single loop serves both stops; one boarding suffices.

Input: routes = [[1,2,3]], source = 1, target = 5

Expected Output: -1

Explanation: Stop 5 is not served by any loop, so it is unreachable.

Input: routes = [[1,7],[3,5]], source = 5, target = 5

Expected Output: 0

Explanation: Source equals target even though the loops are isolated; the answer is 0.

Input: routes = [[1,2],[2,3],[3,4],[4,5]], source = 1, target = 5

Expected Output: 4

Explanation: Each consecutive loop overlaps the next at one stop, forcing four chained boardings: loop0->loop1->loop2->loop3.

Input: routes = [[0,1,6,16,22,23],[14,15,24,32],[4,10,12,20,24,28,33],[1,10,11,19,27,33],[11,23,25,28],[22,23,38],[0,7,8,14,24,30,32]], source = 7, target = 23

Expected Output: 2

Explanation: Board loop 6 (contains 7) to reach stop 0, then board loop 0 (shares stop 0) which serves stop 23. Two boardings.

Hints

Model this as a shortest-path problem where the 'cost' is the number of shuttles boarded, not the number of stops traveled. A plain BFS over stops counts stops, which is the wrong metric.
Pre-compute a map from each stop ID to the list of loop indices that serve it. This lets you jump from a stop to every loop reachable in one boarding.
Run a level-order BFS starting from the source stop. Each BFS level corresponds to one additional shuttle. When you visit a stop, expand every not-yet-used loop through that stop and enqueue all of that loop's stops.
Mark whole loops as visited (not just stops) so you never re-expand the same loop. Handle source == target up front as the answer 0.

Quick Overview