Given a company tree, calculate how many managers are paid less than the average salary of their direct and indirect employees?
For example, consider the following:
A($100)
|
+- B($100)
+- C($200)
|
+- D($60)Here there are two managers, A and C. A should be counted since the average salary of their employees is ($100 + $200 + $60) / 3 = $120, which is more than $100. C should not be counted because their salary is $200, which is more than the average salary of their employees, that is $60.
Followup question: Now that you’ve identified underpaid managers, we want to make sure that they are paid fairly. Given an org tree, find out the minimum amount of extra salary needed to make sure that no one is underpaid.
This problem asks you to count managers whose salary is lower than the average salary of all their direct and indirect subordinates. A natural solution is a postorder DFS that returns the total salary and employee count for each subtree, then checks whether the current manager is underpaid. The follow-up extends this tree aggregation idea to compute the minimum additional salary needed so that every manager is paid fairly.
