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.

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.

Hints

  1. Think of pins and boards as a bipartite graph: pin -> board -> pin.
  2. 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.

Hints

  1. Run BFS starting from the start pin, and treat traversing one board as adding 1 to the distance.
  2. 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.

Loading coding console...