Find max-score path in weighted DAG

Q: Find max-score path in weighted DAG

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.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Airbnb.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Question

You are given a directed acyclic graph (DAG). Each node v has a score w(v). Each directed edge (u→v) has a nonnegative time cost t(u,v). There is a unique start node literally named "start" with w(start)=0. A terminal node is any node whose name begins with an underscore "_". You may traverse edges only in their given direction. For any path P from "start" to any terminal node, define its total score as Score(P) = (sum of w(v) over all nodes v on P) − (sum of t(u,v) over all edges on P). Compute the maximum Score(P) across all such paths and return both this maximum value and one corresponding optimal path (as an ordered list of node names). If no terminal is reachable from "start", indicate that no feasible path exists. Describe your algorithm and analyze its time and space complexity.

PracHub · Accepted Answer

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)

Quick Overview

Solution

Hints

Quick Overview