Skip to main content

21. Clone Graph

mediumAsked at CircleCI

Deep-clone a connected undirected graph, testing your ability to handle shared references — an important skill when CircleCI forks pipeline configurations for parallel builds.

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

Problem

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node has a val and a list of neighbors.

Constraints

  • Nodes in [0, 100]
  • Node values are unique and in [1, 100]
  • No repeated edges, no self-loops

Examples

Example 1

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

Example 2

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

Approaches

1. DFS with visited map

Recursively clone each node, using a map from original to clone to avoid cycles.

Time
O(V+E)
Space
O(V)
function cloneGraph(node) {
  if (!node) return null;
  const map = new Map();
  function dfs(n) {
    if (map.has(n)) return map.get(n);
    const clone = { val: n.val, neighbors: [] };
    map.set(n, clone);
    for (const nb of n.neighbors) clone.neighbors.push(dfs(nb));
    return clone;
  }
  return dfs(node);
}

Tradeoff:

2. BFS with visited map

Use a queue for BFS traversal, creating clones eagerly; avoids deep call stacks for large graphs which is important for complex pipeline DAGs.

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

Tradeoff:

CircleCI-specific tips

CircleCI may extend this to cloning a DAG with weighted edges representing job dependencies — discuss how the visited map handles cycles versus DAGs differently.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →