Katkat
Back

Detect cycles and break them in pod dependencies

Together AISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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)