I am trying Find the phone numbers of all managers whose direct report hierarchy live in more than 1 city in O(n)
time complexity. Below is my approach which is using with Time Complexity O(M*N)
where M is the number of managers and N is the Number of employess.
Can someone please help me with O(N)
solution for this problem.
import java.util.*;
public class EmployeePhoneNums {
public static void main(String[] args) {
String[][] emps2 = new String[][]{
//"EmployeeID", "ManagerID", "City", "Phone number"
{"e1", "e1", "SF", "phone-1"},
{"e2", "e1", "SF", "phone-2"},
{"e3", "e1", "SF", "phone-3"},
{"e4", "e2", "SF", "phone-4"},
{"e5", "e2", "PH", "phone-5"},
{"e6", "e3", "NY", "phone-6"}
};
Map<String, String> phoneNums = getmanagerPhoneNums(emps2);
System.out.println(phoneNums);
}
public static Map<String, String> getmanagerPhoneNums(String[][] input) {
Map<String, String> managerPhoneNums = new HashMap<>();
Map<String, String> phoneMap = new HashMap<>();
Map<String, String> cityMap = new HashMap<>();
Map<String, Set<String>> mgrEmps = new HashMap<>();
Set<String> managers = new LinkedHashSet<>();
for (String[] emp : input) {
phoneMap.put(emp[0], emp[3]);
cityMap.put(emp[0], emp[2]);
managers.add(emp[1]);
if (emp[0].equals(emp[1]))
continue;
else {
mgrEmps.putIfAbsent(emp[1], new HashSet<>());
mgrEmps.get(emp[1]).add(emp[0]);
}
}
System.out.println(mgrEmps);
Queue<String> managersQ = new LinkedList<>(managers);
while (!managersQ.isEmpty()) {
String manager = managersQ.poll();
bfs(manager, mgrEmps, phoneMap, cityMap, managerPhoneNums);
}
return managerPhoneNums;
}
public static void bfs(String manager, Map<String, Set<String>> mgrEmps, Map<String, String> phoneMap, Map<String, String> cityMap, Map<String, String> resultPhoneNums) {
Queue<String> reportees = new LinkedList<>();
if (mgrEmps.containsKey(manager)) reportees.addAll(mgrEmps.get(manager));
Set<String> cities = new HashSet<>();
while (!reportees.isEmpty()) {
int size = reportees.size();
for (int i = 0; i < size; i ) {
String emp = reportees.poll();
if (mgrEmps.get(emp) != null && mgrEmps.get(emp).size() > 0) reportees.addAll(mgrEmps.get(emp));
cities.add(cityMap.get(emp));
if (cities.size() > 1) break;
}
if (cities.size() > 1) {
resultPhoneNums.put(manager, phoneMap.get(manager));
break;
}
}
}
}
CodePudding user response:
Here's a possible algo:
- Maintain two maps - one for all employees, one for managers
- Define a class/DS for the manager -- info, reportees, set of distinct cities the reportees belong to
- The above two can be constructed in O(n)
- Once you have it, you can iterate (in O(n)) to find all managers with reportees city set with size > 1
Defining class to represent Manager - reportees info like below
import java.util.*;
public class MgrReportees {
private String mngr_id = null;
private String[] mngr_info = null;
private List<String> reportee_ids = new ArrayList<>();
private Map<String,String[]> reportee_info = new HashMap<>();
private Set<String> reportee_city = new LinkedHashSet<>();
public void process(String[] emp, Map<String, String[]> all_emp) {
this.mngr_id = emp[1];
if(emp[0].equals(emp[1])) { // this one is manager's info
this.mngr_info = emp;
}else {
if(all_emp.containsKey(emp[1])) { // if available, then update manager's ifo
this.mngr_info = all_emp.get(emp[1]);
}
if(!reportee_info.containsKey(emp[0])) {
reportee_ids.add(emp[0]);
}
reportee_info.put(emp[0], emp);
reportee_city.add(emp[2]);
}
}
public String getMngr_id() {
return mngr_id;
}
public String[] getMngr_info() {
return mngr_info;
}
public List<String> getReportee_ids() {
return reportee_ids;
}
public Map<String, String[]> getReportee_info() {
return reportee_info;
}
public String[] getReportee_info(String reportee_id) {
return reportee_info.get(reportee_id);
}
public Set<String> getReportee_cities() {
return reportee_city;
}
}
Here's how to construct a map of managers info, notice the two maps - all employees and managers
public static Map<String, MgrReportees> constructManagerReportees(String[][] input) {
Map<String, MgrReportees> mngr_registry = new HashMap<>();
Map<String, String[]> employees_registry = new HashMap<>();
for (String[] emp : input) {
employees_registry.put(emp[0],emp );
MgrReportees mgr = mngr_registry.containsKey(emp[1]) ? mngr_registry.get(emp[1]) : new MgrReportees();
mgr.process(emp, employees_registry);
mngr_registry.put(emp[1],mgr);
}
return mngr_registry;
}
and finally calling it & basic city size check:
public static void main(String[] args) {
String[][] emps2 = new String[][]{
//"EmployeeID", "ManagerID", "City", "Phone number"
{"e1", "e1", "SF", "phone-1"},
{"e2", "e1", "SF", "phone-2"},
{"e3", "e1", "SF", "phone-3"},
{"e4", "e2", "SF", "phone-4"},
{"e5", "e2", "PH", "phone-5"},
{"e6", "e3", "NY", "phone-6"}
};
Map<String, MgrReportees> mgrs = constructManagerReportees(emps2);
// Find manager's phone with reportees in more than 1 city
System.out.println("Finding Managers with reportees in more tha 1 city");
for (Map.Entry<String,MgrReportees> entry : mgrs.entrySet()) {
MgrReportees r = entry.getValue();
int cityCount = r.getReportee_cities().size();
if( cityCount > 1) {
System.out.println(String.format("Found Manager Id = %s , Mngr Phone = %s, Reportees City Count = %d "
,entry.getKey()
,r.getMngr_info()[3]
,cityCount));
}
}
System.out.println("Done");
}
for the given sample data, the output will be
Finding Managers with reportees in more tha 1 city
Found Manager Id = e2 , Mngr Phone = phone-2, Reportees City Count = 2
Done
Hope this helps