Airbnb·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jun 2026

Summary

Coding round at Airbnb for a software engineer role. Had drilled a ton of practice problems beforehand, but the one question they threw at me was something I'd never seen, and the interviewer kept jumping in with hints the whole time.

Questions Asked (1)

Given a list of tasks with dependencies between them, determine a valid execution order (or detect if one is impossible).

Algorithms & Data Structures

Author's notes

The only problem I hadn't seen before out of everything I prepped.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the tasks and dependencies as a directed graph, then perform a topological sort using either Kahn's algorithm (BFS) or DFS. If a cycle is detected, report that no valid order exists.

Pro tip: Clarify edge cases upfront, such as duplicate dependencies or disconnected components, and mention that the algorithm runs in O(V+E) time and space, which is optimal.

1. Clarify requirements and edge cases

Ask about input format (e.g., adjacency list or edge list), whether tasks are uniquely identified, and if there can be multiple valid orders. Confirm that detecting impossibility means finding a cycle.

2. Choose representation and algorithm

Represent the graph using an adjacency list and indegree array for Kahn's algorithm, or recursion stack for DFS. Explain why topological sort is the right approach.

3. Implement topological sort

For Kahn's: initialize a queue with nodes of indegree 0, repeatedly dequeue and reduce indegrees of neighbors, adding new zero-indegree nodes. For DFS: perform post-order traversal and reverse the result.

4. Detect cycles and validate result

If the number of processed nodes is less than total nodes, a cycle exists. Otherwise, return the order. Discuss how to handle multiple valid orders (e.g., any order is acceptable).

5. Analyze complexity and test

State time and space complexity: O(V+E). Walk through a simple example and a cycle case to verify correctness.

Key Points to Mention

Topological sorting is applicable only to Directed Acyclic Graphs (DAGs).
Kahn's algorithm uses BFS and indegree counts; DFS uses recursion and a temporary stack.
Cycle detection: if not all nodes are visited, a cycle exists.
Time and space complexity: O(V+E) for both algorithms.
Handling disconnected graphs: the algorithm naturally processes all components.
Potential follow-up: return any valid order or all possible orders (if asked).

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