Fewest Board Switches to Travel Between Two Pins via Shared Boards
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A content platform groups pins into themed boards. Each board has a name and a list of pins, and the same pin can appear on several boards. For example, a pin for one city can sit on both a travel board and a food board.
You start on the pin `start` and want to reach the pin `end`. While you stand on a pin, you may move to any other pin on any board that contains your current pin. The only way to get from one board to another is through a pin that belongs to both.
The score of a trip is the number of times you switch boards. Return the minimum score from `start` to `end`.
### Function Signature
```python
def min_board_switches(boards: dict[str, list[str]], start: str, end: str) -> int:
```
### Rules
- A route is a sequence of boards `b_1, b_2, ..., b_m` with `m >= 1` such that `start` is on `b_1`, `end` is on `b_m`, and every two consecutive boards share at least one pin. The score of the route is `m - 1`. Return the minimum score over all routes.
- If `start == end`, return `0`.
- If `start` and `end` are both on some common board, return `0`, because no switch is needed.
- If no route exists, return `0`. This includes the case where `start` or `end` is on no board at all. A result of `0` therefore covers both "no switch needed" and "unreachable".
- The answer is a single integer, so it is unique. Board names and pin ids are compared as exact strings.
### Constraints
- `1 <= len(boards) <= 10^4`
- Each board's list has between 1 and `10^4` pins, and a pin appears at most once in any single board's list.
- The total number of pin entries across all boards is at most `2 * 10^5`.
- Board names, pin ids, `start` and `end` are non-empty strings of at most 30 characters, drawn from lowercase English letters, digits and underscores.
- `start` and `end` do not have to appear on any board.
- The returned value is between `0` and `len(boards) - 1`.
### Examples
**Example 1**
```text
boards = {
"travel": ["california", "new_york", "washington"],
"food": ["new_york", "sichuan_cuisine", "cantonese_cuisine"],
"sports": ["tennis", "basketball", "california"],
}
start = "california"
end = "cantonese_cuisine"
Output: 1
```
`california` is on `travel` and `sports`, and `cantonese_cuisine` is only on `food`. No single board holds both pins. `travel` and `food` share `new_york`, so the route `travel -> food` needs one switch.
**Example 2**
```text
boards = {"a": ["p1", "p2"], "b": ["p2", "p3"], "c": ["p3", "p4"], "d": ["p5", "p6"]}
start = "p1"
end = "p4"
Output: 2
```
The best route is `a -> b -> c`. It switches boards at `p2` and again at `p3`.
**Example 3**
```text
boards = {"a": ["p1", "p2"], "b": ["p2", "p3"], "c": ["p3", "p4"], "d": ["p5", "p6"]}
start = "p1"
end = "p6"
Output: 0
```
Board `d` shares no pin with `a`, `b` or `c`, so `p6` cannot be reached from `p1`.
Overview: Given boards that each hold a list of pins, where one pin can appear on several boards, compute the fewest board switches needed to travel from a start pin to an end pin. Tests graph modeling of shared memberships, minimum-step search, and careful handling of same-board and unreachable cases.