Katkat
Back

Maximize path score in DAG

AirbnbSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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).