找出每个经理手下的员工人数-yiteyi-C++库

给定一个字典，其中包含员工和他的经理作为（员工，经理）对的映射，如下所示。

null

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

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

编写一个函数，以获取层次结构中每个经理下的员工数量，而不仅仅是他们的直接下属。可以假设一名员工只直接向一名经理报告。在上面的字典中，根节点/ceo被列为向自己报告。输出应该是包含以下内容的字典。

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

来源：微软采访这个问题可能会以不同的方式解决，但我遵循了这一点，发现很有趣，所以分享：

 1. Create a reverse map with Manager->DirectReportingEmployee     combination. Off-course employee will be multiple so Value     in Map is List of Strings.        "C" --> "A", "B",        "E" --> "D"         "F" --> "C", "E", "F" 2. Now use the given employee-manager map to iterate  and at    the same time use newly reverse map to find the count of    employees under manager.      Let the map created in step 2 be 'mngrEmpMap'    Do following for every employee 'emp'.     a) If 'emp' is not present in 'mngrEmpMap'           Count under 'emp' is 0 [Nobody reports to 'emp']     b) If 'emp' is present in 'mngrEmpMap'           Use the list of direct reports from map 'mngrEmpMap'          and recursively calculate number of total employees          under 'emp'.

第二步中的技巧。b是在寻找经理手下的员工数量时使用记忆（动态规划），这样我们就不需要再为任何员工寻找员工数量。在下面的代码中，populateResultUtil（）是一个递归函数，它使用记忆来避免重复计算相同的结果。下面是上述思想的Java实现

