Clone Graph
You are given a reference to one node of a connected undirected graph. Each node has an integer val and a list neighbors of the nodes it is connected to. Return a deep copy of the graph: a new set of nodes with the same values and the same connections, where no node is shared with the original graph.
The values are the numbers 1 to n, each node holding the value equal to its position, and the graph has no repeated edges and no self loops. The node you are given is the one with value 1. If the graph is empty, the given node is null, and you return null. The copy must list each node's neighbors in the same order as the original.
Examples
Node 1 is the first list, node 2 the second, and so on.
Node 1 is the first list, node 2 the second, and so on.
Constraints
- 0 <= number of nodes <= 100
- 1 <= Node.val <= number of nodes, and the values are all different
- the graph is connected, undirected, with no repeated edges and no self loops
Stuck? Take one hint at a time
Common mistakes
- Storing the copy in the map after the recursive calls instead of before, so a cycle recurses forever.
- Using the value as the key when the language compares nodes by reference, or the other way round, without checking that values are unique.
- Returning the original neighbors instead of copies, so the new graph still shares nodes with the old one (a shallow copy).
- Forgetting the empty graph, where the given node is null.
- Marking a node as seen when taking it from the queue rather than when adding it, so it may be copied twice.
Questions an interviewer may ask next
- The graph is directed, and some nodes cannot be reached from the node you are given. What changes? (The copy contains only what is reachable.)
- Clone a linked list in which every node also has a random pointer to any other node. (Copy List with Random Pointer uses the same map.)
- Values are the numbers 1 to n. How can an array replace the map, and does that change the memory used?
- Verify a clone: write a check that no node is shared with the original and every edge is present.
How often this is reported
Grade C: Reported in one source, or backed mainly by volume of reports. This reflects what candidates report, not a guarantee of what any company will ask.
[[2,4],[1,3],[2,4],[1,3]]
[[2,4],[1,3],[2,4],[1,3]]
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.