How do you clone a graph given a reference to a node?
This problem requires creating a deep copy of a connected undirected graph. It tests graph traversal and memoization techniques.
Why Interviewers Ask This
Interviewers ask this to test graph traversal skills and the ability to handle cycles in graphs. They want to see if you can use a hash map to track visited nodes and prevent infinite loops. It demonstrates careful state management in graph problems.
How to Answer This Question
Explain the need for a hash map to store the mapping between original nodes and their clones. Use BFS or DFS to traverse the graph. For each node, create a clone if it doesn't exist, then add edges to the clones of its neighbors. Ensure you check the map before creating new nodes to handle cycles. Discuss space complexity for the map.
Key Points to Cover
- Hash map for node mapping
- DFS/BFS traversal
- Cycle handling via visited map
- Deep copy logic
Sample Answer
To clone a graph, I use a hash map to store the relationship between original nodes and their copies. I perform a depth-first search starting from the given node. For each node, if it hasn't been cloned yet, I create a n…
Common Mistakes to Avoid
- Creating new nodes for already visited neighbors
- Forgetting to link neighbors in the clone
- Not handling disconnected components if applicable
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.