Determine Pin Connections Through Common Boards

Q: Determine Pin Connections Through Common Boards

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

Q: 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.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Pinterest.

Q: What role is this question designed for?

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

Question

##### 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.

PracHub · Accepted Answer

def solution(boards, start_pin, end_pin):
    from collections import defaultdict, deque

if start_pin == end_pin:
        return True

normalized_boards = [set(board) for board in boards]
    pin_to_boards = defaultdict(list)

for board_index, board in enumerate(normalized_boards):
        for pin in board:
            pin_to_boards[pin].append(board_index)

queue = deque([start_pin])
    visited_pins = {start_pin}
    visited_boards = set()

while queue:
        pin = queue.popleft()

for board_index in pin_to_boards.get(pin, []):
            if board_index in visited_boards:
                continue

visited_boards.add(board_index)

for next_pin in normalized_boards[board_index]:
                if next_pin == end_pin:
                    return True
                if next_pin not in visited_pins:
                    visited_pins.add(next_pin)
                    queue.append(next_pin)

return False

def solution(boards, start_pin, end_pin):
    from collections import defaultdict, deque

if start_pin == end_pin:
        return 0

normalized_boards = [set(board) for board in boards]
    pin_to_boards = defaultdict(list)

for board_index, board in enumerate(normalized_boards):
        for pin in board:
            pin_to_boards[pin].append(board_index)

queue = deque([(start_pin, 0)])
    visited_pins = {start_pin}
    visited_boards = set()

while queue:
        pin, boards_used = queue.popleft()

for board_index in pin_to_boards.get(pin, []):
            if board_index in visited_boards:
                continue

visited_boards.add(board_index)
            next_count = boards_used + 1

if end_pin in normalized_boards[board_index]:
                return next_count

for next_pin in normalized_boards[board_index]:
                if next_pin not in visited_pins:
                    visited_pins.add(next_pin)
                    queue.append((next_pin, next_count))

return -1

Quick Overview

Solution

Hints

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

Constraints

Examples

Solution

Hints

Quick Overview