Maximizing Star Power Under Budget - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

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

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 collaboration_map represent?
    • A: Each key represents a celebrity, and the value is a list of tuples representing the celebrity's costars, the star power of their collaboration, and the cost of the collaboration.
  • Q: What is the goal of the problem?
    • A: The goal is to find the maximum star power possible while staying under the given budget from the start celebrity to the target celebrity.
  • Q: What should the function return if no valid path exists within the budget?
    • A: The function should return 0 if it is not possible to reach the target while staying within the budget.
HAPPY CASE
Input: 
```python
collaboration_map = {
    ""Leonardo DiCaprio"": [(""Brad Pitt"", 40, 300), (""Robert De Niro"", 30, 200)],
    ""Brad Pitt"": [(""Leonardo DiCaprio"", 40, 300), (""Scarlett Johansson"", 20, 150)],
    ""Robert De Niro"": [(""Leonardo DiCaprio"", 30, 200), (""Chris Hemsworth"", 50, 350)],
    ""Scarlett Johansson"": [(""Brad Pitt"", 20, 150), (""Chris Hemsworth"", 30, 250)],
    ""Chris Hemsworth"": [(""Robert De Niro"", 50, 350), (""Scarlett Johansson"", 30, 250)]
}

start = ""Leonardo DiCaprio""
target = ""Chris Hemsworth""
budget = 500
```
Output:
```markdown
110
Explanation: The maximum star power path is Leonardo DiCaprio -> Robert De Niro -> Chris Hemsworth with a total star power of 30 + 50 = 80.
```

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

start = ""Leonardo DiCaprio""
target = ""Brad Pitt""
budget = 100
```
Output:
```markdown
0
Explanation: The only path exceeds the budget, so no valid path exists.

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 Under a Budget, we want to consider the following approaches:

  • Depth First Search (DFS) with backtracking: DFS can be used to explore all possible paths from the start celebrity to the target celebrity, keeping track of the total cost and star power along the way.
  • Graph Traversal: Each celebrity and their collaborations can be represented as a graph, and we are interested in the path that maximizes the star power while staying within the budget.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to explore all possible paths from the start celebrity to the target celebrity. Track the current star power and total cost during each path exploration. If the total cost exceeds the budget, stop exploring that path. If the target is reached, update the maximum star power. Use backtracking to explore all potential routes.

1) Initialize a `max_star_power` variable to store the maximum star power found.
2) Define a recursive DFS function:
   a) If the current celebrity is the target, update `max_star_power`.
   b) Explore all neighboring celebrities, checking if the total cost remains within the budget.
   c) Use backtracking to remove the current celebrity from the visited set after exploring all neighbors.
3) Start DFS from the `start` celebrity.
4) Return the `max_star_power` found.

⚠️ Common Mistakes

  • Not tracking the total cost correctly, which could lead to paths exceeding the budget.
  • Forgetting to backtrack properly, which could result in incorrect star power calculations or infinite recursion.

4: I-mplement

Implement the code to solve the algorithm.

def find_max_star_power(collaboration_map, start, target, budget):
    max_star_power = [0]  # To store the maximum star power found

    def dfs(current, current_star_power, current_cost, visited):
        # If we reach the target, update the maximum star power
        if current == target:
            max_star_power[0] = max(max_star_power[0], current_star_power)
            return

        # Explore neighbors
        for neighbor, star_power, cost in collaboration_map.get(current, []):
            if neighbor not in visited and current_cost + cost <= budget:
                visited.add(neighbor)
                dfs(neighbor, current_star_power + star_power, current_cost + cost, visited)
                visited.remove(neighbor)  # Backtrack

    # Start DFS from the start celebrity
    visited = set([start])
    dfs(start, 0, 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, 300), (""Robert De Niro"", 30, 200)],
    ""Brad Pitt"": [(""Leonardo DiCaprio"", 40, 300), (""Scarlett Johansson"", 20, 150)],
    ""Robert De Niro"": [(""Leonardo DiCaprio"", 30, 200), (""Chris Hemsworth"", 50, 350)],
    ""Scarlett Johansson"": [(""Brad Pitt"", 20, 150), (""Chris Hemsworth"", 30, 250)],
    ""Chris Hemsworth"": [(""Robert De Niro"", 50, 350), (""Scarlett Johansson"", 30, 250)]
}

start = ""Leonardo DiCaprio""
target = ""Chris Hemsworth""
budget = 500

print(find_max_star_power(collaboration_map, start, target, budget))  # Expected output: 110
  • Output:
110

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 visited once in the DFS traversal.
  • Space Complexity: O(V) for storing the current path and the recursion stack.