Hollywood Talent Summit - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Graph Traversal, DFS, Tree

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 roads array represent?
    • A: Each element [a, b] in roads represents a two-way road connecting city a and city b.
  • Q: How is the fuel cost calculated?
    • A: Each road between cities costs 1 liter of fuel, and cars must transport the representatives from each city to the capital (city 0).
  • Q: What should happen if the representatives from multiple cities travel in the same car?
    • A: If multiple representatives can fit in a car (based on the number of seats), they will share the fuel cost for that journey.
HAPPY CASE
Input: 
```python
roads_1 = [0,1],[0,2],[0,3](/codepath/compsci_guides/wiki/0,1],[0,2],[0,3)
seats_1 = 5
```
Output:
```markdown
3
Explanation: Each city (1, 2, and 3) sends 1 representative directly to city 0. Since all cities are directly connected to city 0, and each city has only one representative, the total fuel cost is 3 liters.
```

EDGE CASE
Input: 
```python
roads_2 = [3,1],[3,2],[1,0],[0,4],[0,5],[4,6](/codepath/compsci_guides/wiki/3,1],[3,2],[1,0],[0,4],[0,5],[4,6)
seats_2 = 2
```
Output:
```markdown
7
Explanation: Representatives travel from cities 6 -> 4 -> 0, 5 -> 0, 3 -> 1 -> 0, and 2 -> 3 -> 1 -> 0. The minimum fuel needed is 7 liters due to the limited number of seats and the need for multiple trips.

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 Tree Traversal with Fuel Calculation, we want to consider the following approaches:

  • Depth First Search (DFS): Since the cities and roads form a tree structure, DFS can be used to traverse the cities and calculate the number of representatives that need to be transported to the capital city.
  • Greedy Approach: As representatives travel from leaf cities to the root (capital), calculate the fuel cost for each journey, ensuring that the number of trips accounts for the seat capacity.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to traverse the tree and calculate the number of representatives from each subtree. At each city, calculate the number of trips needed to transport representatives to the capital city based on the seat capacity. The total fuel cost is the sum of all trips.

1) Build an adjacency list from the `roads` array to represent the tree structure of the cities.
2) Initialize a `total_fuel` variable to track the total number of liters needed.
3) Define a recursive DFS function:
   a) Traverse all neighbors except the parent to avoid revisiting the parent city.
   b) For each neighboring city, calculate the number of representatives in that subtree.
   c) Calculate the number of trips required to transport those representatives based on the seat capacity, and update the `total_fuel`.
4) Start the DFS from city 0 (the capital) and calculate the total fuel needed.
5) Return the total fuel required.

⚠️ Common Mistakes

  • Forgetting to calculate the fuel cost correctly when multiple representatives share a car.
  • Not handling the case where cities are not directly connected to the capital (though the tree structure guarantees a connection).

4: I-mplement

Implement the code to solve the algorithm.

import math
from collections import defaultdict

def minimum_fuel(roads, seats):
    # Build the adjacency list for the tree structure
    graph = defaultdict(list)
    for a, b in roads:
        graph[a].append(b)
        graph[b].append(a)
    
    # Initialize total fuel cost
    total_fuel = [0]
    
    # DFS function to calculate fuel costs
    def dfs(city, parent):
        representatives = 1  # Assume each city has 1 representative by default
        
        # Traverse all neighbors except the parent (to avoid revisiting)
        for neighbor in graph[city]:
            if neighbor != parent:
                reps_from_subtree = dfs(neighbor, city)
                # Add the representatives from the subtree
                representatives += reps_from_subtree
                # Calculate fuel cost to transport them to the current city
                total_fuel[0] += math.ceil(reps_from_subtree / seats)
        
        return representatives
    
    # Start DFS from city 0 (the capital) with no parent
    dfs(0, -1)
    
    return total_fuel[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:
roads_1 = [0,1],[0,2],[0,3](/codepath/compsci_guides/wiki/0,1],[0,2],[0,3)
seats_1 = 5

roads_2 = [3,1],[3,2],[1,0],[0,4],[0,5],[4,6](/codepath/compsci_guides/wiki/3,1],[3,2],[1,0],[0,4],[0,5],[4,6)
seats_2 = 2

print(minimum_fuel(roads_1, seats_1))  # Expected output: 3
print(minimum_fuel(roads_2, seats_2))  # Expected output: 7
  • Output:
3
7

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 cities (vertices) and E is the number of roads (edges). Each city and road is visited once in the DFS traversal.
  • Space Complexity: O(V + E) for storing the graph and recursion stack.