Microsoft Interview Question for SDE1s


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}	

}

- guilhebl April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Creating your tree would indeed by O(n), but I think counting the reporting employees would be O(n log n) since you need every employee (n) and have to traverse the tree to get the count (log n). For the CEO F, this means traversing the whole tree again, but for leaves it is constant.

We might be able to get to O(n) if we add a count of reports to the TreeNodeEmp class that is computed once after the tree is complete. We would track the leaves of the tree while it is being created and then traverse up towards the root with a queue. At each node reports would equal children.size() + sum of reports in the children.

- David April 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes it's possible to store the counts in each node like having vars such as:
directEmployeesCount and totalEmployeesCount (which represents total count under subtree), then it would be necessary to calculate only once the values (O n log n), after building tree, in subsequent calls it would be O(1).

And for any delete or update the total counts of the left or right branch(starting from direct manager of inserted or deleted employee) counts should be recalculated and cascaded from manager to manager until reaching the CEO, this should be O(L) where L = number of levels in the tree where that employee got inserted/deleted.

- guilhebl April 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- manjunath.ns April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vishal April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Manvi April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Achyuth Gurram April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Achyuth Gurram April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Manvi April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);

}

- sachin jain April 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}

- sachin jain April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sachin jain April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public Dictionary<string, int> CreateHierarchy(Dictionary<string,string> map)
		{
			Dictionary<string,int> result = new Dictionary<string, int> ();

			foreach (KeyValuePair<string,string> pair in map) {
				result[pair.Key] = 0;
			}

			foreach (KeyValuePair<string,string> pair in map) {
				string emp = pair.Key;
				string mgr = pair.Value;

				if (emp.Equals (mgr)) {
					continue;
				}

				int count1 = 0;
				if (!result.ContainsKey (emp)) {
					count1 = 0;
				} else {
					count1 = result [emp];
				}

				int count2 = 0;
				if (!result.ContainsKey(mgr)) {
					count2 = 1;
				} else {
					count2++;
				}

				int count = count1 + count2;
				if(!result.ContainsKey(mgr))
				{
					result.Add (mgr, count);
				}
				else{
					result[mgr] += count;
				}
			}

			return result;
		}

- C# May 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public Dictionary<string, int> CreateHierarchy(Dictionary<string,string> map)
		{
			Dictionary<string,int> result = new Dictionary<string, int> ();

			foreach (KeyValuePair<string,string> pair in map) {
				result[pair.Key] = 0;
			}

			foreach (KeyValuePair<string,string> pair in map) {
				string emp = pair.Key;
				string mgr = pair.Value;

				if (emp.Equals (mgr)) {
					continue;
				}

				int count1 = 0;
				if (!result.ContainsKey (emp)) {
					count1 = 0;
				} else {
					count1 = result [emp];
				}

				int count2 = 0;
				if (!result.ContainsKey(mgr)) {
					count2 = 1;
				} else {
					count2++;
				}

				int count = count1 + count2;
				if(!result.ContainsKey(mgr))
				{
					result.Add (mgr, count);
				}
				else{
					result[mgr] += count;
				}
			}

			return result;
		}

- rafa26 May 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- amandhanjal April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- Anonymous April 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- tjcbs2 April 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- anu.anssy19 April 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I've corrected my code, as per yesterday's comments i got to know that i understood the question in a different way.

This should be the right code.

- anu.anssy19 April 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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(string key in EmployeeNManager.Keys)
            {
                result.Add(key,0);
            }
            foreach (KeyValuePair<string, string> pair in EmployeeNManager)
            {

                if (result.ContainsKey(pair.Value))
                {
                    if (pair.Key != pair.Value)
                       result[pair.Value] = result[pair.Value] + 1;
                }
                
            }

            return result;
        }

- anu.anssy19 April 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Alex April 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Alex April 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 .

- rsingh604 April 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Sa April 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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());

   }
}
}

- rahul.singh4899 April 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nelson Perez April 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
        }

- ezayak April 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Jydas April 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- malinbupt May 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

- pc May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
		}		
	}
}

- bkmtan May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Mohammad May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Mohammad May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

~

- sowmya.kp May 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

~

- sowmya.kp May 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- sonesh June 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

 
 }
}

- liju.leelives June 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zjzzjz October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- adi.dtu January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- amit March 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- amirtar April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can use LinkedHashMap to maintain the insertion order while iterating over the map.

- Anonymous April 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

- randomCoder1988 April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n) time and space complexity

- randomCoder1988 April 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You are assuming that while iterating through the map you preserve the hierarchy, your code will not work for the input
map.put("A", "C");
map.put("B", "C");
map.put("C", "F");
map.put("D", "E");
map.put("E", "F");
map.put("F", "F");
map.put("G", "C");

- Anonymous April 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution will not work for if the iterator for the map you are using does not keep the sequence of hierarchy. the following example will not work.
map.put("A", "C");
map.put("B", "C");
map.put("C", "F");
map.put("D", "E");
map.put("E", "F");
map.put("F", "F");
map.put("G", "C");

- yogibear April 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Same logic as above code. But different looping.

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();
        Integer count= employeeCounts.get(manager);
        if(count==null)
            employeeCounts.put(manager, 1);
        else
            employeeCounts.put(manager, count+1);
    }
    return employeeCounts;
}

- amirtar April 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1) Each employee contains a member integer variable, say "private int reportee" .
2)Manager to employee is a directed edge (--->)
3)Now it will be a forest of graphs. Each graph contains nodes as employees with directed edge.
4)Now run a stack based DFS on each graph.
5)Whenever there is a push in the stack, the "reportee" should be incremented by 1, for all the employee nodes below the newly pushed node.
6) After the DFS is complete on all the nodes of the forest "reportee" variable has the number of subordinates for each employee.

- s100banerjee April 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

- senthilmpro April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

- puncaz April 10, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More