Unit 10 Session 2 Standard (Click for link to problem statements)
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?
costar_a
and costar_b
.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.
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:
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
max_star_power
correctly when multiple paths are found.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]
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
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
90
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
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.O(V)
for the recursion stack and visited set.