Maximizing Star Power - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Graph Traversal, DFS, Backtracking, Weighted Graph

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 graph represent?
    • A: The graph represents collaborations between celebrities, where each edge between two celebrities is associated with two values: star power (benefit) and the cost of hiring them both.
  • Q: What is the goal of the problem?
    • A: The goal is to find the maximum possible star power between two costars, costar_a and costar_b.
  • Q: Can there be multiple paths between the two costars?
    • A: Yes, and the problem asks for the path with the maximum star power.
  • Q: Is there any constraint on the cost of the collaboration?
    • A: No, the problem only asks to maximize the star power and does not factor in the cost for this particular problem.
HAPPY CASE
Input: 
```python
collaboration_map = {
    ""Leonardo DiCaprio"": [(""Brad Pitt"", 40), (""Robert De Niro"", 30)],
    ""Brad Pitt"": [(""Leonardo DiCaprio"", 40), (""Scarlett Johansson"", 20)],
    ""Robert De Niro"": [(""Leonardo DiCaprio"", 30), (""Chris Hemsworth"", 50)],
    ""Scarlett Johansson"": [(""Brad Pitt"", 20), (""Chris Hemsworth"", 30)],
    ""Chris Hemsworth"": [(""Robert De Niro"", 50), (""Scarlett Johansson"", 30)]
}

print(find_max_star_power(collaboration_map, ""Leonardo DiCaprio"", ""Chris Hemsworth""))
```
Output:
```markdown
90
Explanation: The maximum star power path is from Leonardo DiCaprio -> Brad Pitt -> Scarlett Johansson -> Chris Hemsworth with a total star power of 90 (40 + 20 + 30).
```

EDGE CASE
Input: 
```python
collaboration_map = {
    ""Leonardo DiCaprio"": [(""Brad Pitt"", 40)],
    ""Brad Pitt"": [(""Leonardo DiCaprio"", 40)]
}

print(find_max_star_power(collaboration_map, ""Leonardo DiCaprio"", ""Brad Pitt""))
```
Output:
```markdown
40
Explanation: The only path is Leonardo DiCaprio -> Brad Pitt, with a star power of 40.

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 Maximizing Star Power problems, we want to consider the following approaches:

  • Depth First Search (DFS) with backtracking: This is useful for exploring all possible paths between two costars, keeping track of the maximum star power encountered so far.
  • Weighted Graphs: Each edge in the graph has a weight (star power), so we need to sum the weights of the edges on each path to determine the star power of that path.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to explore all possible paths between costar_a and costar_b. Keep track of the total star power of the current path, and update the maximum star power whenever a path to costar_b is found.

1) Initialize a variable `max_star_power` to store the maximum star power encountered during the traversal.
2) Define a recursive DFS function:
   a) If the current celebrity is `costar_b`, update the `max_star_power` if the current path's star power is higher.
   b) For each neighbor (connected celebrity), if they have not been visited, recursively explore their connections while accumulating the star power.
   c) Backtrack by removing the current celebrity from the visited set after exploring its connections.
3) Start the DFS from `costar_a` and return the `max_star_power` after the traversal is complete.

⚠️ Common Mistakes

  • Forgetting to backtrack (unmarking visited celebrities), which can lead to incorrect results.
  • Not updating the max_star_power correctly when multiple paths are found.

4: I-mplement

Implement the code to solve the algorithm.

def find_max_star_power(collaboration_map, costar_a, costar_b):
    # Initialize maximum star power to 0
    max_star_power = [0]
    
    # DFS function
    def dfs(celebrity, current_star_power, visited):
        # If we reached the target costar_b, update the max_star_power
        if celebrity == costar_b:
            max_star_power[0] = max(max_star_power[0], current_star_power)
            return
        
        # Visit all neighbors
        for neighbor, star_power in collaboration_map.get(celebrity, []):
            if neighbor not in visited:
                visited.add(neighbor)
                dfs(neighbor, current_star_power + star_power, visited)
                visited.remove(neighbor)
    
    # Start DFS from costar_a
    visited = set([costar_a])
    dfs(costar_a, 0, visited)
    
    return max_star_power[0]

5: R-eview

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

  • Input:
collaboration_map = {
    ""Leonardo DiCaprio"": [(""Brad Pitt"", 40), (""Robert De Niro"", 30)],
    ""Brad Pitt"": [(""Leonardo DiCaprio"", 40), (""Scarlett Johansson"", 20)],
    ""Robert De Niro"": [(""Leonardo DiCaprio"", 30), (""Chris Hemsworth"", 50)],
    ""Scarlett Johansson"": [(""Brad Pitt"", 20), (""Chris Hemsworth"", 30)],
    ""Chris Hemsworth"": [(""Robert De Niro"", 50), (""Scarlett Johansson"", 30)]
}

print(find_max_star_power(collaboration_map, ""Leonardo DiCaprio"", ""Chris Hemsworth""))  # Expected output: 90
  • Output:
90

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 celebrities (vertices) and E is the number of collaborations (edges). Each celebrity and collaboration is explored once in the DFS traversal.
  • Space Complexity: O(V) for the recursion stack and visited set.