Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
EDGE CASE
Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For Graph Problems, common solution patterns include:
Note: The difference is only in the traversal of DFS and BFS. DFS explores the depths of the graph first and BFS explores the breadth.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use BFS or DFS to mark visited nodes and to keep track of created copies
0. Create visited dictionary to save created nodes in memory
1. Define dfs function:
a. Check is current node is empty.
b. Check if cached.
c. Create a new node and save it into map.
d. Use DFS to copy all its neighbors.
e. Return deepcopy
2. Run dfs on given node
1. Use a hash map to store the reference of the copy of all the nodes that have already been visited and copied.
2. Add the first node to the queue.
3. Do the BFS traversal.
- Pop a node from the front of the queue.
- Visit all the neighbors of this node.
- If any of the neighbors was already visited then it must be present in the `visited` dictionary. Get the clone of this neighbor from `visited` in that case.
- Add the clones of the neighbors to the corresponding list of the clone node.
âš ď¸Ź Common Mistakes
visited
hash map in both the BFS/DFS approaches. We need this to to keep track of the nodes which have already been copied. By doing this we don't end up traversing them again.Implement the code to solve the algorithm.
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
# Create visited dictionary to save created nodes in memory
visited = defaultdict(Node)
def dfs(node: 'Node') -> 'Node':
# Check is current node is empty.
if not node:
return None
# Check if cached.
elif node in visited:
return visited[node]
else:
# Create a new node and save it into map
deepcopy = Node(node.val)
visited[node] = deepcopy
# Use DFS to copy all its neighbors
for neighbor in node.neighbors:
deepcopy.neighbors.append(dfs(neighbor))
# Return deepcopy
return deepcopy
# Run dfs on given node
return dfs(node)
class Solution {
// create a hash map to save the visited node and it's respective clone
// as key and value respectively. This helps to avoid cycles.
private Map<Integer, Node> map;
public Node cloneGraph(Node node) {
if (node == null) return null;
map = new HashMap<>();
return dfs(node, node.val);
}
private Node dfs(Node node, int num){
if(node == null) return null;
// if the node was already visited before, return the clone from the visited dictionary
else if(map.containsKey(num)) return map.get(num);
else{
ArrayList<Node> neighbours = new ArrayList<Node>();
Node cur = new Node(num, neighbours);
map.put(num, cur);
// iterate through the neighbors to generate their clones
// and prepare a list of cloned neighbors to be added to the cloned node.
for(Node neighbour : node.neighbors){
neighbours.add(dfs(neighbour, neighbour.val));
}
return cur;
}
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume V
represents the number of vertices.
Assume E
represents the number of edges
V
nodes.