Maximum Gain on a Budgeted Returning Walk
NVIDIA● HardFULLTIMEONSITE INTERVIEWProblem statement
An undirected graph has a nonnegative gain at each vertex and a positive cost on each edge. Start at vertex start, traverse zero or more edges, and finish at that same vertex with total edge cost at most budget. Return the greatest total gain possible.
- The gain of
startcounts even if you do not move. - Each other vertex contributes its gain only on the first visit. Later visits contribute no additional gain.
- Vertices and edges may be revisited. Parallel edges are allowed. Each row of
edgesis[u, v, cost]and may be used in either direction.
Function
maxGainWalk(gains: int[], edges: int[][], start: int, budget: int) → intExamples
Example 1
gains = [5, 10, 7]edges = [[0, 1, 2], [1, 2, 2], [0, 2, 6]]start = 0budget = 8return = 22The walk 0 to 1 to 2 to 1 to 0 costs 8 and gains 5 + 10 + 7. Revisiting 1 does not count it twice.
Example 2
gains = [4, 100, 3]edges = [[0, 1, 3], [0, 2, 1]]start = 0budget = 5return = 7Node 1 needs cost 6 for a round trip; 0 to 2 to 0 costs 2 and gains 4 + 3.
Example 3
gains = [1, 7, 9, 100]edges = [[0, 1, 1], [0, 2, 1], [2, 3, 8]]start = 0budget = 4return = 17Visit 1 and 2 on separate round trips through 0 for cost 4. Node 3 is too far away.
Example 4
gains = [3, 50]edges = [[0, 1, 1]]start = 0budget = 0return = 3Staying at the starting node costs nothing and includes its gain.
Constraints
1 <= gains.length <= 12;0 <= gains[i] <= 1000.0 <= edges.length <= 100; each endpoint is a distinct valid vertex index and1 <= cost <= 100.0 <= start < gains.length;0 <= budget <= 1000.