Adobe·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Adobe coding round focused entirely on task scheduling with dependency graphs. Pretty classic topological sort territory but they pushed hard on complexity analysis and edge case behavior, which is where things got interesting.

Questions Asked (1)

Given n tasks labeled 0 to n-1 and a list of dependency pairs where (a, b) means task a depends on task b, write a function to determine if all tasks can be completed, and if so, return a valid execution order.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew this was topological sort pretty much immediately, but I fumbled the cycle detection explanation for a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the tasks and dependencies as a directed graph and use topological sorting to detect cycles and produce a valid order. Explain both Kahn's algorithm (BFS) and DFS-based approaches, then implement one with clear time and space complexity analysis.

Pro tip: Mention that you would clarify edge cases upfront, such as duplicate dependencies, self-loops, or disconnected components, and discuss how to handle them. This shows attention to detail and production readiness.

1. Clarify the problem and edge cases

Ask about input constraints (e.g., n size, duplicate edges, self-dependencies) and confirm that a valid order must include all tasks. Discuss what to return if no valid order exists.

2. Model as a directed graph

Represent tasks as nodes and dependencies as directed edges from b to a (since a depends on b). Explain that a cycle indicates impossibility.

3. Choose a topological sort algorithm

Describe Kahn's algorithm using in-degree counts and a queue, or DFS with cycle detection. Compare trade-offs: Kahn's is iterative and easy to reason about; DFS can be more concise but recursion depth may be a concern.

4. Implement and analyze complexity

Write clean code for the chosen algorithm, ensuring O(n + e) time and O(n + e) space. Walk through a small example to verify correctness.

5. Discuss extensions and trade-offs

Mention how to handle large graphs (e.g., iterative DFS to avoid stack overflow), parallel execution possibilities, or detecting all cycles if needed.

Key Points to Mention

Topological sorting is the core concept; a valid order exists if and only if the graph is a DAG.
Kahn's algorithm: compute in-degrees, enqueue nodes with in-degree 0, process and decrement neighbors' in-degrees.
DFS approach: use recursion with a visiting state to detect cycles and build the order in post-order.
Time and space complexity: O(n + e) for both algorithms, where n is number of tasks and e is number of dependencies.
Edge cases: empty input, duplicate edges, self-loops, disconnected components, and multiple valid orders.
Trade-offs: Kahn's algorithm naturally detects cycles and is iterative; DFS may be simpler but risks stack overflow for large graphs.

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