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.
Quick Answer: 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.