Detect cycles and break them in pod dependencies
Company: Together AI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given dependencies between software pods. Each dependency is a directed edge `u -> v` meaning **pod `u` must be built/installed before pod `v`**.
## Part 1: Detect whether a cycle exists
Given:
- `n`: number of pods (labeled `0..n-1`)
- `edges`: list of directed dependency pairs `(u, v)`
Return `true` if the dependency graph contains **any cycle** (i.e., it is impossible to build all pods), otherwise return `false`.
## Part 2: If there is a cycle, output an edge to remove
Using the same input format (directed edges), if the graph has a cycle, return **any single directed edge `(u, v)`** such that **removing that edge makes the graph acyclic**.
If the graph is already acyclic, return an empty result (e.g., `null` / `(-1, -1)` depending on your language).
### Notes / Assumptions
- There may be multiple valid edges to remove; returning any one is acceptable.
- You may assume there exists at least one edge whose removal can break all cycles (i.e., one-edge fix is possible).
### Example
Input: `n = 3`, `edges = [(0,1),(1,2),(2,1)]`
- Part 1 output: `true`
- Part 2 output: `(2,1)` (removing it breaks the cycle)
Quick Answer: This question evaluates proficiency with directed graph concepts and dependency resolution, focusing on cycle detection and selecting a single dependency edge whose removal renders the graph acyclic.
Part 1: Detect a Cycle in Pod Dependencies
You are given `n` software pods labeled `0` to `n - 1` and a list of directed dependencies `edges`, where `(u, v)` means pod `u` must be built before pod `v`.
Return `True` if the dependency graph contains at least one directed cycle. Return `False` if all pods can be built in some valid order.
Constraints
- 0 <= n <= 200000
- 0 <= len(edges) <= 300000
- 0 <= u, v < n for every edge (u, v)
Examples
Input: (4, [(0, 1), (1, 2), (2, 3)])
Expected Output: False
Explanation: The dependencies form a simple chain, so a valid build order exists: 0, 1, 2, 3.
Input: (3, [(0, 1), (1, 2), (2, 0)])
Expected Output: True
Explanation: Every pod depends on another in the cycle 0 -> 1 -> 2 -> 0, so no valid build order exists.
Hints
- A directed graph has no cycle if you can produce a full topological ordering.
- Try repeatedly removing nodes with indegree 0. What does it mean if some nodes are never removed?
Part 2: Remove One Dependency to Break All Cycles
You are given `n` software pods labeled `0` to `n - 1` and a list of directed dependencies `edges`, where `(u, v)` means pod `u` must be built before pod `v`.
Return any one directed edge `(u, v)` such that removing that single edge makes the entire graph acyclic.
If the graph is already acyclic, return `(-1, -1)`.
You may assume that if the graph contains a cycle, there exists at least one single edge whose removal breaks all cycles.
Constraints
- 0 <= n <= 2000
- 0 <= len(edges) <= 5000
- 0 <= u, v < n for every edge (u, v)
- If the graph contains cycles, at least one single-edge removal can make the graph acyclic
Examples
Input: (4, [(0, 1), (1, 2), (2, 3)])
Expected Output: True
Explanation: A simple chain has no cycle, so all pods can be built.
Input: (3, [(0, 1), (1, 2), (2, 1)])
Expected Output: False
Explanation: Pods 1 and 2 depend on each other, creating a cycle.
Hints
- Any valid edge to remove must belong to every cycle, so it must be on at least one cycle you detect.
- Find one cycle first, then try removing each edge on that cycle and test whether the remaining graph has a topological ordering.