Maximize path score in DAG
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates proficiency in graph algorithms and optimization, focusing on reasoning about weighted directed acyclic graphs and maximizing a path score that combines node rewards and edge time costs.
Constraints
- 1 <= len(names) == len(scores) <= 200000
- 0 <= len(edges) <= 300000
- Each edge is a tuple (u, v, cost) with 0 <= u, v < n
- The graph is a directed acyclic graph (DAG)
- 0 <= cost <= 10^9
- -10^9 <= scores[i] <= 10^9
- scores[start] = 0
- At least one node whose name begins with "_" is reachable from start
- The answer fits in a signed 64-bit integer
Examples
Input: (['start', 'a', '_end', 'b'], [0, 5, 10, 4], [(0, 1, 2), (1, 2, 3), (0, 3, 1), (3, 2, 1)], 0)
Expected Output: 12
Explanation: Two main paths reach _end. Path 0->1->2 gives 0+5+10-2-3 = 10. Path 0->3->2 gives 0+4+10-1-1 = 12, which is optimal.
Input: (['_only'], [0], [], 0)
Expected Output: 0
Explanation: The start node is already a valid ending node, so the best path is the single-node path with score 0.
Input: (['start', '_a', 'b', '_c'], [0, -5, 10, 1], [(0, 1, 1), (0, 2, 2), (2, 3, 20), (0, 3, 0)], 0)
Expected Output: 1
Explanation: Ending at _a gives 0-5-1 = -6. Ending at _c directly gives 0+1-0 = 1. Going through b to _c gives 0+10+1-2-20 = -11. The best score is 1.
Input: (['start', 'x', '_mid', 'y', '_end'], [0, 4, 6, 5, 3], [(0, 1, 1), (1, 2, 1), (2, 3, 1), (3, 4, 1), (0, 4, 0)], 0)
Expected Output: 14
Explanation: Stopping at _mid yields 0+4+6-1-1 = 8. Going directly to _end yields 3. Continuing through _mid to _end gives 0+4+6+5+3-1-1-1-1 = 14, which is best.
Input: (['start', 'a', '_bad'], [0, -2, -3], [(0, 1, 1), (1, 2, 1)], 0)
Expected Output: -7
Explanation: The only valid path is 0->1->2, with score 0-2-3-1-1 = -7.
Solution
from collections import deque
def solution(names, scores, edges, start):
n = len(names)
graph = [[] for _ in range(n)]
indegree = [0] * n
for u, v, cost in edges:
graph[u].append((v, cost))
indegree[v] += 1
q = deque(i for i in range(n) if indegree[i] == 0)
topo = []
while q:
u = q.popleft()
topo.append(u)
for v, cost in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
q.append(v)
NEG_INF = -(10 ** 30)
best = [NEG_INF] * n
best[start] = scores[start]
for u in topo:
if best[u] == NEG_INF:
continue
for v, cost in graph[u]:
candidate = best[u] - cost + scores[v]
if candidate > best[v]:
best[v] = candidate
answer = NEG_INF
for i, name in enumerate(names):
if name.startswith('_') and best[i] > answer:
answer = best[i]
return answer
Time complexity: O(n + m). Space complexity: O(n + m).
Hints
- Because the graph is acyclic, you can process nodes in topological order instead of using a general longest-path algorithm.
- Let best[v] be the maximum score of any path from start to v. How does best[v] update across an edge u -> v with cost c?