FastPrepValidate a Directed Graph
Problems/Validate a Directed Graph

Validate a Directed Graph

Shopify logoShopify● MediumINTERNOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The candidate reports writing a graph validator. The original validation rule and code are unavailable; this directed-cycle practice version matches the reported task at about 30%.

Return whether a graph is valid under the rule below.

For this exercise, assume validity means the directed graph contains no directed cycle. Vertices are numbered from 0 to n - 1, and each pair [u, v] in edges is an edge from u to v.

The graph may be disconnected. A self-loop is a cycle. Repeated copies of an edge are allowed and do not by themselves form a cycle. The empty graph is acyclic. Return true for an acyclic graph and false otherwise.

Function

isDirectedAcyclic(n: int, edges: int[][]) → boolean

Examples

Example 1

n = 4edges = [[0,1],[0,2],[2,3]]return = true

Every edge follows the order 0, 1, 2, 3: each source appears before its destination. No directed path can return to its starting vertex, so the graph is acyclic.

Example 2

n = 3edges = [[0,1],[1,2],[2,0]]return = false

The edges form the directed cycle 0 → 1 → 2 → 0, so the graph is invalid.

Constraints

  • 0 <= n <= 2000
  • 0 <= edges.length <= 10000
  • edges[i].length == 2
  • Every edge endpoint is an integer in [0, n). If n == 0, edges is empty.

More Shopify problems

  • Deterministic Secret Santa AssignmentPHONE SCREEN · Seen Oct 2026
  • Mars Rover Robot ControllerPHONE SCREEN · Seen Oct 2026
  • Choose Items for a BackpackOA · Seen May 2026
All Shopify interview questionsSee Shopify hiring insights
Saved
public boolean isDirectedAcyclic(int n, int[][] edges) {
    // Return whether the directed graph has no cycle.
}
Checking account…