Microsoft Interview Question
SDE1sCountry: United States
Interview Type: In-Person
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;
}
}
}
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.
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.
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 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 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;
}
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;
}
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;
}
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.
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;
}
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++;
}
}
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);
}
}
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;
}
}
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");
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");
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;
}
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.
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;
}
This can be done based on topo-traverse.
- zjzzjz October 19, 20151) 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