Q1 PepCoding | Number Of Employees Under Every Manager
Sat Jan 21 2023 07:18:36 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.io.*;
import java.util.*;
public class Main {
public static void findcount(HashMap<String , String> map){
//make a hashmap to store tree information and store root as ceo
HashMap<String , HashSet<String>> tree = new HashMap<>();
String ceo = "";
//traverse the map and fill the tree
for(String emp: map.keySet()){ //emp = employee , man = manager
String man = map.get(emp);
if(man.equals(emp)) ceo = man;
else{
//if manager already exists
if(tree.containsKey(man)){
tree.get(man).add(emp);
}
else{
HashSet<String> emps = new HashSet<>();
emps.add(emp);
tree.put(man,emps);
}
}
}
// make a result Hashmap to store employee:employees under them
//write getsize() recurisive tree function to find employees under manager and pass ceo as root
HashMap<String, Integer> result = new HashMap<>();
getsize(tree , ceo , result);
for(String emp : result.keySet())
System.out.println(emp + " " + result.get(emp));
}
//this is a normal getsize recursive functions in general trees
public static int getsize(HashMap<String , HashSet<String>> tree,
String man , HashMap<String, Integer> result){
//if it doesn't exist in the tree its a leaf node with 0 under employees
if(tree.containsKey(man) == false){
result.put(man,0);
return 1;
}
int size = 0;
//traversing the tree
for(String emp : tree.get(man)){
int cs = getsize(tree,emp,result);
size += cs;
}
result.put(man,size); //putting size infront of that employee
return size+1; //return size and +1 including that employee
}
public static void main(String[] args){
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
HashMap<String , String>map = new HashMap<String , String>();
for(int i=0 ; i < n ; i++)
map.put(scn.next(),scn.next());
findcount(map);
}
}
content_copyCOPY
https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/hashmap-and-heaps/number-of-employees-under-every-manager-official/ojquestion
Comments