Compute org height and minimal CEO promotions
Quick Overview
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.
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 tomanager[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
-
Compute the
maximum reporting layer
in the company (i.e., the tree height in levels): the maximum
level(v)over all employeesv. -
Given an integer threshold
h, deep reporting chains beyondhlayers are considered harmful. You may perform the following operation any number of times:
-
Choose any employee
x != 1and change their manager so thatxnow reports directly to the CEO (i.e., makemanager(x) = 1). The entire subtree ofxmoves 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, arraysmanager[],reportee[], and integerh. -
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.