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.

What difficulty level is this coding question?

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

What role is this question designed for?

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

Find max-score path in weighted DAG | Airbnb Coding Question

Find max-score path in weighted DAG

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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.

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.

You are given a directed acyclic graph (DAG). Each node has an integer score, provided in a dictionary `weights` where `weights[node]` is the score of that node. Each directed edge `(u -> v)` has a nonnegative time cost. The graph always contains a node literally named `"start"`, and `weights["start"] = 0`. A terminal node is any node whose name begins with an underscore `"_"`. For any path `P` from `"start"` to a terminal node, define: `Score(P) = (sum of node scores on P) - (sum of edge costs on P)` Return the maximum possible score and one corresponding optimal path as an ordered list of node names. If no terminal node is reachable from `"start"`, return `None`. Implement `solution(weights, edges)`, where `edges` is a list of tuples `(from_node, to_node, time_cost)`. If multiple optimal paths exist, returning any one of them is acceptable.

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.

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.

Quick Overview

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.