Road Toll Influence | Dataford Interview Questions

There are n cities connected by roads with toll prices; find the road whose toll can be increased so that the average price increase across all routes from city 0 to city n-1 is maximized.

Asked in the DSA round stage. Treat roads as directed edges in a DAG. Increasing one road's toll by 1 increases a route's price by 1 exactly when that route uses the road. Return the zero-based road index, breaking ties by smaller index.

Input: n and roads, where each road is [from, to, toll]. Output: an integer road index.

Constraints

2 <= n <= 1000
1 <= roads.length <= 5000
Each road is [from, to, toll].
0 <= from, to < n and from != to.
1 <= toll <= 10^9.
The roads form a directed acyclic graph.
At least one route exists from city 0 to city n - 1.
Parallel roads are allowed.
Ties are resolved by the smallest road index.

Function Signature

def max_average_increase(n, roads):

Your question is Road Toll Influence. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

There are n cities connected by roads with toll prices; find the road whose toll can be increased so that the average price increase across all routes from city 0 to city n-1 is maximized.

Input: n and roads, where each road is [from, to, toll]. Output: an integer road index.

Constraints

2 <= n <= 1000
1 <= roads.length <= 5000
Each road is [from, to, toll].
0 <= from, to < n and from != to.
1 <= toll <= 10^9.
The roads form a directed acyclic graph.
At least one route exists from city 0 to city n - 1.
Parallel roads are allowed.
Ties are resolved by the smallest road index.

Function Signature

def max_average_increase(n, roads):

Your question is Road Toll Influence. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.