Airbnb·Software Engineer·Technical Phone Screen·Senior

Senior

Jul 2026

Summary

Airbnb SWE interview with a graph algorithm problem that looked clean on the surface but had a few wrinkles worth thinking through carefully. One question, no behavioral fluff, just straight into the technical.

Questions Asked (1)

You're given a directed acyclic graph where each node has a score and each edge has a nonnegative time cost. There's a fixed start node with score zero, and terminal nodes are identified by a naming convention. A path's total value is the sum of node scores minus the sum of edge costs along the way. Find the path from start to any terminal node that maximizes this value, and return both the max value and the actual path. If no terminal is reachable, say so. Walk through your algorithm and give a complexity analysis.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was Dijkstra but that's for minimizing cost, not maximizing a mixed score-minus-cost objective.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem details, then propose a dynamic programming solution on the DAG that computes the maximum value to each node and reconstructs the path. Discuss complexity and edge cases, and compare with alternative approaches like topological sort with DP or modified Dijkstra.

Pro tip: Emphasize that the DAG property allows linear-time DP, and mention that if the graph were not a DAG, the problem would be NP-hard, showing you understand the importance of the constraint.

1. Clarify and Restate

Ask clarifying questions about terminal node identification, score ranges, and whether negative scores are allowed. Restate the problem to ensure alignment.

2. Choose Algorithm

Propose dynamic programming on the DAG: compute topological order, then for each node, compute the maximum value from start to that node. Alternatively, use a modified Dijkstra if edge costs are nonnegative but node scores can be negative.

3. Define DP and Recurrence

Define dp[v] as the maximum value of a path from start to v. Initialize dp[start] = 0, others -inf. For each node in topological order, relax outgoing edges: dp[to] = max(dp[to], dp[from] + score[to] - cost(edge)).

4. Path Reconstruction

Maintain a parent pointer for each node when updating dp. After computing dp for all terminals, find the terminal with max dp, then backtrack using parent pointers to get the path.

5. Complexity and Edge Cases

Analyze time and space complexity: O(V+E) time, O(V) space. Discuss handling unreachable terminals, multiple terminals, and negative values. Mention that if no terminal reachable, return appropriate message.

Key Points to Mention

Topological sort to process nodes in linear order
Dynamic programming recurrence: dp[v] = max over incoming edges (dp[u] + score[v] - cost(u,v))
Parent pointers for path reconstruction
Time complexity O(V+E), space O(V)
Handling unreachable terminals and negative scores
Comparison with Dijkstra's algorithm and why DAG allows simpler DP

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.