Katkat
Back

Collect Pins from Reachable Boards

PinterestSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Implement a breadth-first graph traversal over a collection of boards to collect unique pins in discovery order, handling cycles, shared children, and invalid references.

Collect Pins from Reachable Boards

In Pinterest's architecture, users organize content into boards. A board can contain pins and can also link to other boards (for example, related boards or sections). These links form a directed graph that may contain cycles and shared subgraphs.

You are given a collection of boards represented as a mapping from a board ID to its record, and a start_board_id. Each board record contains:

  • "pins": a list of pin IDs (list[str]) belonging to this board.
  • "children": a list of board IDs (list[str]) that this board links to.

Your task is to traverse the graph starting from start_board_id using a deterministic breadth-first search (BFS) and return a list of pin IDs in the order they are first discovered.

Requirements

  1. Validation:
    • start_board_id must be present in boards.
    • Every board ID referenced in any board's "children" list must be present in boards.
    • If any ID is missing or invalid, raise a ValueError.
  2. Deterministic Traversal:
    • Use standard FIFO queue order starting from start_board_id.
    • For each visited board, process its pins in the given list order before exploring its children.
    • Enqueue child boards in the exact order specified in the current board's "children" list.
  3. Deduplication:
    • Boards: A board should only be visited once. Handle cycles and shared children by tracking visited boards upon enqueueing.
    • Pins: A pin may appear on multiple boards. Each pin must be added to the output list only the first time it is encountered during traversal.

Function Signature

def collect_pins(boards: dict[str, dict[str, list[str]]], start_board_id: str) -> list[str]:
    pass

Examples

Example 1:

boards = {
    "board_1": {"pins": ["pin_a", "pin_b"], "children": ["board_2", "board_3"]},
    "board_2": {"pins": ["pin_b", "pin_c"], "children": ["board_4"]},
    "board_3": {"pins": ["pin_c", "pin_d"], "children": []},
    "board_4": {"pins": ["pin_e"], "children": ["board_1"]}  # Cycle back to board_1
}
start_board_id = "board_1"

# Output: ["pin_a", "pin_b", "pin_c", "pin_d", "pin_e"]

Explanation: board_1 yields pin_a, pin_b. Next in BFS is board_2, yielding pin_c (pin_b already seen). Next is board_3, yielding pin_d (pin_c already seen). Next is board_4, yielding pin_e. board_4 references board_1, which was already visited, terminating the traversal.

Example 2:

boards = {
    "board_1": {"pins": ["pin_x"], "children": ["board_missing"]}
}
start_board_id = "board_1"

# Raises ValueError because "board_missing" does not exist in boards.

Constraints

  • 1 <= len(boards) <= 20,000
  • Total number of pins across all boards <= 100,000
  • Total number of child links across all boards <= 100,000
  • All board and pin IDs are non-empty strings.

Edge Cases to Consider

  • The graph contains self-loops or directed cycles.
  • Two or more boards link to the same shared child board (DAG diamond shape).
  • A board contains empty pins or children lists.
  • start_board_id is missing from boards.

Hints

Hint 1

Validate all board references up front before beginning traversal, or verify them during the BFS check.

Hint 2

Maintain two separate hash sets: one for visited board IDs (to prevent infinite loops in cyclic graphs) and one for emitted pin IDs (to avoid duplicate pins).

Hint 3

Mark child boards as visited immediately when pushing them onto the BFS queue, rather than when popping them, to prevent duplicate enqueues when multiple boards point to the same child.

Follow-up questions

  • How would you modify this solution if the graph had a max depth limit (e.g., only collect pins within 3 hops of the start board)?
  • If the board graph is too large to fit in memory on a single machine, how would you distribute this BFS across multiple workers?
  • How would you handle priority/ranking if pins had timestamps or engagement scores and needed to be yielded in top-k order instead of BFS discovery order?