Compute org height and minimal CEO promotions
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given an organization chart with **n** employees labeled `1..n`. Employee `1` is the CEO (root).
The reporting relationships are given as two integer arrays `manager[]` and `reportee[]` of length `n-1`, where for each index `i`:
- `reportee[i]` reports directly to `manager[i]`
Assume these pairs form a valid **tree** rooted at the CEO.
Define an employee’s **reporting layer** (level) as their distance from the CEO in nodes, with:
- `level(1) = 1` (CEO)
- each direct report of the CEO has level `2`, etc.
### Task
1. Compute the **maximum reporting layer** in the company (i.e., the tree height in levels): the maximum `level(v)` over all employees `v`.
2. Given an integer threshold `h`, deep reporting chains beyond `h` layers are considered harmful. You may perform the following operation any number of times:
- Choose any employee `x != 1` and change their manager so that `x` now **reports directly to the CEO** (i.e., make `manager(x) = 1`). The entire subtree of `x` moves with them.
Return the **minimum number of such moves** required so that in the resulting org chart, the maximum reporting layer is **≤ h**.
### Input/Output requirements
- **Input:** `n`, arrays `manager[]`, `reportee[]`, and integer `h`.
- **Output:**
- The original maximum reporting layer (height).
- The minimum number of moves to make the final height ≤ `h`.
### Notes / Assumptions
- The given relationships form a connected rooted tree with root `1`.
- Clarify in your solution whether you treat “height” as number of nodes on the longest root-to-leaf path (levels, as defined above) rather than number of edges.
Quick Answer: This question evaluates understanding of rooted tree data structures, computation of tree height (reporting layers), and algorithmic manipulation of subtrees to minimize maximum depth, testing skills in tree traversal, depth calculation, and constrained optimization.
Part 1: Maximum Reporting Layer in an Org Tree
You are given an organization chart with employees labeled 1..n, where employee 1 is the CEO. The arrays manager and reportee each have length n-1, and reportee[i] reports directly to manager[i]. These relationships form a valid rooted tree. Define reporting layer as the number of nodes on the path from the CEO: level(1) = 1, direct reports of the CEO are at level 2, and so on. Compute the maximum reporting layer in the company. In this problem, height is measured in levels (nodes), not edges.
Constraints
- 1 <= n <= 100000
- len(manager) == len(reportee) == n - 1
- Employees are labeled from 1 to n
- Employee 1 is the root (CEO)
- The given relationships form a valid connected tree
Examples
Input: (1, [], [])
Expected Output:
Explanation: Only the CEO exists, so the maximum layer is 1.
Input: (5, [1, 2, 3, 4], [2, 3, 4, 5])
Expected Output:
Explanation: This is a chain 1 -> 2 -> 3 -> 4 -> 5, so the deepest level is 5.
Input: (7, [1, 1, 2, 2, 3, 3], [2, 3, 4, 5, 6, 7])
Expected Output:
Explanation: A balanced tree with CEO at level 1, managers at level 2, and leaves at level 3.
Input: (6, [3, 1, 2, 1, 4], [6, 2, 4, 3, 5])
Expected Output:
Explanation: The deepest path is 1 -> 2 -> 4 -> 5, which has 4 levels.
Hints
- Build a children adjacency list from manager -> reportee.
- Run a BFS or DFS from employee 1 while tracking each node's level.
Part 2: Minimum CEO Promotions to Limit Org Height
You are given the same organization tree: employees are labeled 1..n, employee 1 is the CEO, and reportee[i] reports directly to manager[i]. The tree is valid and rooted at employee 1. The reporting layer is defined in levels: level(1) = 1, direct reports are level 2, and so on. You are also given an integer h. If the organization has reporting chains deeper than h levels, you may repeatedly perform this operation: choose any employee x != 1 and make x report directly to the CEO. The entire subtree of x moves with them. Return the minimum number of such moves needed so that the final maximum reporting layer is at most h. If this is impossible, return -1. (This only happens when h = 1 and n > 1, because no non-CEO employee can ever be moved to level 1.)
Constraints
- 1 <= n <= 100000
- len(manager) == len(reportee) == n - 1
- 1 <= h <= n
- Employees are labeled from 1 to n
- Employee 1 is the root (CEO)
- The given relationships form a valid connected tree
Examples
Input: (1, [], [], 1)
Expected Output:
Explanation: A single CEO already has height 1, so no moves are needed.
Input: (5, [1, 2, 3, 4], [2, 3, 4, 5], 3)
Expected Output:
Explanation: Move employee 4 directly under the CEO. Then the deepest level becomes 3.
Input: (7, [1, 2, 3, 4, 5, 6], [2, 3, 4, 5, 6, 7], 3)
Expected Output:
Explanation: For the chain of 7 employees, two promotions are required to break it into short enough segments.
Input: (5, [1, 2, 3, 3], [2, 3, 4, 5], 3)
Expected Output:
Explanation: Promoting employee 3 to report to the CEO makes both employees 4 and 5 end up within 3 levels.
Input: (2, [1], [2], 1)
Expected Output:
Explanation: With h = 1, only the CEO can be at level 1. Employee 2 can never be moved to level 1.
Hints
- Process employees from deepest to shallowest. If a node is already handled by an earlier move, skip it.
- For a node deeper than h, the highest employee you can move while still fixing that node is its ancestor exactly h-2 steps above it.