查找每个经理下的员工数量

2024年8月28日 | 阅读 4 分钟

员工及其老板在一个字典中被映射为一组（员工，经理）对，如下所示。

{ "A", "C" },
{ "B", "C" },
{ "C", "F" },
{ "D", "E" },
{ "E", "F" },
{ "F", "F" } 

In this example C is manager of A, C is also manager of B, F is manager of C and so on.

创建一个函数，返回每个经理在层级结构中拥有的总员工数量，而不仅仅是其直属下属。每个员工可能只向一位老板直接汇报。在上述词汇表中，根节点/CEO 被列为向自己汇报。

应生成一个包含以下词汇的输出字典。

A - 0  
B - 0
C - 2
D - 0
E - 1
F - 5 

这个问题可能有多种解答方式，但我发现它很有趣，所以想分享一下。

1. With the combination of Manager->DirectReportingEmployee, create a reverse map. Employees will, of course, be numerous, thus the value in the map is a list of strings.
       "C" --> "A", "B",
       "E" --> "D" 
       "F" --> "C", "E", "F"
2. Utilize the provided employee-manager map to iterate now, and use the newly created reverse map to determine the number of employees under the management.

	Let's call the map produced in step 2 "mngrEmpMap." Do this for each employee, abbreviated "emp."
   • Count under "emp" is 0 if "emp" is absent from "mngrEmpMap" [No one reports to "emp"]
   • b) When "emp" appears in "mngrEmpMap" Calculate the total number of employees under "emp" recursively using the list of direct reports from the map "mngrEmpMap."

在第 2.b 步中，利用记忆（动态规划）来确定管理下的员工数量，使我们不必为每个单独的员工重复此过程。在下面的代码中，递归函数 populateResultUtil() 利用了记忆化，以避免对相同结果的重复计算。

C++ 代码

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

// This is a recursive function to fill count for 'mngr'
// using mngrEmpMap. This function uses memoization to
// avoid re- computations of subproblems.
int populateResultUtil(
	string mngr,
	unordered_map<string, vector<string> > mngrEmpMap,
	map<string, int>& result)
{
	int count = 0;

	// means employee is not a manager of any other employee
	if (mngrEmpMap.find(mngr) == mngrEmpMap.end()) {
		result.insert({ mngr, 0 });
		return 0;
	}

	// this employee count has already been done by this
	// method, so avoid re-computation
	else if (result.find(mngr) != result.end()) {
		count = result[mngr];
	}
	else {
		vector<string> directReportEmpList
			= mngrEmpMap[mngr];
		count = directReportEmpList.size();
		for (int i = 0; i < directReportEmpList.size();
			i++) {
			count += populateResultUtil(
				directReportEmpList[i], mngrEmpMap, result);
		}
		result.insert({ mngr, count });
	}
	return count;
}

// This function populates 'result' for given input
// 'dataset'
void populateResult(unordered_map<string, string> dataset)
{

	// A hashmap to store result. It stores count of
	// employees under every employee, the count may by 0
	// also
	map<string, int> result;

	// To store reverse of original map, each key will have
	// 0 to multiple values
	unordered_map<string, vector<string> > mngrEmpMap;

	// To fill mngrEmpMap, iterate through the given map
	for (auto d : dataset) {
		string emp = d.first;
		string mngr = d.second;
		if (emp != mngr) // excluding emp-emp entry
		{
			// If 'emp' is the first employee under 'mngr'
			if (mngrEmpMap.find(mngr) == mngrEmpMap.end()) {
				vector<string> directReportList;
				directReportList.push_back(emp);
				// add a new entry for the mngr with empty
				// directReportList
				mngrEmpMap[mngr] = directReportList;
			}
			else {
				// Get the previous list of direct reports
				// under current 'mngr' and add the current
				// 'emp' to the list
				mngrEmpMap[mngr].push_back(emp);
			}
		}
	}

	// Now use manager-Emp map built above to populate
	// result with use of populateResultUtil()

	// note- we are iterating over original emp-manager map
	// and will use mngr-emp map in helper to get the count
	for (auto d : dataset) {
		populateResultUtil(d.first, mngrEmpMap, result);
	}

	map<string, int>::iterator itr;
	auto end = result.end();
	end--; // end to second last;

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

int main()
{
	unordered_map<string, string> dataset;
	dataset["A"] = "C";
	dataset["B"] = "C";
	dataset["C"] = "F";
	dataset["D"] = "E";
	dataset["E"] = "F";
	dataset["F"] = "F";

	populateResult(dataset);

	return 0;
}

输出

result = {A=0, B=0, C=2, D=0, E=1, F=5}

下一主题两个链表的并集和交集

查找每个经理下的员工数量

C++ 代码

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

查找每个经理下的员工数量

C++ 代码

相关帖子

将表示数字的链表相加

香农-法诺算法用于数据压缩

布尔矩阵问题

访问数组位置以最大化分数

包含所有前缀的最长有效单词

栈指针

数据结构中的动态内存分配

给定一个 n x n 的方阵，查找大小为 k x k 的所有子正方形的和

遍历 N 元树的方法数量

B 树可视化

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器