Unit 10 Session 1 Standard (Click for link to problem statements)
Unit 10 Session 1 Advanced (Click for link to problem statements)
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?
Node represent?
Node represents a celebrity, with val as the celebrity’s name and neighbors as the adjacent (sitting next to) guests.HAPPY CASE
Input:
lily = Node(""Lily Gladstone"")
mark = Node(""Mark Ruffalo"")
cillian = Node(""Cillian Murphy"")
danielle = Node(""Danielle Brooks"")
lily.neighbors.extend([mark, danielle])
mark.neighbors.extend([lily, cillian])
cillian.neighbors.extend([danielle, mark])
danielle.neighbors.extend([lily, cillian])
Output: A deep copy of the seating arrangement graph starting from `lily`.
EDGE CASE
Input:
lily = Node(""Lily Gladstone"")
lily.neighbors = []
Output: A copy of the node `lily` with no neighbors.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 Copy problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We will perform a DFS starting from the given node (seat). For each node, we create a new node with the same value, and recursively copy all its neighbors. We use a hash map to keep track of already copied nodes to avoid cycles and redundant work.
1) Create an empty dictionary `old_to_new` to store the mapping from the original nodes to their copies.
2) Define a helper function `dfs(node)` that performs the following:
a) If `node` is `None`, return `None`.
b) If `node` has already been copied, return the copy from the `old_to_new` dictionary.
c) Create a new node with the same value as `node` and add it to `old_to_new`.
d) Recursively copy all neighbors of `node` and add them to the `neighbors` list of the new node.
3) Call `dfs(seat)` to start the DFS and return the copy of the seating arrangement.⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Node():
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def copy_seating(seat):
# Hash map to keep track of visited and copied nodes
old_to_new = {}
def dfs(node):
if node is None:
return None
# If the node is already copied, return the copy
if node in old_to_new:
return old_to_new[node]
# Create a new copy of the node
copy = Node(node.val)
old_to_new[node] = copy
# Recursively copy all the neighbors
for neighbor in node.neighbors:
copy.neighbors.append(dfs(neighbor))
return copy
# Start the DFS from the given seat (starting node)
return dfs(seat)Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
lily = Node(""Lily Gladstone"")
mark = Node(""Mark Ruffalo"")
cillian = Node(""Cillian Murphy"")
danielle = Node(""Danielle Brooks"")
lily.neighbors.extend([mark, danielle])
mark.neighbors.extend([lily, cillian])
cillian.neighbors.extend([danielle, mark])
danielle.neighbors.extend([lily, cillian])
copy = copy_seating(lily)
print(compare_graphs(lily, copy)) # Output: TrueEvaluate the performance of your algorithm and state any strong/weak or future potential work.
O(n), where n is the number of nodes in the graph. Each node is visited once during DFS.O(n) for storing the hash map and the recursion stack (in the worst case).