Clone Graph
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Use a HashMap to track visited nodes and their clones (BFS or DFS).
Why Interviewers Ask This
Salesforce interviewers ask this to evaluate a candidate's mastery of graph traversal algorithms and memory management. They specifically test your ability to handle cycles in undirected graphs without creating infinite loops, while ensuring a true deep copy rather than a shallow reference. This assesses your understanding of HashMap usage for state tracking and your capacity to write clean, production-ready code under pressure.
How to Answer This Question
1. Clarify the input: Confirm if the graph is connected, directed, or contains self-loops, as Salesforce values precise problem definition. 2. Choose a traversal strategy: Explicitly decide between Breadth-First Search (BFS) using a Queue or Depth-First Search (DFS) using recursion, explaining why one might be safer against stack overflow for large inputs. 3. Initialize data structures: Propose a HashMap where keys are original nodes and values are their cloned counterparts to prevent re-cloning and handle cycles. 4. Execute traversal: Walk through the algorithm step-by-step, detailing how you create a new node only if it hasn't been visited, then recursively or iteratively add neighbors to the clone. 5. Validate edge cases: Mention handling null inputs or single-node graphs before returning the final cloned head.
Key Points to Cover
- Explicitly mention using a HashMap to track visited nodes and prevent infinite loops caused by cycles
- Demonstrate clear distinction between shallow copy (reference) and deep copy (new objects)
- Select BFS or DFS with a reasoned justification regarding memory safety or implementation complexity
- Handle edge cases like null inputs or single-node graphs proactively
- Explain the logic for linking neighbors in the cloned graph during traversal
Sample Answer
To solve the Clone Graph problem efficiently, I would first clarify that we are dealing with an undirected graph which inherently contains cycles. My approach uses a Hash Map to map every original node to its correspondi…
Common Mistakes to Avoid
- Creating a shallow copy instead of a deep copy, resulting in shared references between original and cloned graphs
- Failing to detect cycles, causing the algorithm to enter an infinite loop when traversing undirected edges
- Using recursion without considering stack depth limits, which can crash on large graphs common in enterprise systems
- Neglecting to initialize the map with the starting node before beginning the traversal loop
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.