Given a reference to a node in a connected undirected graph, explain how you would return a deep copy (clone) of the entire graph. Each node has a value and a list of its neighbors.
For example, given this graph:
1 --- 2 | | 4 --- 3
You need to create a completely new graph with the same structure, where no node in the clone references any node in the original.
How do you avoid creating duplicate copies of the same node? How do you handle cycles?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
You need to track which nodes have already been cloned to avoid infinite loops in cyclic graphs.
- Hint 2
Use a hash map mapping original nodes to their cloned counterparts.
- Hint 3
BFS or DFS both work. For each node: if already cloned (in the map), use the existing clone. Otherwise, create a new clone, store it in the map, and recursively or iteratively clone its neighbors.
Ready to answer it out loud?
Record your answer in 1:00 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.