How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Detect cycle in a directed graph | Amazon Coding Question

Detect cycle in a directed graph

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a directed graph represented by an adjacency list with n vertices and m edges, determine whether the graph contains a cycle. Describe and implement an algorithm that returns true if a cycle exists and false otherwise. Explain the time and space complexity, and discuss both a DFS-based approach using a recursion stack and an approach based on Kahn’s topological sort.

Quick Answer: This question evaluates mastery of graph algorithms and graph theory concepts—specifically directed cycle detection—and assesses the ability to reason about algorithmic correctness and to analyze time and space complexity for competing approaches.

Given a directed graph with `n` vertices labeled `0` to `n-1` and a list of directed `edges` where each edge `[u, v]` means there is a directed edge from `u` to `v`, determine whether the graph contains a cycle. Return `true` if at least one directed cycle exists, and `false` otherwise. A directed cycle is a path `v0 -> v1 -> ... -> vk -> v0` of length at least 1 that follows edge directions and returns to its starting vertex. Note that a self-loop (an edge `[u, u]`) counts as a cycle. **Approach.** The canonical solution is a DFS that colors each vertex WHITE (unvisited), GRAY (on the current recursion stack), or BLACK (fully explored). A cycle exists iff a DFS encounters an edge to a GRAY vertex — a *back edge* into an ancestor still on the stack. An equivalent alternative is Kahn's algorithm (BFS topological sort): repeatedly remove vertices with in-degree 0; if fewer than `n` vertices get removed, the leftover vertices form a cycle. **Example 1:** ``` Input: n = 4, edges = [[0,1],[1,2],[2,3],[3,1]] Output: true Explanation: 1 -> 2 -> 3 -> 1 forms a cycle. ``` **Example 2:** ``` Input: n = 4, edges = [[0,1],[1,2],[2,3]] Output: false Explanation: The graph is a simple chain (DAG); no cycle. ``` **Example 3:** ``` Input: n = 1, edges = [[0,0]] Output: true Explanation: The self-loop at vertex 0 is a cycle. ```

Constraints

0 <= n <= 10^4
0 <= m <= 10^5 (m = number of edges)
Each edge is [u, v] with 0 <= u, v < n
Self-loops (u == v) are allowed and count as a cycle
Parallel/duplicate edges may appear

Examples

Input: (4, [[0, 1], [1, 2], [2, 3], [3, 1]])

Expected Output: True

Explanation: 1 -> 2 -> 3 -> 1 is a back edge into the current DFS stack, so a cycle exists.

Input: (4, [[0, 1], [1, 2], [2, 3]])

Expected Output: False

Explanation: A straight chain 0->1->2->3 is a DAG; no back edge is ever found.

Input: (0, [])

Expected Output: False

Explanation: An empty graph (no vertices) trivially has no cycle.

Input: (1, [[0, 0]])

Expected Output: True

Explanation: A self-loop at vertex 0 is a cycle: the DFS sees an edge from 0 back to the GRAY node 0.

Input: (3, [[0, 1], [1, 2], [2, 0]])

Expected Output: True

Explanation: 0 -> 1 -> 2 -> 0 is a 3-cycle.

Input: (2, [])

Expected Output: False

Explanation: Two isolated vertices with no edges have no cycle.

Input: (6, [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [4, 5]])

Expected Output: False

Explanation: A diamond into vertex 3 then a tail; vertex 3 having two parents does not create a cycle, it stays a DAG.

Input: (5, [[0, 1], [1, 2], [3, 4], [4, 3]])

Expected Output: True

Explanation: The component {0,1,2} is acyclic, but the separate component {3,4} has 3 -> 4 -> 3; scanning all WHITE start vertices finds it.

Hints

A directed graph has a cycle iff a DFS finds a back edge — an edge pointing to a vertex that is currently on the recursion stack (still being explored).
Three-color the vertices: WHITE = unvisited, GRAY = in progress (on the stack), BLACK = finished. Seeing an edge to a GRAY vertex means a cycle.
Start a DFS from every WHITE vertex so disconnected components are all covered. Don't restart from BLACK vertices.
Alternative: Kahn's topological sort. Compute in-degrees, repeatedly pop vertices with in-degree 0; if you can't process all n vertices, the remainder contains a cycle.
Remember the self-loop edge cases: [u, u] is a cycle by itself.

Quick Overview

This question evaluates mastery of graph algorithms and graph theory concepts—specifically directed cycle detection—and assesses the ability to reason about algorithmic correctness and to analyze time and space complexity for competing approaches.