Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Example
3.
Approach and Ideology
4.
Approach Explanation
5.
Code in C++💻
6.
Code in Java💻
7.
Code in Python💻
8.
Frequently Asked Questions
8.1.
What is the Space Complexity of a Hash Table?
8.2.
What is Hash Collision?
8.3.
What is the Time complexity of Hash Table?
8.4.
What is Hash value?
8.5.
How is the hash function useful for lookups?
9.
Conclusion
Last Updated: Mar 27, 2024
Hard

Find Number of Employees Under Every Manager

Author Gaurav Bashisht
3 upvotes
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

“Find number of employees under every manager” is a popular Hashing problem. In which we need to find all the employees details who directly or indirectly report to any particular manager.

Find Number of Employees Under Every Manager

In this problem, we have a dictionary in which manager-employee pairs are given, in which the first one is an employee and the second one is the manager.

Example

Let's Understand this with an example:

Find Number of Employees Under Every Manager

In this example, P is the Head Manager of the company and is the manager of employees Q and R and Q is the manager of S, and T, whereas U reports to manager R and S, T, and U doesn't have any employees under them.

Now we need to write a function to find number of employees under every manager:

Find Number of Employees Under Every Manager
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach and Ideology

“Find number of employees under every manager” problem can be solved in so many ways, but most of the ways either take a long time or take up a larger space. The approach which is given below might be the best approach to solve this problem.

  1. Declare a reverse map: Manager->DirectReportingEmployee. 
    Data type of List will be String because  manager to employee relation will be one to many
    "Q"  "S", "T",
    "R"  "U" 
    "P"  "P", "Q", "R", “S”, “T”, “U”
     
  2. Iterate employee-manager map to and concurrently use a newly declared reverse map to find the number of employees under every particular manager.
     
  3. Let the map generated by step 2 be 'ManagerEmpMap'
    Do the following for every employee.

    1. If 'employee’ is not available in 'ManagerEmpMap' 
      Total count under 'employee' is 0 [i.e., “Nobody reports to employee”]
       
    2. If 'employee' is available in 'ManagerEmpMap' 
      Use direct report list from map 'ManagerEmpMap' and using loop iteration count the total number of employee under 'employee'.

Approach Explanation

Here is a stepwise explanation of the algorithm.

Step 1

We have given an Employee-Manager map above, and we will declare a reverse map: Manager-Employee.

Find Number of Employees Under Every Manager

Step 2

Now we will iterate the employee-manager map and put the data as the manager-number of employees directly reporting to them in a newly declared reverse map named ManagerEmpMap.

Find Number of Employees Under Every Manager

Step 3

Now in the third step, we will check if the employee is available in the ManagerEmpMap or not for every employee:

  • If not: it means no employee reports to that particular employee.
Find Number of Employees Under Every Manager
  • If yes: It means the employee is the manager, and other employees directly report them.
Find Number of Employees Under Every Manager

Using a loop, we will iterate the direct reporting list of ManagerEmpMap to find the total number of employees reporting to managers directly or indirectly.

Find Number of Employees Under Every Manager

Code in C++💻

C++ Program to find number of employees under every manager using hashing methods.

#include <bits/stdc++.h>
using namespace std;

int populateResUtil(string manager, unordered_map<string, vector<string> > ManagerEmpMap, map<string, int>& Output)
{
	int total = 0;
	if (ManagerEmpMap.find(manager) == ManagerEmpMap.end()) {
		Output.insert({ manager, 0 });
		return 0;
	}
	else if (Output.find(manager) != Output.end()) {
		total = Output[manager];
	}
	else {
		vector<string> directReportingEmpList = ManagerEmpMap[manager];
		total = directReportingEmpList.size();
		for (int i = 0; i < directReportingEmpList.size(); i++) {
			total += populateResUtil(directReportingEmpList[i], ManagerEmpMap, Output);
		}
		Output.insert({ manager, total });
	}
	return total;
}

void populateRes(unordered_map<string, string> meset)
{
	map<string, int> Output;

	unordered_map<string, vector<string> > ManagerEmpMap;

	for (auto d : meset) {
		string emp = d.first;
		string manager = d.second;
		if (emp != manager)
		{
			if (ManagerEmpMap.find(manager) == ManagerEmpMap.end())
			{
				vector<string> directReportList;
				directReportList.push_back(emp);
				ManagerEmpMap[manager] = directReportList;
			}
			else {
				ManagerEmpMap[manager].push_back(emp);
			}
		}
	}

	for (auto d : meset) {
		populateResUtil(d.first, ManagerEmpMap, Output);
	}

	map<string, int>::iterator itr;
	auto end = Output.end();
	end--;

	cout << "Output = {";
	for (itr = Output.begin(); itr != end; itr++) {
		cout << itr->first << "=" << itr->second << ", ";
	}
	cout << itr->first << "=" << itr->second;
	cout << "}";
}

