Amazon·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

May 2026

Summary

Amazon SWE coding round, basically just one problem on topological sort and cycle detection. Nothing too wild but you need to know your graph fundamentals cold.

Questions Asked (1)

Given n tasks and a list of dependency pairs, determine whether all tasks can be completed without a cycle. Output YES if a valid ordering exists, NO if there's a cycle.

Algorithms & Data Structures

Author's notes

Classic course schedule / topological sort problem dressed up as task dependencies.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the tasks and dependencies as a directed graph, then detect cycles using either Kahn's algorithm (BFS-based topological sort) or DFS with recursion stack. If all tasks can be processed without encountering a cycle, output YES; otherwise, output NO.

Pro tip: Clarify edge cases upfront (e.g., duplicate edges, self-loops, disconnected components) and mention that Kahn's algorithm naturally handles them while providing a topological order if needed. Also, discuss time and space complexity to show thoroughness.

1. Understand the problem

Restate the problem: given n tasks and dependency pairs, determine if a valid ordering exists (i.e., the directed graph is acyclic). Confirm input/output format and constraints.

2. Choose an algorithm

Select between Kahn's algorithm (BFS-based topological sort) or DFS with cycle detection. Explain why one might be preferred (e.g., Kahn's gives topological order, DFS is simpler for cycle detection).

3. Implement the solution

Build the graph (adjacency list) and compute in-degrees (for Kahn's) or maintain visited/recursion stacks (for DFS). Process nodes accordingly and detect cycles.

4. Analyze complexity

State time complexity O(V+E) and space complexity O(V+E), where V is number of tasks and E is number of dependencies. Mention that both algorithms are optimal for this problem.

5. Test and validate

Walk through examples: acyclic graph (YES), cyclic graph (NO), disconnected components, self-loop, duplicate edges. Discuss edge cases and how the algorithm handles them.

Key Points to Mention

Directed graph representation: tasks as nodes, dependencies as directed edges.
Cycle detection via topological sorting (Kahn's algorithm) or DFS with recursion stack.
In-degree calculation and queue processing in Kahn's algorithm.
Time and space complexity: O(V+E) for both algorithms.
Handling edge cases: self-loops, duplicate edges, disconnected components.
Output format: YES if acyclic, NO if cyclic.

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