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.

Maximize path score in DAG | Airbnb Coding Question

Maximize path score in DAG

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Given a weighted directed acyclic graph (DAG) where each node v has a score w(v) and each edge (u→v) has a time cost t(u,v), starting from node "start" (w(start)= 0) and ending at any node whose name begins with an underscore "_", find the path P that maximizes Score(P) = Σ w(v) − Σ t(u,v). Output the maximum score (and optionally the corresponding path).

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.

You are given a weighted directed acyclic graph (DAG). Each node i has a name names[i] and a score scores[i]. Each directed edge (u -> v) has a non-negative time cost c. Starting from node start, define the score of a path as the sum of the scores of all visited nodes minus the sum of the time costs of all edges used. Formally, for a path P = v0 -> v1 -> ... -> vk where v0 = start: Score(P) = scores[v0] + scores[v1] + ... + scores[vk] - (cost(v0,v1) + ... + cost(v{k-1},vk)) Find the maximum possible score among all paths that start at start and end at any node whose name begins with an underscore "_". Important notes: - The graph is guaranteed to be a DAG. - A node whose name starts with "_" is a valid ending node even if it has outgoing edges. - You may pass through one underscore-prefixed node and continue to another; only the final chosen node matters. - For this version of the problem, return only the maximum score, not the path itself.

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.

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?

Quick Overview

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.