Skip to main content

133. Clone Graph

mediumAsked at Cisco

Clone Graph at Cisco is a graph-traversal + hash-map double check. The interviewer wants to see whether you reach for a 'visited → clone' map immediately and whether you can handle the cycle-creating self-reference without an infinite recursion.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Reported by Cisco SDE-I and SDE-II candidates as a 30-minute coding round.
  • Reddit r/cscareerquestions (2025-10)— Multiple Cisco interview write-ups list Clone Graph as a recurring problem.

Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a value (int) and a list of its neighbors (List[Node]).

Constraints

  • The number of nodes in the graph is in the range [0, 100].
  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • There are no repeated edges and no self-loops in the graph.
  • The graph is connected and all nodes can be visited starting from the given node.

Examples

Example 1

Input
adjList = [[2,4],[1,3],[2,4],[1,3]]
Output
[[2,4],[1,3],[2,4],[1,3]]

Explanation: Four nodes forming a cycle 1-2-3-4-1. The clone preserves the same shape.

Example 2

Input
adjList = [[]]
Output
[[]]

Explanation: Single node with no edges.

Approaches

1. Brute-force: two-pass copy

First pass — walk the graph and create a clone of every node, mapping original → clone. Second pass — walk again and wire the neighbor lists on the clones.

Time
O(V + E)
Space
O(V)
function cloneGraphBrute(node) {
  if (!node) return null;
  const map = new Map();
  function discover(orig) {
    if (map.has(orig)) return;
    map.set(orig, new Node(orig.val));
    for (const nb of orig.neighbors) discover(nb);
  }
  discover(node);
  for (const [orig, clone] of map) {
    clone.neighbors = orig.neighbors.map(nb => map.get(nb));
  }
  return map.get(node);
}

Tradeoff: Two passes are easier to reason about — discovery is purely about creating empty clones, wiring is purely about edges. Slightly more code than the one-pass DFS but clearer for the interviewer if you stumble.

2. One-pass DFS with memoization (optimal)

Walk the graph once. For each original node, if you've seen it before, return the cached clone; otherwise create the clone, store it BEFORE recursing into neighbors (this breaks cycles), then map the neighbors.

Time
O(V + E)
Space
O(V)
function cloneGraph(node) {
  if (!node) return null;
  const map = new Map();
  function dfs(orig) {
    if (map.has(orig)) return map.get(orig);
    const clone = new Node(orig.val);
    map.set(orig, clone);
    clone.neighbors = orig.neighbors.map(nb => dfs(nb));
    return clone;
  }
  return dfs(node);
}

Tradeoff: The crucial line is `map.set(orig, clone)` BEFORE the recursive call — that's what prevents the recursion from looping forever on cyclic graphs. Shorter than the two-pass version and shows you understand the memoization pattern.

3. BFS with hash map

Iterative variant — queue holds original nodes; clone is created on enqueue and wiring happens on dequeue.

Time
O(V + E)
Space
O(V)
function cloneGraphBFS(node) {
  if (!node) return null;
  const map = new Map();
  map.set(node, new Node(node.val));
  const queue = [node];
  while (queue.length) {
    const orig = queue.shift();
    for (const nb of orig.neighbors) {
      if (!map.has(nb)) {
        map.set(nb, new Node(nb.val));
        queue.push(nb);
      }
      map.get(orig).neighbors.push(map.get(nb));
    }
  }
  return map.get(node);
}

Tradeoff: Avoids deep recursion on long graphs, useful when the call stack would blow up. Cisco interviewers respect candidates who name 'iterative BFS to bound the stack.'

Cisco-specific tips

Cisco interviewers are listening for one specific phrase: 'I need a hash map from original to clone so I don't recurse forever on cycles.' Say that BEFORE you write any code. Then they let you pick DFS or BFS. If they ask 'why does this terminate?', point at the line that inserts into the map BEFORE the recursive call — that's the cycle-breaker.

Common mistakes

  • Recursing into neighbors BEFORE inserting the current node into the map — infinite recursion on any cyclic graph.
  • Cloning the val but not the neighbor list — a deep copy needs both.
  • Returning the wrong start clone — must return `map.get(node)`, the clone of the input, not just any node.

Follow-up questions

An interviewer at Cisco may pivot to one of these next:

  • What if the graph is a DAG instead of undirected? (Same algorithm — only the edge semantics differ.)
  • What if nodes also carry a `random` pointer like LC 138? (Same memoization technique; clone all nodes first, then wire random.)
  • Memory-constrained clone — clone in-place by inserting clones into the original neighbor lists. (Used in LC 138 too.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does inserting into the map BEFORE recursing prevent infinite recursion?

The recursive call asks 'do you have a clone of this node?' The map says 'yes' (the empty clone you just inserted), so the recursion returns instead of descending again. The empty clone gets its neighbors filled in by the OUTER call once the inner recursion returns.

Is BFS or DFS expected at Cisco?

Either passes the rubric on correctness. DFS is the shorter code, BFS is the answer to 'what if the graph is so deep you'd overflow the stack?' Lead with DFS; offer BFS as the production-grade variant.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Clone Graph and other Cisco interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →