How should I practice Choose a Road to Maximize Average Route Toll Increase?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Harness phone screen problems in FastPrep.

Is Choose a Road to Maximize Average Route Toll Increase associated with Harness?

FastPrep tags this as a Harness phone screen coding practice problem when the problem catalog has that company and stage context.

Choose a Road to Maximize Average Route Toll Increase

Harness● HardFULLTIMEPHONE SCREEN

Learn

Problem statement

A directed acyclic graph has cities 0 through n-1. Each road is [from,to,toll]. Every route means a directed path from city 0 to city n-1.

Increase exactly one road's toll by one. Return the zero-based input index that maximizes the average toll increase across all routes. Roads on no complete route contribute zero; break ties by smaller input index. Return -1 when no route exists.

Function

bestRoadToIncrease(n: int, roads: int[][]) → int

Examples

Example 1

n = 4roads = [[0,1,5],[0,2,1],[1,3,2],[2,3,9]]return = 0

Every road belongs to one of two routes, so index zero wins the tie.

Example 2

n = 4roads = [[0,1,1],[1,2,1],[1,3,1],[2,3,1]]return = 0

Road 0 appears on both complete routes.

Example 3

n = 3roads = [[0,1,2]]return = -1

No route reaches the destination.

Constraints

2 <= n <= 100000.
The graph is a DAG.
Path counts fit in a signed 64-bit integer.