Clone a graph (cycle-safe)

Expected question

"Given a reference to a node in a connected undirected graph, return a deep copy. The graph may contain cycles."

Variant forms

"Clone an undirected graph — handle cycles."
"Clone a directed graph with possible cycles."
"BFS vs DFS for cloning — which and why?"
"What if node values are not unique?"
"Clone only the connected component reachable from the start."
"Serialize/deserialize the graph instead of cloning in memory."
"How do you prove you didn't share neighbor references with the original?"
"Extend to cloning with per-node metadata maps."

The question, as it might actually be asked

Given a reference to a node in a connected undirected graph where each node has val and neighbors, return a deep copy. Graph may contain cycles.

How you'd talk while coding

I'd ask undirected vs directed, connected vs multi-component, whether vals are unique (don't key the map on val), and confirm we can't mutate the original. Brute recursion without memo loops forever on a cycle — that's the scar. Correct is old→new map, BFS or DFS, wire neighbors through the map. I'd prefer iterative BFS for stack safety on large graphs. Tests: two nodes pointing at each other; single node; prove cloned neighbor identity ≠ original. Staff+ stop line: "Map by object identity, not val. Multi-component needs an entrypoint list. I won't pitch a distributed graph DB."

Where this actually gets asked

Graph medium with cycles. Staff+ signal: visited map, clear BFS vs DFS, undirected vs directed API.

Problem

Given a reference to a node in a connected undirected graph where each node has val and neighbors, return a deep copy. Graph may contain cycles.

Clarifying questions you should ask first

Undirected? Connected? Disconnected components?
Node vals unique? (often yes — don't assume for identity)
Mutate original allowed? (no)

Approach ladder

Step	Idea
Brute	Recurse without memo — infinite loop on cycles
Correct	HashMap old→new; DFS or BFS
Staff+	Iterative BFS for stack safety; multi-component entrypoint

Reference solution (Python)

from __future__ import annotations
from collections import deque
from dataclasses import dataclass, field

@dataclass
class Node:
    val: int
    neighbors: list["Node"] = field(default_factory=list)

def clone_graph(node: Node | None) -> Node | None:
    if node is None:
        return None
    mapping: dict[Node, Node] = {node: Node(node.val)}
    q: deque[Node] = deque([node])
    while q:
        cur = q.popleft()
        for nb in cur.neighbors:
            if nb not in mapping:
                mapping[nb] = Node(nb.val)
                q.append(nb)
            mapping[cur].neighbors.append(mapping[nb])
    return mapping[node]

Complexity: O(V+E) time and space.

Verbal tests to narrate

Two nodes pointing at each other
Single node self-loop (if allowed) / no neighbors
Verify cloned neighbor identity ≠ original

Staff+ deep dive

Topic	Talking point
Why map by object identity	Vals may collide in variants
DFS recursion depth	Prefer BFS/iterative for large graphs
Serialization	Clone vs serialize/deserialize trade-off

What not to discuss

Distributed graph DBs
Ignoring cycles

What's expected at each level

Mid-level: DFS clone; may miss cycles.
Senior: Memoized BFS/DFS + tests.
Staff+: Iterative, identity map, component discussion.
Principal: Relates to real object-graph copy / config snapshot systems.

Follow-up questions to expect

"What breaks naive recursion?" — Cycles, and diamond shared neighbors without a memo map.
"BFS vs DFS?" — Either works with original→clone. I'd mention stack limits and pick iterative BFS for large graphs.
"Mutation during clone?" — Usually out of scope; I'd state the assumption.
"When to stop?" — Cycle-safe clone + tests. Don't invent a graph service.

00-staff-plus-coding-bar.md