int main()
{
	unordered_map<string, string> meset;
	meset["S"] = "Q";
	meset["T"] = "Q";
	meset["Q"] = "P";
	meset["U"] = "R";
	meset["R"] = "P";
	meset["P"] = "P";

	populateRes(meset);

	return 0;
}

 

OUTPUT

C++ Output

Code in Java💻

Java program to find number of employees under every manager using hashing methods.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindEmpUnderManager
{
	static Map<String,Integer> Res = new HashMap<String, Integer>();

	public static void main(String[] args)
	{
		Map<String, String> meSet = new HashMap<String, String>();
		meSet.put("S", "Q");
		meSet.put("T", "Q");
		meSet.put("Q", "P");
		meSet.put("U", "R");
		meSet.put("R", "P");
		meSet.put("P", "P");

		populateRes(meSet);
		System.out.println("res = " + Res);
	}

	private static void populateRes(Map<String, String> meSet)
	{
		Map<String, List<String>> ManagerEmpMap = new HashMap<String, List<String>>();

		for (Map.Entry<String,String> entry: meSet.entrySet())
		{
			String employee = entry.getKey();
			String manager = entry.getValue();
			if (!employee.equals(manager))
			{
				List<String> directRepList = ManagerEmpMap.get(manager);

				if (directRepList == null)
				{
					directRepList = new ArrayList<String>();
					ManagerEmpMap.put(manager, directRepList);
				}
				directRepList.add(employee);
			}
		}

		for (String manager: meSet.keySet())
			populateResUtil(manager, ManagerEmpMap);
	}

	private static int populateResUtil(String manager, Map<String, List<String>>  ManagerEmpMap)
	{
		int total = 0;
		if (!ManagerEmpMap.containsKey(manager))
		{
			Res.put(manager, 0);
			return 0;
		}
		else if (Res.containsKey(manager)){
			total = Res.get(manager);
		}
		else
		{
			List<String> directRepEmpList = ManagerEmpMap.get(manager);
			total = directRepEmpList.size();
			for (String directRepEmp: directRepEmpList)
				total += populateResUtil(directRepEmp, ManagerEmpMap);

			Res.put(manager, total);
		}
		
		return total;
	}
}

 

OUTPUT

You can also read about the Longest Consecutive Sequence.

Code in Python💻

Python program to find number of employees under every manager.

class Solution():
    def __init__(self):
           pass


    def EmpUnderMan(self,y):
        x = dict()
        for pair in y:
            if(pair[0]==pair[1]): 
                   continue
            if pair[0] not in x: 
                   x[pair[0]] = []
            if pair[1] not in x:
                   x[pair[1]] = [pair[0]]
            else:
                   x[pair[1]].append(pair[0])

        z = dict() 
        for mngr in x:
            z[mngr] = len(x[mngr])
            for Emp in x[mngr]:
                z[mngr] += len(x[Emp])
            print("{} : {}".format(mngr,z[mngr]))



if __name__=="__main__":
      y = (("S", "Q"),("T", "Q"),("Q", "P"),("U", "R"),("R", "P"),  ("P","P"))
      obj = Solution()
      obj.EmpUnderMan(y)

 

OUTPUT

Python OutPut

Frequently Asked Questions

What is the Space Complexity of a Hash Table?

Space complexity is the storage occupied by the data structure with respect to the amount elements it stores.

The space Complexity of the Hash function is O(n).

What is Hash Collision?

It may be possible that a Hash function can generate the same hash value for two different inputs, known as a hash collision. 

What is the Time complexity of Hash Table?

Time complexity is the time taken by an algorithm to execute. The time complexity of a Hash Table is O(n).

What is Hash value?

The hash value is a string that is obtained by calculating the Hashing Algorithm. It is used for indexing hash tables and determining the integrity of data.

How is the hash function useful for lookups?

Searching through large amounts of data is a very resource-consuming process, and a hash table acts like an index table listing the key of data stored. So in this way, a hash table helps in searching for information. 

Conclusion

This article taught us how to solve the "find number of employees under every manager" problem using the Hashing technique. We understood the problem statement with the help of an example and also learned about algorithms to solve the problem, and we implemented the algorithm using different programming languages.

Also read,

 

Refer to our guided paths on Coding Ninjas Studio to learn more about C programming, DSA, JavaScript, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Learning!

Previous article
Find All Duplicates in an Array
Next article
Find duplicates in a given array when elements are not limited to a range
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass