CareerCup

This can be done based on topo-traverse.
1) Keep track of map M from one to people one manages, initialize everyone to be zero at the beginning
2) at each topo-search step, when a node n is ready to run, add M[n]+1 to all its successors.
3) if a cycle is detected, raise an exception

Based on the input data it would make it possible to build the tree in O(n) time, using a HashMap lets you jump directly to a node instead of traversing there from the tree's root node:

1. build tree of designated company hierarchy based on input map, use an auxiliary
Map of <String, TreeNodeEmp> representing each employee and also for adding the direct employees of a specific manager.
complexity: O(n)

2. Once tree is built, calculate counts of Direct employees and total employees under each employee.

Once calculated subsequent operations for read will be O(1) such as counting total direct and indirect employees for any given employee, whenever tree is changed (nodes inserted or deleted) subtree counts of left or right branch starting from root should be recalculated.

Solution in Java:

public class Solution {

public static void main(String[] args) {
	printAllEmployeesOfAllManagers();
}

public static void printAllEmployeesOfAllManagers() {
	Map<String, String> dataSet = new HashMap<>();
	dataSet.put("A", "C");
	dataSet.put("B", "C");
	dataSet.put("C", "F");
	dataSet.put("D", "E");
	dataSet.put("E", "F");
	dataSet.put("F", "F");

	Map<String, TreeNodeEmp> empTreeNodeMap = new HashMap<>();
	TreeNodeEmp root = buildHierarchyTreeOfCompany(dataSet, empTreeNodeMap);
	calculateCountsOfTree(root); 
	Map<String, Integer> output = new HashMap<>();

	for (Map.Entry<String, TreeNodeEmp> empEntry : empTreeNodeMap
			.entrySet()) {
		String empName = empEntry.getKey();
		TreeNodeEmp emp = empEntry.getValue();
		output.put(empName, emp.countTotalEmployees);
	}
	printResults(output);
}

public static void printResults(Map<String, Integer> results) {
	for (Map.Entry<String, Integer> r : results.entrySet()) {
		System.out.println(r.getKey() + " - " + r.getValue());
	}
}

public static void calculateCountsOfTree(TreeNodeEmp root) {
	if(root == null) {
		return;
	}
	root.countDirectEmployees = root.children.size();
	root.countTotalEmployees = getCountEmployeesOfManager(root) - 1;
	for (TreeNodeEmp emp : root.children) {
		calculateCountsOfTree(emp);
	}
}

public static Integer getCountEmployeesOfManager(TreeNodeEmp root) {
	if(root == null) {
		return 0;
	}
	int count = 1;
	for (TreeNodeEmp emp : root.children) {
		count += getCountEmployeesOfManager(emp);
	}
	return count;
}

public static TreeNodeEmp buildHierarchyTreeOfCompany(
		Map<String, String> empMap, Map<String, TreeNodeEmp> empTreeNodeMap) {
	Map<String, List<TreeNodeEmp>> auxMgrEmpList = new HashMap<>();
	List<TreeNodeEmp> listEmps = null;
	TreeNodeEmp emp = null, mgr = null, root = null;
	String nameEmp, managerName;

	for (Map.Entry<String, String> empMapEntry : empMap.entrySet()) {
			nameEmp = empMapEntry.getKey();
			managerName = empMapEntry.getValue();

			if (!empTreeNodeMap.containsKey(nameEmp)) {
				emp = new TreeNodeEmp(nameEmp, managerName);

				// check for who was added before and have this as a manger
				if(auxMgrEmpList.containsKey(nameEmp)) {
				   emp.children.addAll(auxMgrEmpList.get(nameEmp));	
				}										
				empTreeNodeMap.put(nameEmp, emp);
			}
			
			if (nameEmp.equals(managerName)) {
				root = emp;
			} else if (empTreeNodeMap.containsKey(managerName)) {
				mgr = empTreeNodeMap.get(managerName);
				mgr.children.add(emp);
			} else if (!auxMgrEmpList.containsKey(managerName)){
				listEmps = new ArrayList<>();
				listEmps.add(emp);
				auxMgrEmpList.put(managerName, listEmps);
			} else {
				listEmps = auxMgrEmpList.get(managerName);
				listEmps.add(emp);
				auxMgrEmpList.put(managerName, listEmps);					
			}

	}

	return root;
}

class TreeNodeEmp {
	String name;
	String managerName;
	Integer countDirectEmployees;
	Integer countTotalEmployees;
	Set<TreeNodeEmp> children;

	public TreeNodeEmp(String name, String managerName) {
		this.name = name;
		this.managerName = managerName;
		children = new HashSet<>();
		countDirectEmployees = 0;
		countTotalEmployees = 0;
	}

}	

}

import java.util.ArrayList;

public class TestBuildHierachy {

/**
* @param args
*/
public static void main(String[] args) {

HashMap<String, String> employees = new HashMap<String, String>();
employees.put("A", "C");
employees.put("B", "C");
employees.put("C", "F");
employees.put("D", "E");
employees.put("E", "F");
employees.put("F", "F");

buildHierachy(employees);

}

public static void buildHierachy(HashMap<String, String> employees) {
HashMap<String, Manager> managerMap = new HashMap<String, Manager>();
Manager ceo = null;

for (String manager : employees.values()) {
if (!managerMap.containsKey(manager)) {
managerMap.put(manager, new Manager(manager));
}
}

for (String employee : employees.keySet()) {
String managerName = employees.get(employee);
if (employee.equals(managerName)) {
ceo = managerMap.get(managerName);
} else if (managerMap.containsKey(employee)) {
managerMap.get(managerName).addChildren(
managerMap.get(employee));
} else {
Employee emp = new Employee(employee);
managerMap.get(managerName).addChildren(emp);
}
}
if (ceo != null) {
ceo.printDepth(new Integer(0));
}
}

}

