Analyze Underpaid Managers in a Salary Tree
Google● HardNEW GRADPHONE SCREENProblem statement
A company hierarchy is a rooted tree. parent[i] is the direct manager of employee i, or -1 for the root. salary[i] is the employee's positive integer salary.
For every manager with at least one direct or indirect report, compare the manager's salary with all descendants:
- Count managers whose salary is strictly below the arithmetic mean of their descendants' original salaries.
- Compute the minimum total integer salary increase needed so that no manager is below the mean of descendants' final salaries. Salaries may only increase. Leaves remain unchanged.
- Count managers whose salary is strictly below the median of their descendants' original salaries. For an even descendant count, the median is the average of the two middle values.
Return these three results as [meanCount, minimumBudget, medianCount].
Function
analyzeManagerSalaries(parent: int[], salary: int[]) → long[]Examples
Example 1
parent = [-1,0,0]salary = [50,60,80]return = [1,20,1]The root's descendant mean and median are both 70, so it needs a raise from 50 to 70.
Example 2
parent = [-1,0,1,1]salary = [10,10,30,50]return = [2,60,2]Manager 1 rises from 10 to 40. The root's final descendants are then 40, 30, and 50, so the root also rises from 10 to 40. The total budget is 60.
Example 3
parent = [-1,0,0,1]salary = [100,80,60,40]return = [0,0,0]No manager is below either descendant statistic, and no raise is needed.
Constraints
1 <= parent.length = salary.length <= 200.- Exactly one entry of
parentis-1; all other entries form one rooted tree. 1 <= salary[i] <= 10^9.- The final budget fits a signed 64-bit integer.