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.

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.

Hints

  1. Because the graph is acyclic, try processing nodes in topological order instead of using general longest-path algorithms.
  2. 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.

Loading coding console...