Given a list of employees in the format <"EmployeeID", "ManagerID", "City", "Phone number">
eg String[][] emps = new String[][] {
{"e1", "e1", "NY", "phone-1"},
{"e2", "e1", "NY", "phone-2"},
{"e3", "e1", "NY", "phone-3"},
{"e4", "e2", "SF", "phone-4"},
{"e5", "e2", "NY", "phone-5"},
{"e6", "e3", "NY", "phone-6"},
{"e7", "e3", "NY", "phone-7"},
{"e8", "e3", "SF", "phone-8"},
{"e9", "e8", "NY", "phone-9"},
{"e0", "e8", "NY", "phone-0"},
};-
Find the phone numbers of all managers whose direct report employees live in more than 1 city (in O(n) time complexity). Note the ceo will not have a manager, so his manager will be himself
This can be done by creating a Map<Manager, Set> and also a Map<EmpId, PhoneNumber>. -
In the second part we want to find the phone numbers of all managers whose report chain lives in more than 1 city eg
In the example above Only Emp 1 has his reportee chain in 2 different cities. (His own city does not matter, only reportee chain needs to have more than 1 city )
Solution for Part 2
List<String> result = new ArrayList<>();
Map<String, String> phoneMap = new HashMap<>();
Map<String, String> cityMap = new HashMap<>();
Map<String, Set<String>> mgrEmps = new HashMap<>();
public List<String> findPhone(String[][] input){
String ceo = null;
for(String[] emp : input) {
phoneMap.put(emp[0], emp[3]);
cityMap.put(emp[0], emp[2]);
if(emp[0].equals(emp[1]))
ceo = emp[0];
else {
mgrEmps.putIfAbsent(emp[0], new HashSet<>());
mgrEmps.putIfAbsent(emp[1], new HashSet<>());
mgrEmps.get(emp[1]).add(emp[0]);
}
}
System.out.println(mgrEmps);
getReporteeCities(ceo);
return result;
}
public Set<String> getReporteeCities (String emp){
Set<String> cities = new HashSet<>();
for(String reportee : mgrEmps.get(emp)) {
cities.addAll(getReporteeCities(reportee));
}
System.out.println(emp +" "+cities);
if(cities.size()>1)
result.add(phoneMap.get(emp));
cities.add(cityMap.get(emp));
return cities;
}
Comments (2)