class Manager extends Employee {
List<Employee> children = new ArrayList<Employee>();

public Manager(String name) {
super(name);
}

public void addChildren(Employee ele) {
children.add(ele);
}

public int printDepth(Integer depth){
for(Employee emp: children){
depth += emp.printDepth(new Integer(0));
}
System.out.println(name + " : " + depth);
return depth + 1;
}
}

class Employee {
String name;

public Employee(String name) {
this.name = name;
}

public int printDepth(Integer depth) {
System.out.println(name + " : " + 0);
return 1;
}

}

import java.util.ArrayList;

public class TestBuildHierachy {

/**
* @param args
*/
public static void main(String[] args) {

HashMap < String, String > employees = new HashMap < String, String > ();
employees.put("A", "C");
employees.put("B", "C");
employees.put("C", "F");
employees.put("D", "E");
employees.put("E", "F");
employees.put("F", "F");

buildHierachy(employees);

}

public static void buildHierachy(HashMap < String, String > employees) {
HashMap < String, Manager > managerMap = new HashMap < String, Manager > ();
Manager ceo = null;

for (String manager: employees.values()) {
if (!managerMap.containsKey(manager)) {
managerMap.put(manager, new Manager(manager));
}
}

for (String employee: employees.keySet()) {
String managerName = employees.get(employee);
if (employee.equals(managerName)) {
ceo = managerMap.get(managerName);
} else if (managerMap.containsKey(employee)) {
managerMap.get(managerName).addChildren(
managerMap.get(employee));
} else {
Employee emp = new Employee(employee);
managerMap.get(managerName).addChildren(emp);
}
}
if (ceo != null) {
ceo.printDepth(new Integer(0));
}
}

}

class Manager extends Employee {
List < Employee > children = new ArrayList < Employee > ();

public Manager(String name) {
super(name);
}

public void addChildren(Employee ele) {
children.add(ele);
}

public int printDepth(Integer depth) {
for (Employee emp: children) {
depth += emp.printDepth(new Integer(0));
}
System.out.println(name + " : " + depth);
return depth + 1;
}
}

class Employee {
String name;

public Employee(String name) {
this.name = name;
}

public int printDepth(Integer depth) {
System.out.println(name + " : " + 0);
return 1;
}

}

public Dictionary<string, int> GetManagerReportees(Dictionary<string, string> empManagerMap)
        {
            Dictionary<string, int> managerReporteeMap = new Dictionary<string, int>();
            foreach (var entry in empManagerMap)
            {
                managerReporteeMap[entry.Key] = 0;
            }

            foreach (var entry in empManagerMap)
            {
                if (entry.Value.Equals(entry.Key)) continue;

                if (managerReporteeMap.ContainsKey(entry.Value))
                {
                    managerReporteeMap[entry.Value] += 1; // increment all parents....
                    var prevParent = entry.Value;
                    while (true)
                    {   
                        var curParent = empManagerMap[prevParent];
                        if (curParent.Equals(prevParent)) break;
                        managerReporteeMap[curParent] += 1;
                        prevParent = curParent;
                    }
                }
            }
            
            return managerReporteeMap;
        }

package com.tutorialpoint;

import java.util.Map;
import java.util.TreeMap;

public class ManagerProb
{
public static void main(String[] args) {
Map<String,String> employees = new TreeMap<String, String>();

employees.put("A", "C");
employees.put("B", "C");
employees.put("C", "F");
employees.put("D", "F");
employees.put("E", "F");
employees.put("F", "F");

Map<String,Integer> managerMap= getHierarchyOrder(employees);
for(Map.Entry<String, Integer> entry: managerMap.entrySet())
{
System.out.print("Manager Name : "+entry.getKey());
System.out.println("People under him : "+entry.getValue());
}
}

public static Map<String,Integer> getHierarchyOrder(Map<String,String> employees)
{
Map<String,Integer> freqEntry = new TreeMap<String, Integer>();

for(Map.Entry<String,String> entry : employees.entrySet())
{
if(!freqEntry.containsKey(entry.getKey()))
{
freqEntry.put(entry.getKey(), 0);

}

updateManager(employees,freqEntry,entry.getKey(),entry.getValue());
}

return freqEntry;
}

public static void updateManager(Map<String,String> employees,Map<String,Integer> freqEntry, String currentEmployee,String manager)
{
if(currentEmployee.equalsIgnoreCase(manager))
{
return;
}else
{
if(!freqEntry.containsKey(manager))
{
freqEntry.put(manager, 1);

}else
{
int freq= freqEntry.get(manager);
freq++;
freqEntry.put(manager, freq);
}

updateManager(employees, freqEntry, manager, employees.get(manager));
}
}
}

package com.algorithms;

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

