Detect cycle in directed dependency graph
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a directed dependency graph representing services in a system.
- There are `n` services, labeled from `0` to `n - 1`.
- You are given a list of directed edges `dependencies`, where each element is a pair `[a, b]` meaning **service `a` depends on service `b`** (i.e., there is a directed edge `a -> b`).
Assume:
- `1 <= n <= 10^5`
- `0 <= a, b < n`
- There may be zero or more edges.
**Task:**
1. Implement a function that determines whether there is at least one cycle in this directed graph.
- Return `true` if there is a cycle.
- Return `false` otherwise.
2. Follow-up: Now you are given **multiple dependency arrays** instead of just one. Each array represents an additional list of edges on the same set of services. For example:
- `dependencies1`, `dependencies2`, ..., `dependenciesk`
Each `dependenciesi` is a list of `[a, b]` pairs as defined above. Treat the union of all these edges as a single directed graph and determine whether this combined graph contains any cycle.
Describe the approach, data structures, and algorithm you would use, and analyze the time and space complexity.
Overview: This question evaluates understanding of graph theory and algorithmic problem-solving, specifically cycle detection in directed dependency graphs and the ability to reason about combined edge sets across multiple dependency arrays.
Detect a Cycle in a Directed Dependency Graph
You are given a directed dependency graph representing services in a system.
- There are `n` services, labeled from `0` to `n - 1`.
- You are given a list of directed edges `dependencies`, where each element is a pair `[a, b]` meaning **service `a` depends on service `b`** (a directed edge `a -> b`).
**Task:** Implement a function that determines whether the graph contains at least one cycle. Return `true` if there is a cycle, otherwise return `false`.
A cycle means a chain of dependencies that loops back on itself (e.g. `a -> b -> c -> a`), which would make the services impossible to start in a valid order. A self-dependency `[a, a]` counts as a cycle.
**Function signature:** `solution(n, dependencies)` where `n` is the number of services and `dependencies` is a list of `[a, b]` pairs.
**Constraints:**
- `1 <= n <= 10^5`
- `0 <= a, b < n`
- There may be zero or more edges.
Constraints
- 1 <= n <= 10^5
- 0 <= a, b < n
- There may be zero or more edges.
- A self-loop [a, a] is considered a cycle.
Examples
Input: (3, [[0, 1], [1, 2], [2, 0]])
Expected Output: True
Explanation: 0 -> 1 -> 2 -> 0 forms a cycle.
Input: (3, [[0, 1], [1, 2]])
Expected Output: False
Explanation: A simple chain 0 -> 1 -> 2 has no cycle.
Hints
- A directed graph has a cycle if and only if a DFS encounters a 'back edge' — an edge that points to a node currently on the DFS recursion stack.
- Track three states per node: unvisited, currently-on-stack (gray), and fully-processed (black). Seeing a gray neighbor means a cycle.
- Because n can be up to 10^5, prefer an explicit (iterative) stack over deep recursion to avoid stack-overflow on long chains.
- Don't forget disconnected components: start a DFS from every node that is still unvisited.
Detect a Cycle in the Union of Multiple Dependency Arrays
Follow-up to the single-graph cycle detection problem.
Now, instead of a single list of edges, you are given **multiple dependency arrays** over the same `n` services: `dependencies1, dependencies2, ..., dependenciesk`. Each `dependenciesi` is a list of `[a, b]` pairs meaning service `a` depends on service `b` (`a -> b`).
**Task:** Treat the **union of all edges** across every array as one combined directed graph, and determine whether that combined graph contains any cycle. Return `true` if the union has a cycle, otherwise `false`.
The key insight is that no single array needs to contain a cycle on its own — the cycle can emerge only once the edges are merged (e.g. one array supplies `a -> b` and another supplies `b -> a`).
**Function signature:** `solution(n, dependency_arrays)` where `dependency_arrays` is a list of edge lists; each edge list is a list of `[a, b]` pairs.
**Constraints:**
- `1 <= n <= 10^5`
- `0 <= a, b < n`
- Each array may have zero or more edges; there may be zero or more arrays.
Constraints
- 1 <= n <= 10^5
- 0 <= a, b < n
- Each array may have zero or more edges; there may be zero or more arrays.
- A cycle can span edges contributed by different arrays.
Examples
Input: (3, [[[0, 1]], [[1, 2]], [[2, 0]]])
Expected Output: True
Explanation: Three arrays each supply one edge; their union 0 -> 1 -> 2 -> 0 is a cycle.
Input: (3, [[[0, 1]], [[1, 2]]])
Expected Output: False
Explanation: Union is the chain 0 -> 1 -> 2, no cycle.
Hints
- You do not need to detect a cycle per array. Merge every edge from every array into one shared adjacency list, then run a single cycle-detection pass.
- Reuse the same 3-color DFS from the single-graph version — the only change is how you populate the adjacency list.
- Watch for cycles that only appear after merging: array 1 gives a -> b and array 2 gives b -> a; neither alone has a cycle, the union does.
- Total work is O(n + E) where E is the combined edge count; iterating over arrays first does not change the asymptotic cost.