Copying Seating Arrangements - codepath/compsci_guides GitHub Wiki

Unit 10 Session 1 Standard (Click for link to problem statements)

Unit 10 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Graphs, Depth First Search (DFS), Deep Copy

1: U-nderstand

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?
  • Q: What does each Node represent?
    • A: Each Node represents a celebrity, with val as the celebrity’s name and neighbors as the adjacent (sitting next to) guests.
  • Q: How do we perform a deep copy?
    • A: For each node, we need to create a new node with the same value and then recursively copy its neighbors, ensuring that no node is copied more than once.
  • Q: How do we avoid cycles or revisiting the same node?
    • A: Use a hash map (dictionary) to map original nodes to their copied versions and avoid revisiting nodes.
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.

2: M-atch

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:

  • DFS (Depth First Search): This is suitable for traversing through the graph structure and making recursive calls to copy each node and its neighbors.
  • Hash Map: Use a hash map to avoid revisiting and copying nodes that have already been copied.

3: P-lan

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

  • Forgetting to handle cycles or revisiting nodes, leading to infinite recursion.
  • Not copying the neighbors correctly, leading to broken connections in the graph.

4: I-mplement

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)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • 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])

copy = copy_seating(lily)
print(compare_graphs(lily, copy))  # Output: True

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(n), where n is the number of nodes in the graph. Each node is visited once during DFS.
  • Space Complexity: O(n) for storing the hash map and the recursion stack (in the worst case).