Circular Dependency Check

10pts
Google

Problem Statement

In a healthy corporate hierarchy, the reporting structure should form a directed acyclic graph (DAG). However, data entry errors can lead to circular dependencies—where Employee A reports to Employee B, who reports to Employee C, who eventually reports back to Employee A.

Write a query to identify all employees who are part of such a circular chain. An employee is considered part of a circular dependency if they appear anywhere within a reporting loop.

Rules:

  • Output column: employee_id.
  • Result must be sorted in ascending order.
  • A circular dependency can involve any number of employees (minimum 2).
  • The top-level CEO typically has a null manager_id, but in a cycle, no one may have a null manager_id in that specific loop.
Tests your understanding of
Recursive CTE, Graph Theory and Hierarchical Data

Input Tables

employees
employee_id(INTEGER)full_name(VARCHAR)manager_id(INTEGER)
1Sundarnull
2Ruth1
3Thomas2
4Prabhakar3
5Demis4
3Thomas5
10Jeff11
11Sanjay10

Expected Output

employee_id(INTEGER)
3
4
5
10
11

Tags

HardRecursive CTEGraph TheoryHierarchical Data
45-60 min
28%

Hints