Encuentre el número de empleados debajo de cada gerente

Dado un diccionario que contiene el mapeo del empleado y su gerente como un número de pares (empleado, gerente) como se muestra a continuación. 

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

Escriba una función para obtener el número de empleados bajo cada gerente en la jerarquía, no solo sus informes directos. Se puede suponer que un empleado depende directamente de un solo gerente. En el diccionario anterior, el Node raíz/director ejecutivo aparece como dependiente de sí mismo. 

La salida debe ser un diccionario que contenga lo siguiente. 

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

Esta pregunta podría resolverse de manera diferente, pero seguí esto y me pareció interesante, así que comparto:

 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'. 

Un truco en el paso 2.b es usar la memorización (programación dinámica) mientras se encuentra el número de empleados bajo un gerente para que no necesitemos encontrar el número de empleados nuevamente para ninguno de los empleados. En el siguiente código, populateResultUtil() es la función recursiva que utiliza la memorización para evitar volver a calcular los mismos resultados.

A continuación se muestra la implementación de Java de las ideas anteriores.

#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;
}
 
// This code is contributed by Snigdha Patil

// 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;
    }
}

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}