public class EmployeeHierarchyCounter {
	public static void main(String[] args) {
		Map<String, String> employeeManager=new HashMap<String, String>();
		employeeManager.put("A", "C");
		employeeManager.put("B", "C");
		employeeManager.put("C", "F");
		employeeManager.put("D", "E");
		employeeManager.put("E", "F");
		employeeManager.put("F", "F");
		
		Map<String,ArrayList<String>> managerEmployee=new HashMap<String, ArrayList<String>>();
		Iterator<String> it=employeeManager.keySet().iterator();
		String boss=null;
		while(it.hasNext()){
			String key=it.next();
			String manager=employeeManager.get(key);
			if(manager.equals(key)){
				boss=manager;
			}else{
				if(managerEmployee.containsKey(manager)){
					managerEmployee.get(manager).add(key);
				}else {
					ArrayList<String> list=new ArrayList<String>();
					list.add(key);
					managerEmployee.put(manager, list);
				}
			}
		}
		
		//iterate and print managerEmployee map
		it=managerEmployee.keySet().iterator();
		while(it.hasNext()){
			String manager=it.next();
			System.out.print("Manager: "+manager + " Employees ==> ");
			for(String employee: managerEmployee.get(manager)){
				System.out.print(employee+" ");
			}
			System.out.println();
		}
		
		//start from boss and continue till you reach the end
		Map<String,Integer> employeeCount=new HashMap<String, Integer>();
		calculateEmployees(managerEmployee, employeeCount, boss);
		
		it=employeeCount.keySet().iterator();
		while(it.hasNext()){
			String key=it.next();
			System.out.println(key+" ==> "+ employeeCount.get(key));
		}
	}
	public static void calculateEmployees(Map<String,ArrayList<String>> managerEmployee,Map<String,Integer> employeeCount, String boss){
		if(!managerEmployee.containsKey(boss)){
			employeeCount.put(boss, 0);
			return;
		}
		ArrayList<String> employees=managerEmployee.get(boss);
		employeeCount.put(boss, 0);
		for(String employee: employees){
			calculateEmployees(managerEmployee, employeeCount, employee);
			employeeCount.put(boss, employeeCount.get(boss)+employeeCount.get(employee)+1);
		}
	}
	
}

package com.algorithms;

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

public class EmployeeHierarchyCounter {
	public static void main(String[] args) {
		Map<String, String> employeeManager=new HashMap<String, String>();
		employeeManager.put("A", "C");
		employeeManager.put("B", "C");
		employeeManager.put("C", "F");
		employeeManager.put("D", "E");
		employeeManager.put("E", "F");
		employeeManager.put("F", "F");
		
		Map<String,ArrayList<String>> managerEmployee=new HashMap<String, ArrayList<String>>();
		Iterator<String> it=employeeManager.keySet().iterator();
		String boss=null;
		while(it.hasNext()){
			String key=it.next();
			String manager=employeeManager.get(key);
			if(manager.equals(key)){
				boss=manager;
			}else{
				if(managerEmployee.containsKey(manager)){
					managerEmployee.get(manager).add(key);
				}else {
					ArrayList<String> list=new ArrayList<String>();
					list.add(key);
					managerEmployee.put(manager, list);
				}
			}
		}
		
		//iterate and print managerEmployee map
		it=managerEmployee.keySet().iterator();
		while(it.hasNext()){
			String manager=it.next();
			System.out.print("Manager: "+manager + " Employees ==> ");
			for(String employee: managerEmployee.get(manager)){
				System.out.print(employee+" ");
			}
			System.out.println();
		}
		
		//start from boss and continue till you reach the end
		Map<String,Integer> employeeCount=new HashMap<String, Integer>();
		calculateEmployees(managerEmployee, employeeCount, boss);
		
		it=employeeCount.keySet().iterator();
		while(it.hasNext()){
			String key=it.next();
			System.out.println(key+" ==> "+ employeeCount.get(key));
		}
	}
	public static void calculateEmployees(Map<String,ArrayList<String>> managerEmployee,Map<String,Integer> employeeCount, String boss){
		if(!managerEmployee.containsKey(boss)){
			employeeCount.put(boss, 0);
			return;
		}
		ArrayList<String> employees=managerEmployee.get(boss);
		employeeCount.put(boss, 0);
		for(String employee: employees){
			calculateEmployees(managerEmployee, employeeCount, employee);
			employeeCount.put(boss, employeeCount.get(boss)+employeeCount.get(employee)+1);
		}
	}
	
}

package com.algorithms;

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

public class EmployeeHierarchyCounter {
	public static void main(String[] args) {
		Map<String, String> employeeManager=new HashMap<String, String>();
		employeeManager.put("A", "C");
		employeeManager.put("B", "C");
		employeeManager.put("C", "F");
		employeeManager.put("D", "E");
		employeeManager.put("E", "F");
		employeeManager.put("F", "F");
		
		Map<String,ArrayList<String>> managerEmployee=new HashMap<String, ArrayList<String>>();
		Iterator<String> it=employeeManager.keySet().iterator();
		String boss=null;
		while(it.hasNext()){
			String key=it.next();
			String manager=employeeManager.get(key);
			if(manager.equals(key)){
				boss=manager;
			}else{
				if(managerEmployee.containsKey(manager)){
					managerEmployee.get(manager).add(key);
				}else {
					ArrayList<String> list=new ArrayList<String>();
					list.add(key);
					managerEmployee.put(manager, list);
				}
			}
		}
		
		//iterate and print managerEmployee map
		it=managerEmployee.keySet().iterator();
		while(it.hasNext()){
			String manager=it.next();
			System.out.print("Manager: "+manager + " Employees ==> ");
			for(String employee: managerEmployee.get(manager)){
				System.out.print(employee+" ");
			}
			System.out.println();
		}
		
		//start from boss and continue till you reach the end
		Map<String,Integer> employeeCount=new HashMap<String, Integer>();
		calculateEmployees(managerEmployee, employeeCount, boss);
		
		it=employeeCount.keySet().iterator();
		while(it.hasNext()){
			String key=it.next();
			System.out.println(key+" ==> "+ employeeCount.get(key));
		}
	}
	public static void calculateEmployees(Map<String,ArrayList<String>> managerEmployee,Map<String,Integer> employeeCount, String boss){
		if(!managerEmployee.containsKey(boss)){
			employeeCount.put(boss, 0);
			return;
		}
		ArrayList<String> employees=managerEmployee.get(boss);
		employeeCount.put(boss, 0);
		for(String employee: employees){
			calculateEmployees(managerEmployee, employeeCount, employee);
			employeeCount.put(boss, employeeCount.get(boss)+employeeCount.get(employee)+1);
		}
	}

}

