Note: This coding challenge was asked to me in the Google coding interview round. You have 45 minutes to solve this coding problem.

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, which is $60.

You can choose any programming language of your choice. I choose Python.

"""Employee node""" class NodeEmp: def __init__(self, salary, ptrs=[]): self.salary = salary self.ptrs = ptrs self.emp_sum = 0 self.emp_count = 0 """Initialize employee data""" emp = NodeEmp(110, [ NodeEmp(100), NodeEmp(200, [NodeEmp(60)]) ] ) """Initialize less paid manager count""" count = 0 """Calculate salary sum and number of employees""" def count_salary(root): emp_sum = 0 emp_count = 0 if root.ptrs: for i in root.ptrs: emp_sum += (i.emp_sum + i.salary) emp_count += (i.emp_count+1) return emp_sum, emp_count """Traverse all employees""" def traverse(root): if root: for i in root.ptrs: traverse(i) print(f"Emp salary: {root.salary}") root.emp_sum, root.emp_count = count_salary(root) print(f"emp_sum: {root.emp_sum} emp_count:{root.emp_count}") if root.emp_count: avg = root.emp_sum/root.emp_count print(f"avg : {avg}") if root.salary < avg: global count print("count") count += 1 print() traverse(emp) print(f"Number of less paid managers: {count}")

**Output:**

Emp salary: 100 emp_sum: 0 emp_count:0 Emp salary: 60 emp_sum: 0 emp_count:0 Emp salary: 200 emp_sum: 60 emp_count:1 avg : 60.0 Emp salary: 110 emp_sum: 360 emp_count:3 avg : 120.0 count Number of less paid managers: 1

This code defines a Python class `NodeEmp`

to represent a node in an employee salary hierarchy. The hierarchy is structured as a tree where each node can have multiple child nodes, and each node represents an employee with a salary.

The goal of the code is to count the number of managers (nodes) whose salary is less than the average salary of their direct subordinates (employees).

Let’s break down the logic of the code.

**NodeEmp Class:**

Here we are implementing the tree (not the binary tree) as there can be multiple subordinates aka employees of the managers.

Each instance of the NodeEmp class represents a node in the employee hierarchy. It has attributes:

`salary`

: the salary of the current employee or manager.`ptrs`

: a list of pointers to child nodes (subordinates).`emp_sum`

: the sum of salaries of the current node and its subordinates.`emp_count`

: the count of employees (including the current node and its subordinates).’

**Creating Example Hierarchy (emp):**

- An example hierarchy is created with a top-level manager (emp) with a salary of 110.
- This manager has two direct subordinates: one with a salary of 100, another with a salary of 200, and a subordinate with a salary of 60.

**Counting Salary and Employee Count (count_salary function):**

- The
`count_salary`

function takes a node as an argument and iterates through its child nodes. - For each child node, it adds the child’s
`emp_sum`

and salary to the total`emp_sum`

and increments the total`emp_count`

. - This function is used to calculate the sum of salaries (
`emp_sum`

) and the count of employees (`emp_count`

) for a given node and its subordinates.

**Traversing the Hierarchy ( traverse function):**

The `traverse`

function recursively traverses the employee hierarchy starting from the given node.

For each node, it calls the `traverse`

function on its child nodes and then prints information about the current node:

- The employee’s salary.
- The sum of salaries (
`emp_sum`

) and the count of employees (`emp_count`

) calculated using`count_salary`

. - If the current manager has at least one subordinate, it calculates the average salary (
`avg`

) of its subordinates and compares it with the manager’s salary. - If the manager’s salary is less than the average, it increments the global variable
`count`

.

**Printing the Result:**

After the traversal, the code prints the total number of managers whose salary is less than the average salary of their subordinates (`count`

).

**Summary:**

The code traverses a hierarchical structure of employees and managers, calculates statistics (sum of salaries, count of employees), and checks if each manager’s salary is less than the average salary of their subordinates, incrementing a counter (count) accordingly.

The final count represents the number of managers meeting this condition in the hierarchy.

There can be many other ways to solve this coding problem. If you have any better or optimized solution, let me know in the comment section below. If you have any questions or thoughts about the solution provided here, you can ask me.

All the best!