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 Technical Screen rounds at Uber.

What role is this question designed for?

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

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.

Input: (1, [])

Expected Output: False

Explanation: A single node with no edges has no cycle.

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

Expected Output: True

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

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

Expected Output: False

Explanation: Two disjoint edges, no cycle in either component.

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

Expected Output: True

Explanation: The back edge 4 -> 1 closes the loop 1 -> 2 -> 3 -> 4 -> 1.

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

Expected Output: True

Explanation: A self-loop is a cycle.

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

Expected Output: False

Explanation: A DAG: two paths converge at 3 then continue to 5, no back edge.

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.

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

Expected Output: True

Explanation: First array gives a path, second array closes it into a cycle.

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

Expected Output: False

Explanation: Two disjoint edges across two arrays, no cycle.

Input: (2, [[], []])

Expected Output: False

Explanation: All arrays empty: no edges, no cycle.

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

Expected Output: True

Explanation: A self-loop in one array is a cycle.

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

Expected Output: True

Explanation: Edges spread across three arrays union into 0 -> 1 -> 2 -> 3 -> 4 -> 0.

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

Expected Output: False

Explanation: Union is the chain 0 -> 1 -> 2 -> 3, 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.

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