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 Onsite rounds at Pinterest.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Pinterest during technical interviews.

Determine Pin Connections Through Common Boards

Company: Pinterest

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Scenario Pinterest boards contain many pins; need to infer relationships between pins. ##### Question Given the membership lists of all boards, write a function that returns whether two pins are connected through any sequence of common boards. Follow-up: return the minimum number of boards required to connect the two pins. ##### Hints Model boards/pins as a bipartite graph; BFS from one pin over boards to the other.

Quick Answer: This question evaluates graph modeling and connectivity concepts, including representing boards and pins as relationships and reasoning about reachability and minimal connection paths.

Part 1: Determine Whether Two Pins Are Connected

You are given `boards`, where each board is a list of pin IDs. Two pins are considered connected if you can start at `start_pin` and repeatedly do the following: move from a pin to any board that contains it, then move from that board to any pin on that same board. Return whether `end_pin` is reachable. Equivalently, you are checking whether there exists any chain of overlapping boards that connects the two pins. A pin is always considered connected to itself, even if it does not appear in any board.

Constraints

0 <= len(boards) <= 10^4
0 <= sum(len(board) for board in boards) <= 2 * 10^5
Pin IDs are integers
Boards may contain duplicate pin IDs; duplicates should not change the answer

Examples

Input: ([[1, 2, 3], [3, 4], [6, 7]], 1, 4)

Expected Output: True

Explanation: Pin 1 shares board 0 with pin 3, and pin 3 shares board 1 with pin 4.

Input: ([[1, 2], [3, 4], [5]], 1, 5)

Expected Output: False

Explanation: There is no chain of boards connecting pin 1 to pin 5.

Input: ([], 8, 9)

Expected Output: False

Explanation: With no boards, different pins cannot be connected.

Input: ([], 8, 8)

Expected Output: True

Explanation: A pin is considered connected to itself by a path of length 0.

Input: ([[10], [11, 12]], 10, 12)

Expected Output: False

Explanation: Pin 10 is isolated on its own board and does not connect to pin 12.

Hints

Think of pins and boards as a bipartite graph: pin -> board -> pin.
Use BFS or DFS, but make sure to mark both visited pins and visited boards so you do not reprocess the same board many times.

Part 2: Minimum Number of Boards Needed to Connect Two Pins

You are given `boards`, where each board is a list of pin IDs. You may move from a pin to any board that contains it, then from that board to any pin on the same board. Return the minimum number of boards used in any valid connection from `start_pin` to `end_pin`. If both pins are on the same board, the answer is 1. If `start_pin == end_pin`, the answer is 0. If no connection exists, return -1.

Constraints

0 <= len(boards) <= 10^4
0 <= sum(len(board) for board in boards) <= 2 * 10^5
Pin IDs are integers
Boards may contain duplicate pin IDs; duplicates should not change the answer

Examples

Input: ([[1, 2, 3], [3, 4], [4, 5]], 1, 5)

Expected Output: 3

Explanation: One shortest path is 1 -> board[0] -> 3 -> board[1] -> 4 -> board[2] -> 5, which uses 3 boards.

Input: ([[1, 2], [2, 3]], 1, 2)

Expected Output: 1

Explanation: Pins 1 and 2 already share the first board.

Input: ([[1, 9], [9, 2], [1, 3], [3, 4], [4, 2]], 1, 2)

Expected Output: 2

Explanation: The shortest route is 1 -> board[0] -> 9 -> board[1] -> 2, which uses 2 boards.

Input: ([[1, 2], [3, 4]], 1, 4)

Expected Output: -1

Explanation: There is no chain of overlapping boards connecting the two pins.

Input: ([], 7, 7)

Expected Output: 0

Explanation: A pin connects to itself without using any board.

Hints

Run BFS starting from the start pin, and treat traversing one board as adding 1 to the distance.
If you mark a board as visited the first time you process it, you avoid counting the same board multiple times and keep the search efficient.

Quick Overview

This question evaluates graph modeling and connectivity concepts, including representing boards and pins as relationships and reasoning about reachability and minimal connection paths.