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:

1. Maintain two maps - one for all employees, one for managers
2. Define a class/DS for the manager -- info, reportees, set of distinct cities the reportees belong to
3. The above two can be constructed in O(n)
4. 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