JAVA

                         // Java program to find number of persons under every employee                       
                         import                                     java.util.ArrayList;                       
                         import                                     java.util.HashMap;                       
                         import                                     java.util.List;                       
                         import                                     java.util.Map;                       
           
                         public                                     class                                     NumberEmployeeUnderManager                       
                         {                       
                                                 // A hashmap to store result. It stores count of employees                       
                                                 // under every employee, the count may by 0 also                       
                                                 static                                     Map<String,Integer> result =                       
                                                 new                                     HashMap<String, Integer>();                       
           
                                                 // Driver function                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 Map<String, String> dataSet =                                     new                                     HashMap<String, String>();                       
                                                 dataSet.put(                                     "A"                                     ,                                     "C"                                     );                       
                                                 dataSet.put(                                     "B"                                     ,                                     "C"                                     );                       
                                                 dataSet.put(                                     "C"                                     ,                                     "F"                                     );                       
                                                 dataSet.put(                                     "D"                                     ,                                     "E"                                     );                       
                                                 dataSet.put(                                     "E"                                     ,                                     "F"                                     );                       
                                                 dataSet.put(                                     "F"                                     ,                                     "F"                                     );                       
           
                                                 populateResult(dataSet);                       
                                                 System.out.println(                                     "result = "                                     + result);                       
                                                 }                       
           
                                                 // This function populates 'result' for given input 'dataset'                       
                                                 private                                     static                                     void                                     populateResult(Map<String, String> dataSet)                       
                                                 {                       
                                                 // To store reverse of original map, each key will have 0                       
                                                 // to multiple values                       
                                                 Map<String, List<String>> mngrEmpMap =                       
                                                 new                                     HashMap<String, List<String>>();                       
           
                                                 // To fill mngrEmpMap, iterate through the given map                       
                                                 for                                     (Map.Entry<String,String> entry: dataSet.entrySet())                       
                                                 {                       
                                                 String emp = entry.getKey();                       
                                                 String mngr = entry.getValue();                       
                                                 if                                     (!emp.equals(mngr))                                     // excluding emp-emp entry                       
                                                 {                       
                                                 // Get the previous list of direct reports under                       
                                                 // current 'mgr' and add the current 'emp' to the list                       
                                                 List<String> directReportList = mngrEmpMap.get(mngr);                       
           
                                                 // If 'emp' is the first employee under 'mgr'                       
                                                 if                                     (directReportList ==                                     null                                     )                       
                                                 {                       
                                                 directReportList =                                     new                                     ArrayList<String>();                       
                                                 // add a new entry for the mngr with empty directReportList                       
                                                 mngrEmpMap.put(mngr, directReportList);                       
                                                 }                       
                                                 directReportList.add(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                                     (String mngr: dataSet.keySet())                       
                                                 populateResultUtil(mngr, mngrEmpMap);                       
                                                 }                       
           
                                                 // This is a recursive function to fill count for 'mgr' using                       
                                                 // mngrEmpMap.  This function uses memoization to avoid re-                       
                                                 // computations of subproblems.                       
                                                 private                                     static                                     int                                     populateResultUtil(String mngr,                       
                                                 Map<String, List<String>> mngrEmpMap)                       
                                                 {                       
                                                 int                                     count =                                     0                                     ;                       
           
                                                 // means employee is not a manager of any other employee                       
                                                 if                                     (!mngrEmpMap.containsKey(mngr))                       
                                                 {                       
                                                 result.put(mngr,                                     0                                     );                       
                                                 return                                     0                                     ;                       
                                                 }                       
           
                                                 // this employee count has already been done by this                       
                                                 // method, so avoid re-computation                       
                                                 else                                     if                                     (result.containsKey(mngr))                       
                                                 count = result.get(mngr);                       
           
                                                 else                       
                                                 {                       
                                                 List<String> directReportEmpList = mngrEmpMap.get(mngr);                       
                                                 count = directReportEmpList.size();                       
                                                 for                                     (String directReportEmp: directReportEmpList)                       
                                                 count +=  populateResultUtil(directReportEmp, mngrEmpMap);                       
           
                                                 result.put(mngr, count);                       
                                                 }                       
                                                 return                                     count;                       
                                                 }                       
                         }                       

Python3

                         class                                     Solution():                       
                                                 def                                     __init__(                                     self                                     ):                       
                                                 pass                       
           
                                                 def                                     assignAndPrint(                                     self                                     ,t):                       
                                                 #We will directly permute over t. Access 2nd element(i.e. manager) of certain tuple and assign the relation in                       
                                                 # dictionary. We will assign list of employees to a particular manager so that with iterations, we can append                       
                                                 # more employees to that list and list grows.                       
                                                 d                                     =                                     dict                                     ()                       
                                                 for                                     pair                                     in                                     t:                       
                                                 if                                     (pair[                                     0                                     ]                                     =                                     =                                     pair[                                     1                                     ]):                                     # because we dont want to assign self managing role                       
                                                 continue                       
                                                 if                                     pair[                                     0                                     ]                                     not                                     in                                     d:                                     # assign employee a empty list of employees                       
                                                 d[pair[                                     0                                     ]]                                     =                                     []                       
                                                 # for managers -                       
                                                 if                                     pair[                                     1                                     ]                                     not                                     in                                     d:                       
                                                 d[pair[                                     1                                     ]]                                     =                                     [pair[                                     0                                     ]]                       
                                                 else                                     :                       
                                                 d[pair[                                     1                                     ]].append(pair[                                     0                                     ])                       
                                                 #print(d)                       
                                                 # now we know how many employees are directly under a particular manager.                       
                                                 # now lets count the total number of employees under a particular manager.                       
                                                 c                                     =                                     dict                                     ()                                     # store    manager:count of employee    as key value                       
                                                 for                                     manager                                     in                                     d:                       
                                                 c[manager]                                     =                                     len                                     (d[manager])                       
                                                 for                                     employee                                     in                                     d[manager]:                       
                                                 c[manager]                                     +                                     =                                     len                                     (d[employee])                       
                                                 print                                     (                                     "{} : {}"                                     .                                     format                                     (manager,c[manager]))                                     # prints which manager has total how many employees                       
                                                 # Note : Employees having no employees under are also considered as managed with 0 employees.                       
           
           
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 # t is tuple containing employee and boss pair.                       
                                                 t                                     =                                     ((                                     "A"                                     ,                                     "C"                                     ),(                                     "B"                                     ,                                     "C"                                     ),(                                     "C"                                     ,                                     "F"                                     ),(                                     "D"                                     ,                                     "E"                                     ),(                                     "E"                                     ,                                     "F"                                     ),(                                     "F"                                     ,                                     "F"                                     ))                       
                                                 obj                                     =                                     Solution()                       
                                                 obj.assignAndPrint(t)                       

输出

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

本文由 钱丹·普拉卡什 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章