package com.tutorialpoint;

import java.util.Map;
import java.util.TreeMap;

public class ManagerProb
{
public static void main(String[] args) {
Map<String,String> employees = new TreeMap<String, String>();

employees.put("A", "C");
employees.put("B", "C");
employees.put("C", "F");
employees.put("D", "F");
employees.put("E", "F");
employees.put("F", "F");

Map<String,Integer> managerMap= getHierarchyOrder(employees);
for(Map.Entry<String, Integer> entry: managerMap.entrySet())
{
System.out.print("Manager Name : "+entry.getKey());
System.out.println("People under him : "+entry.getValue());
}
}

public static Map<String,Integer> getHierarchyOrder(Map<String,String> employees)
{
Map<String,Integer> freqEntry = new TreeMap<String, Integer>();

for(Map.Entry<String,String> entry : employees.entrySet())
{
if(!freqEntry.containsKey(entry.getKey()))
{
freqEntry.put(entry.getKey(), 0);

}

updateManager(employees,freqEntry,entry.getKey(),entry.getValue());
}

return freqEntry;
}

public static void updateManager(Map<String,String> employees,Map<String,Integer> freqEntry, String currentEmployee,String manager)
{
if(currentEmployee.equalsIgnoreCase(manager))
{
return;
}else
{
if(!freqEntry.containsKey(manager))
{
freqEntry.put(manager, 1);

}else
{
int freq= freqEntry.get(manager);
freq++;
freqEntry.put(manager, freq);
}

updateManager(employees, freqEntry, manager, employees.get(manager));
}
}
}

public static void employeeHierarchy(Map<String, String> map)
{
Map<String, Integer> result = new HashMap<>();

for(Entry<String, String> entry : map.entrySet())
{
String employee = entry.getKey();
String manager = entry.getValue();

if(employee.equals(manager))
{
continue;
}

Integer count1 = result.get(employee);
if(count1 == null)
{
count1 = 0;
}

Integer count2 = result.get(manager);
if(count2 == null)
{
count2 = 1;
}
else
{
count2++;
}

int count = count1 + count2;
result.put(manager, count);
}

System.out.println(result);

}

public static void employeeHierarchy(Map<String, String> map)
    {
        Map<String, Integer> result = new HashMap<>();
        
        for(Entry<String, String> entry : map.entrySet())
        {
            String employee = entry.getKey();
            String manager = entry.getValue();
            
            if(employee.equals(manager))
            {
                continue;
            }
            
            Integer count1 = result.get(employee);
            if(count1 == null)
            {
                count1 = 0;
            }
            
            Integer count2 = result.get(manager);
            if(count2 == null)
            {
                count2 = 1;
            }
            else
            {
                count2++;
            }
            
            int count = count1 + count2;
            result.put(manager, count);
        }
        
        System.out.println(result);
        
    }

public static Map<String, Integer> returnTotalNumberOfReports(Map<String, String> employees){
		Map<String, Integer> totalNumberOfReports = new HashMap<String, Integer>(employees.size());
		for(Map.Entry<String, String> employee : employees.entrySet()){
			String employeeName = employee.getKey();
			String employeeManager = employee.getValue();
			Integer totalReports = 0;
			Integer managersReports = 1;

			if (!employeeName.equals(employeeManager)) {
				if (totalNumberOfReports.containsKey(employeeName)) {
					totalReports = totalNumberOfReports.get(employeeName);
				} else {
					totalNumberOfReports.put(employeeName, totalReports);
				}
			}else{
				continue;//we don't need to add this employee because it is a root node/CEO
			}
			
			if(totalNumberOfReports.containsKey(employeeManager)){
				managersReports = totalNumberOfReports.get(employeeManager) + 1;
			}
			
			totalNumberOfReports.put(employeeManager, managersReports + totalReports);

		}
		return totalNumberOfReports;
	}

using namespace std;
void main()
{
   unordered_map<string, int> subords;
   unordered_map<string, string> heir({ { "A", "C" }, { "B", "C" },
                                        { "C", "F" }, { "D", "E" },
                                        { "E", "F" }, { "F", "F" } });
   for (auto entry : heir)
   {
      string cur = entry.first, next = entry.second;
      while (cur != next)
      {
         subords[next]++;
         cur = next;
         next = heir[next];
      }
   }
   for (auto entry : heir)
      printf("%s: %d\n", entry.first.c_str(), subords[entry.first]);
   getch();
}

using namespace std;
void main()
{
   unordered_map<string, int> subords;
   unordered_map<string, string> heir({ { "A", "C" }, { "B", "C" },
                                        { "C", "F" }, { "D", "E" },
                                        { "E", "F" }, { "F", "F" } });
   for (auto entry : heir)
   {
      string cur = entry.first, next = entry.second;
      while (cur != next)
      {
         subords[next]++;
         cur = next;
         next = heir[next];
      }
   }
   for (auto entry : heir)
      printf("%s: %d\n", entry.first.c_str(), subords[entry.first]);
   getch();
}

output:

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

private Dictionary<string, int> NoOfemplyeesForEachManger()
        {
            Dictionary<string, int> result = new Dictionary<string, int>();
            Dictionary<string, string> EmployeeNManager = new Dictionary<string, string>();
            EmployeeNManager.Add("GB", "GB");
            EmployeeNManager.Add("JC", "GB");
            EmployeeNManager.Add("AG", "JC");
            EmployeeNManager.Add("JL", "JC");
            EmployeeNManager.Add("FS", "JC");

            foreach (KeyValuePair<string,string> pair in EmployeeNManager)
            {
                
                    if (result.ContainsKey(pair.Value))
                    {
                        if (pair.Key != pair.Value)
                            result[pair.Value] = result[pair.Value] + 1;
                    }
                    else
                    {
                        if(pair.Key==pair.Value)
                            result.Add(pair.Value, 0);
                        else
                            result.Add(pair.Value, 1);
                    }
                }
            
            return result;
        }

