Notes

You work in Human Resources of a large company, and during a recent review, you come to
realize that some managers might seem underpaid. To ensure fairness, you come up with an
impartial rule:

A manager is underpaid if and only if their salary is less than the average
of the salaries of all their direct and indirect reports.

For example, consider the following:

A($100)
|
+- B($100)
+- C($200)
|
+- D($60)

Here A is underpaid, since the average salary of their reports is ($100+$200+$60) / 3 = $120 which is more than $100.

Question: Given an organization tree, return the count of underpaid managers.


1. Node
1. For each node
1. Go throught reports/children
1.

1. Node
1. The sum and count of all its children
1. BFS DFS or whatever


class Node(object):
def __init__(self, val: int):
super(Node, self).__init__()
self.val = val
self.reports = []

def __hash__(self) -> int:
pass

def count_reports(self):
queue = [i for i in self.reports]
visited = set()

def sum_reports(self):
pass






@functools.cache
def countsum(node) -> tuple:
queue = [node]
visited = set()

report_count = 0
salary_sum = 0

while len(queue) > 0:
current = queue.pop()

if current in visited:
continue

visited.add(current)
report_count += 1
salary_sum += current.val

for i in current.reports:
queue.append(i)

return report_count, salary_sum


A($100)
|
+- B($100)
+- C($200)
|
+- D($60)



def underpaid_count(node):
nodes = node.iter_nodes() # D, C, B, A
results = [(n, countsum(n)) for n in nodes] # D 1, 60
# C 2, 260
# B 1, 100
# A 4, 460

results = [(n, (count, summ) for n, v in nodes if count > 1]

i = 0
for node, (reports_count, salaries_sum) in zip(nodes, results):
count = reports_count - 1
summ = salaries_sum - node.val

if node.val < (summ / count): # 360/3 = 120
i += 1

return i


assert underpaid_count(A) == 1, 'Oops'