Unit 10 Session 2 Advanced (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?
roads array represent?
[a, b] in roads represents a two-way road connecting city a and city b.0).HAPPY CASE
Input:
```python
roads_1 = [[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]]
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.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:
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
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]Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
roads_1 = [[0,1],[0,2],[0,3]]
seats_1 = 5
roads_2 = [[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: 73
7Evaluate the performance of your algorithm and state any strong/weak or future potential work.
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.O(V + E) for storing the graph and recursion stack.