We can solve this using recursion.
First call is "printTotalReportCount" which will tally every employee's total subordinate count.

int getDirectReportCount(map<string,string> mEmployees,string employee,int count)
{
	map<string,string>::iterator iter = mEmployees.begin();

	while(iter != mEmployees.end())
	{
		if(iter->second == employee && iter->first != iter->second)
		{
			count++;
			count += getDirectReportCount(mEmployees,iter->first,0);	
		}	

		++iter;
	}

	return count;
}

void printTotalReportCount(map<string,string> mEmployees)
{
	map<string,string>::iterator iter = mEmployees.begin();

	while(iter != mEmployees.end())
	{
	    printf("\n%s - %d",iter->first.c_str(),getDirectReportCount(mEmployees,iter->first,0));
		iter++;
	}
}

We can solve this using recursion.
Call "printTotalReportCount" which will call getDirectReportCount and recursively find all the managers subordinate total.

int getDirectReportCount(map<string,string> mEmployees,string employee,int count)
{
	map<string,string>::iterator iter = mEmployees.begin();

	while(iter != mEmployees.end())
	{
		if(iter->second == employee && iter->first != iter->second)
		{
			count++;
			count += getDirectReportCount(mEmployees,iter->first,0);	
		}	

		++iter;
	}

	return count;
}

void printTotalReportCount(map<string,string> mEmployees)
{
	map<string,string>::iterator iter = mEmployees.begin();

	while(iter != mEmployees.end())
	{
	    printf("\n%s - %d",iter->first.c_str(),getDirectReportCount(mEmployees,iter->first,0));
		iter++;
	}
}

do we need to maintain order ? the example provided is the order list. what i mean is parent is mentioned as a child of another parent only after it is mentioned as parent of its child .

I'm surprised by the length of the codes above. This is my answer in Java.

public HashMap<String, Integer> mapEmployee(HashMap<String, String> map){
        HashMap<String, Integer> res = new HashMap<>();
        int count = 0;
        for(String s : map.keySet()){
            for(String t : map.keySet()){
                if(s.equals(map.get(t))){
                    count++;
                }                
            }
            res.put(s, count);
            count = 0;
        }
        return res;
    }

does ordering of the data matters .

my code break if i add the hierarchy after finishing the root node

import java.util.*;

 class  reportManager {

public static void main(String []args) {

  Map<String,String> inPut = new HashMap<String,String>();
    inPut.put("A","C");
    inPut.put("B","C");
    inPut.put("C","F");
    inPut.put("D","E");
    inPut.put("E","F");
    inPut.put("G","F");
    inPut.put("F","F");
    inPut.put("M","G");
  Map<String,Integer> outPut= new HashMap<String,Integer>();

   Iterator<Map.Entry<String,String>> entries=  inPut.entrySet().iterator();
    while(entries.hasNext()){
      Map.Entry<String,String> entry= entries.next();
      if(!(outPut.containsKey(entry.getKey()))){
        if(!(outPut.containsKey(entry.getValue()))){
            outPut.put(entry.getKey(),0);
            outPut.put(entry.getValue(),1);
         }
         else {
              outPut.put(entry.getValue(),(outPut.get(entry.getValue())+1));
              outPut.put(entry.getKey(),0);
         }
      }
      else {
            if(!(outPut.containsKey(entry.getValue()))){
             outPut.put(entry.getValue(),outPut.get(entry.getKey())+1);
            }
            else {
                 if(!(entry.getKey().equals(entry.getValue())))
                  outPut.put(entry.getValue(),(outPut.get(entry.getValue()) + (outPut.get(entry.getKey()))+1));
            }
      }
    }
    //printing the value of the putPut String                                                                                                                                        
       for(Map.Entry<String,Integer> entry1 :outPut.entrySet()){
       System.out.println(""+entry1.getKey()+":"+entry1.getValue());

   }
}
}

I'm think there might be a better solution but mine is "reverse" the dictionary and traverse the "tree" counting the levels of depth and adding them up.

This is a O(n) solution as it looks up each employee a constant number of times.

public Dicitonary<string, int> CountReports(Dicitonary<string, string> map)
{
	var Rmap = new Dicitonary<string, List<string>>();
	string ceo = null;

	foreach(var kvp in map)
	{
		if(kvp.Key == kvp.Value)
		{
			ceo = kvp.Key;
		}
		else
		{
			if(!Rmap.ContainsKey(kvp.Value))
			{
				Rmap.Add(kvp.Value, new List<string>() { kvp.Key });
			}
			else
			{
				Rmap[kvp.Value].Add(kvp.Key);
			}
		}

		var result = new Dictionary<string, int>();

		CountReportsHelper(Rmap, result, ceo);

		return result;
	}

	private int CountReportsHelper(
		Dictionary<string, List<string>> Rmap, 
		Dictionary<string, int> result,
		string root)
	{
		if(!Rmap.ContainsKey(root))
		{
			result.Add(root, 0);
			return 1;
		}

		int count = 0;
		foreach(string r in Rmap[root])
		{
			count += CountReportsHelper(Rmap, result, r);
		}

		result.Add(root , count);
		return count + 1;
	}
}

C#

