“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.
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:
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:
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.
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”
Iterate employee-manager map to and concurrently use a newly declared reverse map to find the number of employees under every particular manager.
Let the map generated by step 2 be 'ManagerEmpMap' Do the following for every employee.
If 'employee’ is not available in 'ManagerEmpMap' Total count under 'employee' is 0 [i.e., “Nobody reports to employee”]
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.
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.
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.
If yes: It means the employee is the manager, and other employees directly report them.
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.
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
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;
}
}
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
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.
305+ registered