Cast vs Crew - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-35 mins
  • 🛠️ Topics: Graph Traversal, DFS, Connected Components

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 the adjacency dictionary cast_and_crew represent?
    • A: It represents connections between cast or crew members based on their involvement in the same movie.
  • Q: How are cast and crew members grouped?
    • A: Cast members are connected to each other, and crew members are connected to each other, but there are no connections between cast and crew.
  • Q: What should the function return?
    • A: The function should return two lists, one containing all cast members and the other containing all crew members.
HAPPY CASE
Input: 
get_out_movie = {
    ""Daniel Kaluuya"": [""Allison Williams""],
    ""Allison Williams"": [""Daniel Kaluuya"", ""Catherine Keener"", ""Bradley Whitford""],
    ""Bradley Whitford"": [""Allison Williams"", ""Catherine Keener""],
    ""Catherine Keener"": [""Allison Williams"", ""Bradley Whitford""],
    ""Jordan Peele"": [""Jason Blum"", ""Gregory Plotkin"", ""Toby Oliver""],
    ""Toby Oliver"": [""Jordan Peele"", ""Gregory Plotkin""],
    ""Gregory Plotkin"": [""Jason Blum"", ""Toby Oliver"", ""Jordan Peele""],
    ""Jason Blum"": [""Jordan Peele"", ""Gregory Plotkin""]
}

Output:
[
    ['Daniel Kaluuya', 'Allison Williams', 'Catherine Keener', 'Bradley Whitford'],
    ['Jordan Peele', 'Jason Blum', 'Gregory Plotkin', 'Toby Oliver']
]
Explanation: The function correctly separates the cast from the crew into two distinct groups.

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 Connected Components problems, we want to consider the following approaches:

  • Depth First Search (DFS): DFS can be used to explore all cast members or crew members from one starting node, marking each node as visited to avoid cycles.
  • Breadth First Search (BFS): BFS could also be used, but DFS is more typical when finding connected components in undirected graphs.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to explore the graph. Each time we find an unvisited node, we start a new DFS traversal, marking all nodes in that connected component. After the traversal completes, we have found either a complete group of cast members or crew members.

1) Initialize a `visited` set to track people who have already been added to a group.
2) Define a recursive DFS function that:
   a) Marks the current person as visited and adds them to the current group.
   b) Recursively explores all unvisited neighbors (people connected to the current person).
3) Traverse through all people in `cast_and_crew`:
   a) For each unvisited person, start a DFS and create a new group.
4) Return the list of groups after the DFS traversal is complete.

⚠️ Common Mistakes

  • Not marking people as visited, which could lead to cycles and infinite recursion.
  • Forgetting to explore all neighbors of a person, resulting in incomplete groups.

4: I-mplement

Implement the code to solve the algorithm.

def get_groups(cast_and_crew):
    visited = set()
    groups = []

    def dfs(person, group):
        # Mark the current person as visited and add them to the group
        visited.add(person)
        group.append(person)
        
        # Recursively visit all unvisited neighbors
        for neighbor in cast_and_crew[person]:
            if neighbor not in visited:
                dfs(neighbor, group)
    
    # Traverse all people in cast_and_crew
    for person in cast_and_crew:
        if person not in visited:
            group = []
            dfs(person, group)
            groups.append(group)
    
    return groups

5: R-eview

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

  • Input:
get_out_movie = {
    ""Daniel Kaluuya"": [""Allison Williams""],
    ""Allison Williams"": [""Daniel Kaluuya"", ""Catherine Keener"", ""Bradley Whitford""],
    ""Bradley Whitford"": [""Allison Williams"", ""Catherine Keener""],
    ""Catherine Keener"": [""Allison Williams"", ""Bradley Whitford""],
    ""Jordan Peele"": [""Jason Blum"", ""Gregory Plotkin"", ""Toby Oliver""],
    ""Toby Oliver"": [""Jordan Peele"", ""Gregory Plotkin""],
    ""Gregory Plotkin"": [""Jason Blum"", ""Toby Oliver"", ""Jordan Peele""],
    ""Jason Blum"": [""Jordan Peele"", ""Gregory Plotkin""]
}

print(get_groups(get_out_movie))  # Expected output: cast and crew groups as separate lists
  • Output:
[
    ['Daniel Kaluuya', 'Allison Williams', 'Catherine Keener', 'Bradley Whitford'],
    ['Jordan Peele', 'Jason Blum', 'Gregory Plotkin', 'Toby Oliver']
]

6: E-valuate

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

  • Time Complexity: O(V + E), where V is the number of people (vertices) and E is the number of connections (edges). We explore each person and connection once.
  • Space Complexity: O(V) for storing the visited set and recursion stack.