static int CountEmpl(string Manager, Dictionary<string,string> employees, Dictionary<string,int> result)
        {
            if (result.ContainsKey(Manager))
            {
                return result[Manager];
            }

            if (!employees.ContainsValue(Manager)) return 0;


            int empl_number = 0;
            foreach (var item in employees)
            {
                if (item.Value == Manager & item.Value != item.Key)
                {
                    empl_number++;
                    empl_number = empl_number + CountEmpl(item.Key, employees, result);
                }
            }
            result.Add(Manager, empl_number);
            return empl_number;
        }
         static void Main(string[] args)
        {
            Dictionary<string, string> employees = new Dictionary<string, string>() 
            { 
            { "A","C" }, 
            { "B","C" }, 
            { "D","E" }, 
            { "C","E" }, 
            { "E","F" }, 
            { "F","F" } 
            };

            foreach (var item in employees)
            {
                System.Console.WriteLine(" {0} - {1} ", item.Key, item.Value);
            }
            System.Console.WriteLine("-----------------------------------------");

            Dictionary<string, int> result = new Dictionary<string, int>();

            foreach (var item in employees)
            {
                CountEmpl(item.Value, employees, result);
            }

            foreach (var item in result)
            {
                System.Console.WriteLine(" {0} - {1} ", item.Key, item.Value);
            }
            System.Console.ReadLine();
        }

import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;

public static HashMap managerControl(HashMap elements)
    {
      HashMap<String,Integer> map=new HashMap<String,Integer>();
      Set set=elements.entrySet();
      Iterator i=set.iterator();
      //Here we create a new map with the direct employees of each manager
      while(i.hasNext())
      {
        Map.Entry me=(Map.Entry)i.next();
        String manager=(String)me.getValue();
        String employee=(String)me.getKey();
        if(employee!=manager)
        {
         int count=0;
         if(!map.containsKey(employee))
           map.put(employee, count);
         if(!map.containsKey(manager))
           map.put(manager, ++count);
         else
         {
          count=map.get(manager);
          count++;
          map.put(manager, count);   
         }
        }
       }
       Iterator j=set.iterator();
       //Here we add the subordinates of each employee to the manager
       while(j.hasNext())
       {
           Map.Entry me=(Map.Entry)j.next();
           String manager=(String)me.getValue();
           String employee=(String)me.getKey();
           if(employee!=manager)
           {
               int emp=map.get(employee);
               int man=map.get(manager);
               int sum=emp+man;
               map.put(manager, sum);
           }
       }
      return map;
    }

typedef unordered_map<string, vector<string> > Tree;

typedef unordered_map<string, int> NumTable;

void calc(const string &s, Tree &st, NumTable &ans)
{
	if (ans.count(s) > 0) return;

	int cnt = 0;

	for (const auto &t : st[s])
	{
		calc(t, st, ans); cnt += ans[t] + 1;
	}

	ans[s] = cnt;
}

NumTable numOfEmployees(const unordered_map<string, string> &dic)
{
	NumTable ans; Tree st;

	for (auto &p : dic)
	{
		if (p.first == p.second) continue;

		st[p.second].push_back(p.first);
	}

	for (auto &p : st) calc(p.first, st, ans);

	return ans;
}

This can be done without creating the tree

1. Traverse each Key in the Map
{
    1. For the key, find corresponding value
    2. Increase count for the value in the output Map
   3. Search Map by value(manager of Key) to find it's parent - Repeat this step till we    reach to the root and increase the count for each parent found of the way
}

idea I have is,

1) find all the managers with direct reports first
2) sum up the middle managers to the superior bosses
3) print out the reports, added extra boss, "G"

Output
C:\dev\codetests>java EmployeeCount
CEO=G;G
A=0
B=0
C=2
D=0
E=1
F=5
G=6

import java.util.*;

public class EmployeeCount {
	
	public static void main( String[] args ) {
	
		Map<String, String> employee = new HashMap<String, String>();
		employee.put("A","C");
		employee.put("B","C");
		employee.put("C","F");
		employee.put("D","E");
		employee.put("E","F");
		employee.put("F","G");
		employee.put("G","G");
		
		EmployeeCount empCnt = new EmployeeCount(employee);
		empCnt.run();
		empCnt.printReports();
	}
	
	private Map<String, String> _employees;	
	private Map<String, Integer> _reportsCount;
	
	public EmployeeCount(Map<String, String> employees) {
	
		_employees = employees;
		_reportsCount = new HashMap<String, Integer>();
	}
	
	public void run() {
	
		// count the direct reports
		Iterator<Map.Entry<String, String>> empMapIter = _employees.entrySet().iterator();
		while (empMapIter.hasNext()) { 
		
			Map.Entry<String, String> me = empMapIter.next();

			// exclude the ceo
			if (!me.getKey().equals(me.getValue())) {
				if (!_reportsCount.containsKey(me.getValue())) {
								
					_reportsCount.put(me.getValue(), 1);
				} else {

					Integer count = _reportsCount.get(me.getValue());
					_reportsCount.put(me.getValue(), ++count);
				}
			}			
		}
		
		// add the intermediary reporting line
		Iterator<String> intReportsIter = _reportsCount.keySet().iterator();
		while (intReportsIter.hasNext()) {
			
			String r = intReportsIter.next();
			
			// search in employees
			if (_employees.containsKey(r)) {
				String mgrOfmgr = _employees.get(r);
				
				// exclude the ceo
				if (!r.equals(mgrOfmgr)) {
				
					Integer count = _reportsCount.get(mgrOfmgr);
					_reportsCount.put(mgrOfmgr, count + _reportsCount.get(r));
				}
				else {
					System.out.println("CEO=" + r + ";" + mgrOfmgr);
				}
			}			
		}		
		
		// report those who are not managers
		Iterator<String> employeeIter = _employees.keySet().iterator();
		while (employeeIter.hasNext()) {
		
			String emp = employeeIter.next();
			if (!_reportsCount.containsKey(emp)) {
				_reportsCount.put(emp, 0);
			}
		}		
	}
	
