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.

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.

Hints

  1. Because the graph is acyclic, you can process nodes in topological order instead of using a general longest-path algorithm.
  2. 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?

Loading coding console...