Amazon·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Amazon ML engineer phone screen, one algorithmic problem the whole time. The question was about cycle detection in a directed graph and they wanted near-linear complexity. Pretty standard graph theory but the constraints made it interesting.

Questions Asked (1)

You have a directed acyclic graph with n nodes and a list of existing edges. Given a candidate new directed edge, write a function that returns true if adding it keeps the graph acyclic, or false if it introduces a cycle. Your solution should run in close to linear time given up to 100k nodes and edges.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was just 'run a full topological sort after adding the edge' which technically works but I second-guessed myself on whether that was efficient enough.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Precompute a topological ordering of the existing DAG, then for each candidate edge (u, v), check if u is reachable from v in the current graph. If so, adding (u, v) would create a cycle; otherwise, it's safe. Use DFS or BFS for reachability, but optimize by leveraging the topological order to prune searches.

Pro tip: Mention that you can precompute transitive closure or use bitsets for dense graphs, but for sparse graphs with 100k nodes, a single DFS per query is efficient. Also, note that if multiple queries are expected, you can precompute reachability using topological order and bitsets for O(n^2/64) time, but for a single query, O(n+m) is optimal.

1. Clarify the problem and constraints

Confirm that the graph is a DAG, the edge is directed, and we need to check if adding it creates a cycle. Ask about the number of queries (single vs multiple) and memory constraints.

2. Choose the right algorithm

For a single query, perform a DFS/BFS from v to see if u is reachable. If yes, adding (u, v) creates a cycle. For multiple queries, precompute reachability using topological order and bitsets or transitive closure.

3. Implement efficiently

Use iterative DFS to avoid recursion depth issues. If using topological order, process nodes in reverse topological order to compute reachability sets efficiently.

4. Analyze time and space complexity

For single query: O(n+m) time, O(n) space. For multiple queries: O(n^2/64) time with bitsets, O(n^2/64) space. Discuss trade-offs.

5. Test with edge cases

Test with self-loop (u==v), edge already exists, edge from node to itself, and large graphs to ensure performance.

Key Points to Mention

Cycle detection in directed graphs using DFS (back edge detection) or topological sorting.
Reachability check: adding edge (u, v) creates a cycle iff there is a path from v to u.
Topological ordering can be used to prune reachability searches or precompute reachability.
Time complexity: O(n+m) for single query, O(n^2/64) for multiple queries with bitsets.
Space complexity: O(n) for single query, O(n^2/64) for bitset approach.
Trade-offs between precomputation and query time, especially for large graphs.

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