Katkat
Back

Build a Top-Down Reporting Forest from Employee-Manager Pairs

SnowflakeSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Given employee-to-manager pairs of integer IDs, build the top-down reporting forest with every top-level manager as a root, and return it as a preorder listing of IDs and depths. Tests finding the roots, building child lists, deterministic sibling ordering, and handling long reporting chains.

You are given a list of reporting relationships. Each person is identified by a positive integer ID, and each pair [employee, manager] means that employee reports directly to manager. Build the reporting structure top-down: every top-level manager, who reports to no one, is the root of a tree, with middle managers below them and employees below those. Together the trees form a forest.

Return the forest as an indented org-chart listing: one row [id, depth] per person, in the order the people appear in the chart.

Function Signature

def reporting_forest(pairs: list[list[int]]) -> list[list[int]]:

Rules

  • A top-level manager is a person who appears in at least one pair but never as the employee of a pair. A top-level manager has depth 0; every other person has the depth of their manager plus 1.
  • Every person who appears in any pair appears in the output exactly once.
  • Order the output as a preorder walk. List the trees in ascending order of their top-level manager's ID. Within a tree, list a person, then the whole subtree of each of their direct reports, taking direct reports in ascending order of ID.
  • Each output row is a two-element list [id, depth] of integers.

Constraints

  • 1 <= len(pairs) <= 10**5
  • Each pair has exactly two elements, and 1 <= employee, manager <= 10**9.
  • In each pair, employee != manager.
  • Each person appears as the employee in at most one pair, so everyone has at most one direct manager.
  • The relationships contain no cycle: following managers upward from anyone always reaches a top-level manager.
  • A reporting chain can be as long as len(pairs), so depths range from 0 to len(pairs).

Examples

Example 1

Input: pairs = [[2, 1], [3, 1], [4, 2], [5, 6]]
Output: [[1, 0], [2, 1], [4, 2], [3, 1], [6, 0], [5, 1]]

1 and 6 never appear as employees, so they are the two roots, in ascending order. The direct reports of 1 are 2 and 3, and the whole subtree of 2 (2, then 4) comes before 3. The tree rooted at 6 comes second even though it contains 5, because trees are ordered by the ID of their root.

Example 2

Input: pairs = [[9, 7], [7, 3], [4, 3]]
Output: [[3, 0], [4, 1], [7, 1], [9, 2]]

3 is the only top-level manager. Its direct reports are ordered by ID (4 before 7), not by input order, and 9 sits two levels below 3.

Example 3

Input: pairs = [[10, 20]]
Output: [[20, 0], [10, 1]]