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;
}
}
}
}
Advertisement
Answer
For this problem, we can model relationships between employee as a Directed Acyclic Graph (or DAG) perfectly well.
That will allow finding managers having subordinates that from at least two different cities in a liner time O(n).
For this task we don’t need to distinguish between the job-rolls, meaning we can assume that each employee can potentially have a manager and subordinates, the vertex of the graph would represented by the Employee class.
There would be no cycles in this graph because according to the sample data each employee can have at most one manager (I’ll ignore the case with employee e1 which happens to be the boss to themself because it doesn’t make sense from the perspective of this problem), and connected vertexes would from so-called N-ary tree.
There also could be a situation when there are several groups of employee that have no connection with each other, they will form so-called connected components. To ensure that all vertexes would be examined in case when graph contains several connected components, we need to iterate over the collection of all vertexes and fire the traversal algorithm for every vertex that hasn’t been encountered yet.
To understand the logic of traversal, let’s consider the following graph of employees.
As you can see, Employee-1 (with id1) and Employee-3 (with id3) are marked with a green tick denoted that they have subordinates that live in more than one city. Orange arrows represent relation employee-subordinates, black arrows – direction of traversal.
Let’s assume traversal starts from Employee-1. To traverse the graph, we would use the Depth first search algorithm (for short DFS), tweaked a little bit for our purposes. Internally it uses a stack data structure (in the code below denoted simply as stack). And in every branch when we hit the employee that has no subordinates we need to be able to traverse backwards propagating the properties (that’s the tweak I’ve mentioned), and for that we will use another stack (denoted as isBeingVisited, meaning that we are not done yet with examining the employees it contains because we are traversing their subordinates).
So we are starting by allocating Employee-1 on the top of the stack. Each step of the traversal begins with removing an element from of stack. And initially we have only Employee-1, it’s being removed and since it has subordinates it would be placed on the top of the stack isBeingVisited, and its subordinates Employee-2 and Employee-3 would be pushed onto the stack.
At the beginning of the second step, we have Employee-3 on the top of the stack. It’s being removing and allocated on the top of the isBeingVisited, while its subordinates Employee-4 and Employee-5 would be pushed onto the stack.
The third step would start with removal Employee-5 from the stack pushing it onto the isBeingVisited and allocating its subordinate Employee-6 on the stack.
Here we’ve reached the leave of the N-ary tree, it means two things: Employee-6 has no chances to appear in the resulting list (they luck subordinates) and we don’t need to push them into isBeingVisited (we’re done here), but as the last action to tell its manages where they leave. So we are starting to moving backwards, propagating either the properties, which is either a boolaen field isSelected (denoting whether this employee matches the given criterion), or a set of cities (for more detail see the implementation of propagateSelection()).
Note: in the code logic for backward traversal decoupled from the DFS-implementation, and stack isBeingVisited is being processed in one go.
In short, method getSelectedEmployee() fires the traversal by invoking DFS-implementation, method dfs(), whenever it encounters the vertex that hasn’t been seen before. And when dfs() is done, method select() performs traversal in the backward direction (from subordinate to manager), propagating the properties of the subordinates and populating the resulting list.
The implementation might of the graph might look like this.
public static class EmployeeGraph {
private Map<String, Employee> employeeById = new HashMap<>();
public List<Employee> getSelectedEmployee() {
List<Employee> result = new ArrayList<>(); // will store the managers having subordinates from more than one city
Deque<Employee> stack = new ArrayDeque<>(); // will be used for performing traversal in the DFS implementation
Set<Employee> seen = new HashSet<>(); // is meant to store every encountered vertex
for (Employee next : employeeById.values()) {
if (!seen.contains(next)) {
stack.push(next);
seen.add(next);
dfs(result, stack, seen);
}
}
return result;
}
private void dfs(List<Employee> result, Deque<Employee> stack, Set<Employee> seen) { // DFS implementation
Deque<Employee> isBeingVisited = new ArrayDeque<>(); // stack of vertices that are being visited, i.e. managers which subordinates haven't been fully examined
while (!stack.isEmpty()) {
Employee current = stack.pop();
List<Employee> subordinates = current.getSubordinates();
if (subordinates.isEmpty()) {
current.propagateSelection(); // share the city with a direct manager
} else {
isBeingVisited.push(current);
for (Employee subordinate: current.getSubordinates()) {
if (seen.add(subordinate)) stack.push(subordinate); // allocating subordinates on the stack
}
}
}
select(result, isBeingVisited); // examining the properties of managers that has been visited
}
private void select(List<Employee> result, Deque<Employee> isBeingVisited) {
while (!isBeingVisited.isEmpty()) {
Employee manager = isBeingVisited.pop();
if (manager.isSelected()) result.add(manager); // if manager is marked as selected - add to the result list
manager.propagateSelection(); // propagating the properties to the direct manager (if any)
}
}
// NOT a part of the Algorithm - convenience-method for initializing the graph by parsing string arguments into instances of employee
public void addEmployee(String... args) {
if (args.length == 1) {
employeeById.computeIfAbsent(args[0], Employee::new);
} else if (args.length == 4) {
Employee manager = args[1] != null ? employeeById.computeIfAbsent(args[1], Employee::new) : null;
if (employeeById.containsKey(args[0])) {
Employee employee = employeeById.get(args[0]);
employee.setManager(manager)
.setCity(args[2])
.setPhone(args[3]);
} else {
employeeById.put(args[0], new Employee(args[0],manager, args[2], args[3]));
}
if (args[1] != null) {
manager.addSubordinate(employeeById.get(args[0]));
}
} else {
throw new IllegalArgumentException();
}
}
public static class Employee {
private String id;
private String city;
private String phone;
private Employee manager;
private List<Employee> subordinates = new ArrayList<>();
private Set<String> subordinateCities = new HashSet<>();
private boolean isSelected;
public Employee(String id) {
this.id = id;
}
public Employee(String id, Employee manager, String city, String phone) {
this.id = id;
this.city = city;
this.phone = phone;
this.manager = manager;
}
public void addSubordinate(Employee employee) {
subordinates.add(employee);
}
public void propagateSelection() {
if (manager == null) return;
if (isSelected) {
manager.setSelected();
} else {
shareSubordinateCitiesWithManager();
manager.trySelect();
}
}
public void shareSubordinateCitiesWithManager() {
Set<String> managersSubCities = manager.subordinateCities;
managersSubCities.addAll(this.subordinateCities);
managersSubCities.add(this.city);
}
public void trySelect() {
if (subordinateCities.size() >= 2) {
setSelected();
}
}
public List<Employee> getSubordinates() {
return subordinates;
}
public String getPhone() {
return phone;
}
public void setSelected() {
isSelected = true;
}
public boolean isSelected() {
return isSelected;
}
public Employee setCity(String city) {
this.city = city;
return this;
}
public Employee setPhone(String phone) {
this.phone = phone;
return this;
}
public Employee setManager(Employee manager) {
this.manager = manager;
return this;
}
}
}
Note: as suggested by the documentation, as the implementation of the stack data structure we need to use classes that implement Deque interface (class Stack is legacy and shouldn’t be used). And the best choice when we need a general purpose implementation of the Deque is an ArrayDeque, which is backed by the plain array as its name suggests, and its methods are much chipper than corresponding methods of the LinkedList. The only reason you can encounter LinkedList in the code, espesially while implementing graph traversal algorithms is because since the earlier days of Java it was the only general perpose implementation of the Queue and Deque interfaces until the Java 6 when ArrayDeque was introduced in the JDK.
main()
public static void main(String[] args) {
String[][] emps = new String[][]{
//"EmployeeID", "ManagerID", "City", "Phone number"
{"e1", null, "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"}
};
EmployeeGraph graph = new EmployeeGraph();
for (String[] arr: emps) graph.addEmployee(arr); // initializing the graph
graph.getSelectedEmployee().forEach(e -> System.out.println(e.getPhone())); // printing the result - phones of the selected managers
}
Output:
phone-2 phone-1