City Traffic
Category: System Design
Problem Description
Given a representation of an undirected graph where each node represents a city with its population, and edges represent roads connecting cities. The input strArr is an array of strings, where each string is formatted as population:[neighbor1_population,neighbor2_population,...].
For example:
strArr = ["1:[5]", "4:[5]", "3:[5]", "5:[1,4,3,2]", "2:[5,15,7]", "7:[2,8]", "8:[7,38]", "15:[2]", "38:[8]"]
The task is to calculate, for each city, the maximum traffic that would flow through any single road connected to it if all people from all other cities decided to travel to that city. Traffic on a road is calculated by summing the populations of all cities that would use that road to reach the target city.
For instance, if everyone travels to city 7:
- Traffic via the upper road to city 7: (population of city 8 + population of city 38) = (8 + 38) = 46.
- Traffic via the lower road to city 7: (population of city 2 + population of city 15 + population of city 1 + population of city 3 + population of city 4 + population of city 5) = (2 + 15 + 1 + 3 + 4 + 5) = 30.
The maximum traffic for city 7 is max(46, 30) = 46.
The program should output a comma-separated string of city:max_traffic pairs, sorted by city number. For the example above, the output would be: 1:82,2:53,3:80,4:79,5:70,7:46,8:38,15:68,38:45.
Constraints:
- Cities are represented by unique positive integers.
- The graph is undirected and has no cycles.
- There will be at least 2 cities.
AI interview prep
Core dilemma
Efficiently calculating the sum of populations for all possible subtrees rooted at each neighbor of a target city, and then determining the maximum among these sums for each city.
2 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
City Traffic
Category: System Design
Problem Description
Given a representation of an undirected graph where each node represents a city with its population, and edges represent roads connecting cities. The input strArr is an array of strings, where each string is formatted as population:[neighbor1_population,neighbor2_population,...].
For example:
strArr = ["1:[5]", "4:[5]", "3:[5]", "5:[1,4,3,2]", "2:[5,15,7]", "7:[2,8]", "8:[7,38]", "15:[2]", "38:[8]"]
The task is to calculate, for each city, the maximum traffic that would flow through any single road connected to it if all people from all other cities decided to travel to that city. Traffic on a road is calculated by summing the populations of all cities that would use that road to reach the target city.
For instance, if everyone travels to city 7:
- Traffic via the upper road to city 7: (population of city 8 + population of city 38) = (8 + 38) = 46.
- Traffic via the lower road to city 7: (population of city 2 + population of city 15 + population of city 1 + population of city 3 + population of city 4 + population of city 5) = (2 + 15 + 1 + 3 + 4 + 5) = 30.
The maximum traffic for city 7 is max(46, 30) = 46.
The program should output a comma-separated string of city:max_traffic pairs, sorted by city number. For the example above, the output would be: 1:82,2:53,3:80,4:79,5:70,7:46,8:38,15:68,38:45.
Constraints:
- Cities are represented by unique positive integers.
- The graph is undirected and has no cycles.
- There will be at least 2 cities.