Clone Graph

Clone Graph

What is this problem about?

The Clone Graph interview question asks you to create a deep copy of a connected, undirected graph. In a deep copy, you aren't just copying the pointers or references to existing nodes; instead, you must create entirely new node instances such that the new graph's structure perfectly mirrors the original. Each node in this graph contains a value and a list of its neighbors. Since the graph is undirected and can contain cycles, you must ensure that your cloning process doesn't fall into an infinite loop or create redundant copies of the same node.

Why is this asked in interviews?

Companies like Meta, Google, and Amazon frequently use the Clone Graph coding problem to assess a candidate's understanding of graph traversal and memory management. It tests your ability to handle complex data structures, specifically those that involve pointers and cycles. Interviewers want to see if you can distinguish between a "shallow copy" (copying references) and a "deep copy" (creating new objects) and if you can use auxiliary data structures like hash maps to keep track of visited nodes.

Algorithmic pattern used

The most common Graph interview pattern for this problem is using a traversal algorithm—either Breadth-First Search (BFS) or Depth-First Search (DFS)—combined with a Hash Table. The hash table (or dictionary) is crucial because it maps original nodes to their corresponding clones. This prevents re-cloning nodes and allows you to correctly wire up neighbors even when cycles exist.

Example explanation

Imagine a simple graph with three nodes: A, B, and C.

• A is connected to B and C.
• B is connected to A and C.
• C is connected to A and B.

When you start at node A, you create a clone A'. You then look at A's neighbors (B and C). You create B' and C', and add them to A''s neighbor list. When you move to B', you see it has a neighbor A. Instead of creating a new clone for A, you look up the map, find A', and simply link B' to A'. This ensures the identity of the nodes is preserved in the clone.

Common mistakes candidates make

• Shallow Copying: Simply copying the list of neighbors without creating new node instances for them.
• Handling Cycles: Forgetting to track visited nodes, leading to an infinite recursion or an infinite loop in BFS.
• Disconnected Components: While the problem often specifies a connected graph, failing to consider how to handle multiple components if the requirement changed.

Interview preparation tip

When practicing the Clone Graph coding problem, always draw out the graph and the corresponding hash map on a whiteboard. Visualizing the mapping from the original node to the clone makes it much easier to write the logic for updating neighbors.