Adobe·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Adobe SWE interview with a graph-based algorithmic problem. Pretty standard topological sort territory but they pushed hard on the details around cycle detection and handling ambiguity in output.

Questions Asked (1)

Given n tasks labeled 0 through n-1 and a list of prerequisite pairs where (a, b) means b must be completed before a, find a valid ordering to complete all tasks. If a cycle exists in the dependencies, report that it's impossible. Walk through your algorithm, data structures, time and space complexity, how you detect cycles, and how you handle cases where multiple valid orderings exist.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is basically topological sort dressed up as a scheduling problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by restating the problem as a topological sort on a directed graph, then present Kahn's algorithm (BFS-based) as your primary solution, clearly explaining how in-degree tracking and queue processing naturally detect cycles. Alternatively, mention DFS with recursion stack for cycle detection, and compare trade-offs between the two approaches.

Pro tip: Emphasize that Kahn's algorithm is often preferred in interviews because it detects cycles without extra state and produces a valid ordering in one pass; also note that if multiple valid orderings exist, any topological order is acceptable unless a specific tie-breaking rule is given.

1. Model the problem as a directed graph

Explain that tasks are nodes and prerequisite pairs (a, b) become directed edges b → a, since b must come before a. Clarify that a valid ordering is a topological sort, and a cycle means no such ordering exists.

2. Choose an algorithm and data structures

Present Kahn's algorithm: compute in-degrees for all nodes, use a queue to process nodes with in-degree 0, and build the ordering. Mention adjacency list representation for O(V+E) space and time.

3. Walk through the algorithm step-by-step

Detail: initialize in-degree array, enqueue all zero in-degree nodes, repeatedly dequeue a node, append to result, decrement in-degrees of its neighbors, and enqueue any that become zero. After processing, if result length < n, a cycle exists.

4. Analyze complexity and cycle detection

State time complexity O(V+E) and space O(V+E). Explain that cycle detection is inherent: if the queue empties before all nodes are processed, the remaining nodes form at least one cycle.

5. Address multiple valid orderings and edge cases

Note that any topological order is valid; if a specific order is required (e.g., lexicographically smallest), use a min-heap instead of a queue. Discuss edge cases: no prerequisites, disconnected components, and self-loops.

Key Points to Mention

Topological sorting is the core concept; both Kahn's algorithm (BFS) and DFS with recursion stack can solve it.
In-degree tracking and queue processing in Kahn's algorithm naturally detect cycles when not all nodes are processed.
Time and space complexity are O(V+E) for both approaches, where V is number of tasks and E is number of prerequisite pairs.
Multiple valid orderings exist when there are nodes with the same in-degree; any valid order is acceptable unless tie-breaking is specified.
Edge cases: empty input, no prerequisites, disconnected graph, and self-dependencies (cycles of length 1).
Trade-offs: Kahn's algorithm is iterative and avoids recursion depth issues; DFS can be more intuitive for some but requires explicit cycle detection with a recursion stack.

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