Detect cycles and break them in pod dependencies

Q: Detect cycles and break them in pod dependencies

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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)

Detect cycles and break them in pod dependencies

Quick Overview

Part 1: Detect whether a cycle exists

Part 2: If there is a cycle, output an edge to remove

Notes / Assumptions

Example

Comments (0)