Employee Reporting: Build an Org Chart Query System for Hierarchical Reporting Structures
Question Details
Round 1 Coding
Problem
Given a list of (employee_id, manager_id) pairs representing a company hierarchy, implement queries to find: direct reports, all reports in the subtree, the management chain to the root, and the lowest common manager of two employees.
python
class OrgChart:
def __init__(self, reports: list[tuple[int, int]]):
# reports: (employee_id, manager_id); root has manager_id = -1
...
def direct_reports(self, emp_id: int) -> list[int]:
...
def all_reports(self, emp_id: int) -> list[int]: # entire subtree
...
def management_chain(self, emp_id: int) -> list[int]: # emp -> root
...
def lowest_common_manager(self, emp1: int, emp2: int) -> int:
...
Example
reports = [(2,1),(3,1),(4,2),(5,2),(6,3)]
chart = OrgChart(reports)
chart.direct_reports(1) -> [2, 3]
chart.all_reports(2) -> [4, 5]
chart.management_chain(5) -> [5, 2, 1]
chart.lowest_common_manager(4, 6) -> 1
Follow-ups
- What is the time complexity of
lowest_common_manager? How can you optimize it with preprocessing? - How would you handle an employee who reports to multiple managers (matrix org structure)?
- How do you detect cycles in the reporting structure (e.g., employee A reports to B who reports to A)?
- How would you store this hierarchy in a relational database and write a recursive CTE to fetch the full subtree?
Full Details
Round 1 Coding
Problem
Given a list of (employee_id, manager_id) pairs representing a company hierarchy, implement queries to find: direct reports, all reports in the subtree, the management chain to the root, and the lowest common manager of two employees.
python
class OrgChart:
def __init__(self, reports: list[tuple[int, int]]):
# reports: (employee_id, manager_id); root has manager_id = -1
...
def direct_reports(self, emp_id: int) -> list[int]:
...
def all_reports(self, emp_id: int) -> list[int]: # entire subtree
...
def management_chain(self, emp_id: int) -> list[int]: # emp -> root
...
def lowest_common_manager(self, emp1: int, emp2: int) -> int:
...
Example
reports = [(2,1),(3,1),(4,2),(5,2),(6,3)]
chart = OrgChart(reports)
chart.direct_reports(1) -> [2, 3]
chart.all_reports(2) -> [4, 5]
chart.management_chain(5) -> [5, 2, 1]
chart.lowest_common_manager(4, 6) -> 1
Follow-ups
- What is the time complexity of
lowest_common_manager? How can you optimize it with preprocessing? - How would you handle an employee who reports to multiple managers (matrix org structure)?
- How do you detect cycles in the reporting structure (e.g., employee A reports to B who reports to A)?
- How would you store this hierarchy in a relational database and write a recursive CTE to fetch the full subtree?
About This Question
This is a reported interview question from a patreon interview during the phone round.
It covers the following topics: Phone, Sql, Recursion, Coding, Matrix .