How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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

Last updated: Apr 12, 2026

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.

Medium
Airbnb
Coding & Algorithms
Software Engineer

Airbnb

Aug 4, 2025, 10:55 AM

Software Engineer

Technical Screen

Coding & Algorithms

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

Comments (0)

Loading comments...

Browse More Questions

More Coding & Algorithms•More Airbnb•More Software Engineer•Airbnb Software Engineer•Airbnb Coding & Algorithms•Software Engineer Coding & Algorithms