	public void printReports() {
	
		if (_reportsCount.size() != 0) {
		
			Iterator<Map.Entry<String, Integer>> reportIter = _reportsCount.entrySet().iterator();
			while (reportIter.hasNext()) {
			
				Map.Entry<String, Integer> me = reportIter.next();
				StringBuilder sb = new StringBuilder();
				sb.append(me.getKey()).append("=").append(me.getValue());
				
				System.out.println(sb.toString());				
			}
		} else  {
		
			System.out.println("Report count process not run yet");
		}		
	}
}

public static Dictionary<string, int> GeManagerPersones(Dictionary<string, string> personManagerMap)
{
Dictionary<string, int> report = new Dictionary<string, int>();
Dictionary<string, List<string>> managerEmployeMap = new Dictionary<string, List<string>>();

// Generate ManagerToEmployeeMap
foreach (KeyValuePair<string, string> item in personManagerMap)
{
if (item.Value == item.Key) continue;

if (!managerEmployeMap.ContainsKey(item.Value))
{

managerEmployeMap.Add(item.Value, new List<string>() { item.Key });
}

else
{
managerEmployeMap[item.Value].Add(item.Key);
}
}

foreach (KeyValuePair<string, string> obj in personManagerMap)
report.Add(obj.Key, GetEmployeeCount(obj.Key, managerEmployeMap));


return report;

}

public static int GetEmployeeCount(string employee, Dictionary<string, List<string>> managerEmployeeMap)
{
if (!managerEmployeeMap.ContainsKey(employee))
{
return 0;// employee without without any staff

}
int count = managerEmployeeMap[employee].Count;
foreach (string emp in managerEmployeeMap[employee])
{
count+= GetEmployeeCount(emp, managerEmployeeMap);
}

return count;
}

public static Dictionary<string, int> GeManagerPersones(Dictionary<string, string> personManagerMap)
        {
            Dictionary<string, int> report = new Dictionary<string, int>();
            Dictionary<string, List<string>> managerEmployeMap = new Dictionary<string, List<string>>();

            // Generate ManagerToEmployeeMap
            foreach (KeyValuePair<string, string> item in personManagerMap)
            {
                if (item.Value == item.Key) continue;

                if (!managerEmployeMap.ContainsKey(item.Value))
                {

                    managerEmployeMap.Add(item.Value, new List<string>() { item.Key });
                }

                else
                {
                    managerEmployeMap[item.Value].Add(item.Key);
                }
            }
 
            foreach (KeyValuePair<string, string> obj in personManagerMap)
                report.Add(obj.Key, GetEmployeeCount(obj.Key, managerEmployeMap));


            return report;

        }

        public static int GetEmployeeCount(string employee, Dictionary<string, List<string>> managerEmployeeMap)
        {
            if (!managerEmployeeMap.ContainsKey(employee))
            {
                return 0;// employee without without any staff

            }
            int count = managerEmployeeMap[employee].Count;
            foreach (string emp in managerEmployeeMap[employee])
            {           
             count+= GetEmployeeCount(emp, managerEmployeeMap);
            }

            return count;
        }

I am new to C++. I came up with this and tested it:

int main() {
map<string,int> no_of_reportees;
map<string,string> reports_to;
map<string,int>::const_iterator j;
map<string,string>::const_iterator i;
reports_to["A"] = "C";
reports_to["B"] = "C";
reports_to["C"] = "F";
reports_to["D"] = "E";
reports_to["E"] = "F";
reports_to["F"] = "F";

for( i = reports_to.begin(); i != reports_to.end() ; ++i ) {
                if(i->first != i->second)
                {
                no_of_reportees[i->second]++;
                no_of_reportees[i->second] += no_of_reportees[i->first];
        }
}
for(i = reports_to.begin(); i != reports_to.end() ; ++i ) {
        cout<< i->first<<":"<<no_of_reportees[i->first]<<"\n";
}
}

Output:
A:0
B:0
C:2
D:0
E:1
F:5

~

I am new to C++. I came up with this and tested it:

int main() {
map<string,int> no_of_reportees;
map<string,string> reports_to;
map<string,int>::const_iterator j;
map<string,string>::const_iterator i;
reports_to["A"] = "C";
reports_to["B"] = "C";
reports_to["C"] = "F";
reports_to["D"] = "E";
reports_to["E"] = "F";
reports_to["F"] = "F";

for( i = reports_to.begin(); i != reports_to.end() ; ++i ) {
                if(i->first != i->second)
                {
                no_of_reportees[i->second]++;
                no_of_reportees[i->second] += no_of_reportees[i->first];
        }
}
for(i = reports_to.begin(); i != reports_to.end() ; ++i ) {
        cout<< i->first<<":"<<no_of_reportees[i->first]<<"\n";
}
}

Output:
A:0
B:0
C:2
D:0
E:1
F:5

~

here is the easy solution

Foreach entry a from the dic employes
	out_dic<a.firststring> = 0; 
Foreach entry a from the dic employes
	out_dic<a.secondstring>  = out_dic<a.secondstring> + 1;
Foreach entry a from the dic employes
	out_dic<a.secondstring>  = out_dic<a.secondstring> + out_dic<a.firststring>;
return out_dic;

Two hashing enabled DSs are only required. I have used hashmap and hashtable

import java.util.*;

