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.