Celebrity Collaborations - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-30 mins
🛠️ Topics: Graphs, Weighted Graphs, Adjacency Lists

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 key in the collaborations dictionary represent?
- A: Each key represents an actor, and the value is a list of tuples representing the actor's costars and the number of films they have collaborated on.
Q: Are the edges in the graph undirected?
- A: Yes, the collaborations are undirected, meaning if Actor A costarred with Actor B, then the reverse is also true.
Q: Can the same pair of actors collaborate on multiple films?
- A: Yes, the weight of the edge represents the number of films they have costarred in together.

HAPPY CASE
Input: 
```python
collaborations = {
    ""Chadwick Boseman"": [(""Lupita Nyong'o"", 2), (""Robert Downey Jr."", 3), (""Mark Ruffalo"", 2)],
    ""Lupita Nyong'o"": [(""Chadwick Boseman"", 2), (""Robert Downey Jr."", 1)],
    ""Robert Downey Jr."": [(""Chadwick Boseman"", 3), (""Lupita Nyong'o"", 1), (""Mark Ruffalo"", 3)],
    ""Mark Ruffalo"": [(""Chadwick Boseman"", 2), (""Robert Downey Jr."", 3)]
}
print(collaborations[""Chadwick Boseman""])
```
Output:
```markdown
[(""Lupita Nyong'o"", 2), (""Robert Downey Jr."", 3), (""Mark Ruffalo"", 2)]
```

EDGE CASE
Input: 
```python
collaborations = {}
```
Output:
```markdown
[]
Explanation: If no actors or collaborations are present, the output is an empty list.

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

Graph Representation: Use an adjacency dictionary to represent the weighted graph, where each key is an actor and each value is a list of tuples representing the costars and the number of films they have collaborated on.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: To build the adjacency dictionary, start with an empty dictionary. For each pair of actors and their number of collaborations, add the information to both actors' lists, since the graph is undirected.

1) Initialize an empty dictionary `collaborations` to store the adjacency list.
2) For each pair of actors and their number of collaborations:
   a) If the actor is not already in the dictionary, add them with an empty list.
   b) Add the tuple `(costar, num_collaborations)` to the actor's list.
   c) Repeat the same for the costar (since the graph is undirected).
3) After processing all pairs, return the `collaborations` dictionary.

⚠️ Common Mistakes

Forgetting to add the collaboration to both actors' lists, which could result in an incomplete graph.
Not properly handling actors who appear multiple times but may not yet exist in the dictionary.

4: I-mplement

Implement the code to solve the algorithm.

# Example usage
collaborations = {
    ""Chadwick Boseman"": [(""Lupita Nyong'o"", 2), (""Robert Downey Jr."", 3), (""Mark Ruffalo"", 2)],
    ""Lupita Nyong'o"": [(""Chadwick Boseman"", 2), (""Robert Downey Jr."", 1)],
    ""Robert Downey Jr."": [(""Chadwick Boseman"", 3), (""Lupita Nyong'o"", 1), (""Mark Ruffalo"", 3)],
    ""Mark Ruffalo"": [(""Chadwick Boseman"", 2), (""Robert Downey Jr."", 3)]
}

print(collaborations[""Chadwick Boseman""])

5: R-eview

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

Input:

collaborations = {
    ""Chadwick Boseman"": [(""Lupita Nyong'o"", 2), (""Robert Downey Jr."", 3), (""Mark Ruffalo"", 2)],
    ""Lupita Nyong'o"": [(""Chadwick Boseman"", 2), (""Robert Downey Jr."", 1)],
    ""Robert Downey Jr."": [(""Chadwick Boseman"", 3), (""Lupita Nyong'o"", 1), (""Mark Ruffalo"", 3)],
    ""Mark Ruffalo"": [(""Chadwick Boseman"", 2), (""Robert Downey Jr."", 3)]
}
print(collaborations[""Chadwick Boseman""])

Output:

[(""Lupita Nyong'o"", 2), (""Robert Downey Jr."", 3), (""Mark Ruffalo"", 2)]

6: E-valuate

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

Time Complexity: O(E), where E is the number of edges (collaborations) in the graph. Each edge (collaboration) is processed once for both actors.
Space Complexity: O(V + E), where V is the number of vertices (actors) and E is the number of edges (collaborations), to store the adjacency list.