class managers
{
 public static void main(String args[])
 {
  Map<String,String> emp = new HashMap<String,String>(){ 
{
	put("A","C"); 
	put("B","C"); 
	put("C","F"); 
	put("D","E"); 
	put("E","F"); 
	put("F","F");
}}; 
Hashtable mgrs = new Hashtable();
Iterator it = emp.entrySet().iterator();
while (it.hasNext()) {
        Map.Entry pair = (Map.Entry)it.next();
       
        
        if(!mgrs.containsKey(pair.getValue()))
          mgrs.put(pair.getValue(),0);
        
        if(!mgrs.containsKey(pair.getKey()))
          mgrs.put(pair.getKey(),0);
         
        mgrs.put(pair.getValue(),(int)mgrs.get(pair.getValue())+1);
        
        if(pair.getValue() == pair.getKey())
         mgrs.put(pair.getValue(),(int)mgrs.get(pair.getValue())+1);
        
    }
    
System.out.println(mgrs);

 
 }
}

Create a HashMap<String, Integer> map, put (key=emp name, value=0) for each emp.

For each (emp, boss) in Dict
	if emp != boss
		update map[boss] += map[emp]+1

print map.

I think of two approaches here - 
1. Using directed Graph (Not necessary that all comes under one manager)
    For each entry in hashmap :
        addEdge(entry.key, entry.val); //directed edge

   //When printing employee under it or count just bfs/dfs starting from that node.

2. Use Hashmap : 
Map <String, List<String>> map;

//iterate first time to store the relationship between manager and immediate employees
for each entry in hierarchy:
     if entry.key != entry.val : 
           List<String> l = map.containsKey(entry.val) ? map.get(entry.val) : new ArrayList();
           l.add(entry.key);

           map.put( entry.val, l);
           
           //insert key for leaf node employees
           if map.containsKey(entry.key) : 
                   map.put(entry.key, new ArrayList());

//Now, we need to put all employees under a manager from hierarchy
for each entry in map :
    List<String> l = entry.val;
    List<String> nl = new ArrayList(l);
    for each key in l : 
         nl.addAll(map.get(key));

    map.put(entry.key, nl);

//Print map directly and get size

My version (Corrected for the root count)

public Map<String, Integer> getEmployees(Map<String, String> employeeManager){
    Map<String,Integer> employeeCounts= new HashMap<>();
    for(Map.Entry<String, String> pair:employeeManager.entrySet()){
        String employee= pair.getKey();
        String manager= pair.getValue();
        if(!employee.equals(manager)){
            Integer count= employeeCounts.get(manager);
            if(count==null)
                employeeCounts.put(manager, 1);
            else
                employeeCounts.put(manager, count+1);
        }        
    }
    return employeeCounts;
}

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Map<String, String> map = new HashMap<String, String>();
		map.put("A", "C");
		map.put("B", "C");
		map.put("C", "F");
		map.put("D", "E");
		map.put("E", "F");
		map.put("F", "F");
		System.out.println(getEmployees(map));
	}
	
	public static Map<String, Integer> getEmployees(Map<String, String> map){
		Map<String, Integer> resultMap = new TreeMap<String, Integer>();
		Iterator<String> it = map.keySet().iterator();
		while(it.hasNext()){
			String key = it.next();
			String value = map.get(key);
			if(key != value){
			  if(!resultMap.containsKey(value)){
				resultMap.put(value, 1);
			}else{
				resultMap.put(value, resultMap.get(value) + 1);
			}
			if(resultMap.containsKey(key)){
				//if key already has some count, we can add those to the value's count
				resultMap.put(value, resultMap.get(value) + resultMap.get(key));
			}
		}
	}
	Iterator<String> it1 = map.keySet().iterator();
	// to add the remaining employees whom no one reports to
	while(it1.hasNext()){
		String key = it1.next();
		if(!resultMap.containsKey(key)){
			resultMap.put(key, 0);
		}
	}
	return resultMap;
	}
}

import java.util.HashMap;

public class EmployeeDictionary {

	public static void main(String[] args) {
		HashMap<String,String> empHashMap = new HashMap<String,String>();
		empHashMap.put("A", "C");
		empHashMap.put("B", "C");
		empHashMap.put("C", "F");
		empHashMap.put("D", "E");
		empHashMap.put("E", "F");
		empHashMap.put("F", "F");
		
		getManagerDict(empHashMap);
		
	}
	
	/* Function to count Managers */
	public static void getManagerDict(HashMap<String,String> empHashMap){
		int[] arr = new int[empHashMap.size()];

		for(String key : empHashMap.keySet())
		{
			int value = empHashMap.get(key).charAt(0) - 65;
			arr[value]++;
		}
		
		for(int i = 0; i< arr.length ; i++)
		{
			
			String asciiVal  = Character.toString((char) (i + 65));
			System.out.println(asciiVal + " - "+ arr[i]);
		}
		
	}
	

}

OUTPUT :
A - 0
B - 0
C - 2
D - 0
E - 1
F - 3

This logic does not care about the original order. But it finds out the total repoting (not direct) for each employee.

It uses two iterations #1 find direct reports #2 performs the summation

Dictionary<string, int> fnGetReporting(Dictionary<string, string> list)
{
	Dictionary<string, int> result=new Dictionary<string, int>();
	
	foreach(var i in list)
	{
		if(result.contains(i.value))
			result.update(i.value, result.get(i.value)+(i.value==i.key?0:1))
		else		
			result.add(i.value,(i.value==i.key?0:1))				
	}
	
	foreach(var i in list)
	{
		if(result.contains(i.key) && i.key!=i.value)
		{
			result.update(i.value, result.get(i.value)+result.get(i.key))
		}
		else
		{
			result.add(i.key,0);
		}
	}

	return result;
}