Build a Top-Down Reporting Forest from Employee-Manager Pairs
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
Input: pairs = [[10, 20]]
Output: [[20, 0], [10, 1]]
```
Overview: 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 `pairs`. 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: a list with one row `[id, depth]` per person, in the order the people appear in the chart.
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.
No input or output value exceeds 2^31 - 1: IDs are at most `10**9` and depths are at most `len(pairs) <= 10**5`, so 32-bit integers (`int` in Java and C++) are sufficient.
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]]
Explanation: `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]]
Explanation: `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`.
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)`.
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
Input: ([[2, 1], [3, 1], [4, 2], [5, 6]],)
Expected Output: [[1, 0], [2, 1], [4, 2], [3, 1], [6, 0], [5, 1]]
Explanation: Source Example 1: roots 1 and 6 in ascending order; the subtree of 2 precedes its sibling 3; tree 6 comes second although it contains 5.
Input: ([[9, 7], [7, 3], [4, 3]],)
Expected Output: [[3, 0], [4, 1], [7, 1], [9, 2]]
Explanation: Source Example 2: reports of 3 are listed by ID (4 before 7), not input order; 9 is two levels below 3.
Hints
- A top-level manager is anyone who appears in some pair but never as an employee, and the trees are listed in ascending order of that person's ID.
- Before listing anyone, gather each manager's direct reports so they can be visited in ascending ID order no matter how the pairs were ordered in the input.
- A single reporting chain can be as long as len(pairs), up to 10**5 levels, so consider how deep your traversal is allowed to go.