[Google Coding Question] How many Managers are Paid Less than the Average Salary

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

Problem statement:

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.

Python Code

"""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

Code Explanation:

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!

Aniruddha Chaudhari

I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.