Find max-score path in weighted 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, testing understanding of weighted DAGs where node scores and edge time costs combine to define path values and the ability to reconstruct an optimal path.
Constraints
- 1 <= number of nodes <= 10^5
- 0 <= number of edges <= 2 * 10^5
- The graph is a DAG
- Every edge endpoint appears in `weights`
- `weights["start"] = 0` and the node `"start"` exists
- Node scores are integers in the range [-10^9, 10^9]
- Edge costs are integers in the range [0, 10^9]
Examples
Input: ({'start': 0, 'A': 5, 'B': 2, 'C': 4, '_end': 3}, [('start', 'A', 1), ('start', 'B', 0), ('A', 'C', 1), ('B', 'C', 1), ('C', '_end', 2), ('A', '_end', 5)])
Expected Output: (8, ['start', 'A', 'C', '_end'])
Explanation: The best path is start -> A -> C -> _end. Its score is (0 + 5 + 4 + 3) - (1 + 1 + 2) = 8.
Input: ({'start': 0, 'X': 1, 'Y': 10, '_t1': 2, '_t2': 1}, [('start', 'X', 1), ('X', '_t1', 0), ('start', 'Y', 3), ('Y', '_t2', 1)])
Expected Output: (7, ['start', 'Y', '_t2'])
Explanation: Path start -> Y -> _t2 has score (0 + 10 + 1) - (3 + 1) = 7, which is better than the path through X.
Input: ({'start': 0, 'A': 5, '_goal': 7}, [('start', 'A', 1)])
Expected Output: None
Explanation: The only terminal node, _goal, is not reachable from start, so no feasible path exists.
Input: ({'start': 0, 'A': -5, 'B': 4, 'C': 6, '_end': 1}, [('start', 'A', 0), ('A', '_end', 0), ('start', 'B', 2), ('B', 'C', 1), ('C', '_end', 1)])
Expected Output: (7, ['start', 'B', 'C', '_end'])
Explanation: The direct route through A gives score -4, while start -> B -> C -> _end gives (0 + 4 + 6 + 1) - (2 + 1 + 1) = 7.
Input: ({'start': 0, 'P': 2, 'Q': 7, 'R': 3, '_z': 4, 'T': 100}, [('start', 'P', 1), ('start', 'Q', 5), ('P', 'R', 1), ('Q', 'R', 0), ('R', '_z', 1)])
Expected Output: (8, ['start', 'Q', 'R', '_z'])
Explanation: Node R can be reached from both P and Q. The better predecessor is Q, producing score (0 + 7 + 3 + 4) - (5 + 0 + 1) = 8.
Solution
def solution(weights, edges):
from collections import deque
nodes = set(weights.keys())
for u, v, _ in edges:
nodes.add(u)
nodes.add(v)
if "start" not in nodes:
return None
adj = {node: [] for node in nodes}
indegree = {node: 0 for node in nodes}
for u, v, cost in edges:
adj[u].append((v, cost))
indegree[v] += 1
q = deque([node for node in nodes if indegree[node] == 0])
topo = []
while q:
u = q.popleft()
topo.append(u)
for v, _ in adj[u]:
indegree[v] -= 1
if indegree[v] == 0:
q.append(v)
if len(topo) != len(nodes):
raise ValueError("Input graph must be a DAG")
neg_inf = float("-inf")
best = {node: neg_inf for node in nodes}
parent = {node: None for node in nodes}
best["start"] = weights["start"]
for u in topo:
if best[u] == neg_inf:
continue
for v, cost in adj[u]:
cand = best[u] + weights[v] - cost
if cand > best[v]:
best[v] = cand
parent[v] = u
best_terminal = None
best_score = neg_inf
for node in nodes:
if node.startswith("_") and best[node] > best_score:
best_score = best[node]
best_terminal = node
if best_terminal is None:
return None
path = []
cur = best_terminal
while cur is not None:
path.append(cur)
cur = parent[cur]
path.reverse()
if path[0] != "start":
return None
return (best_score, path)Time complexity: O(V + E). Space complexity: O(V + E).
Hints
- Because the graph is acyclic, try processing nodes in topological order instead of using general longest-path algorithms.
- For each node, store the best score achievable when reaching it from `start`, and keep a parent pointer so you can rebuild the path at the end.