Algorithms
Who is our Boss? LCA for n-array Tree
In a company which has CEO Bill and a hierarchy of employees. Employees can have a list of other employees reporting to them, which can themselves have reports, and so on. An employee with at least one report is called a manager.
Please implement the closestCommonManager method to find the closest manager (i.e. farthest from the CEO) to two employees. You may assume that all employees eventually report up to the CEO. Assume the following class which you can’t change –
public static class Employee {
private final int id;
private final String name;
private final List<Employee> reports;
public Employee(int id, String name) {
this.id = id;
this.name = name;
this.reports = new ArrayList<Employee>();
}
/**
* @return an integer ID for this employee, guaranteed to be unique.
*/
public int getId() {
return id;
}
/**
* @return a String name for this employee, NOT guaranteed to be unique.
*/
public String getName() {
return name;
}
/**
* @return a List of employees which report to this employee. This list may be empty, but will
* never be null.
*/
public List<Employee> getReports() {
return reports;
}
/**
* Adds the provided employee as a report of this employee.
*/
public void addReport(Employee employee) {
reports.add(employee);
}
}
Given two employees in a company, find the closest common boss of the two employees.
Bill --> CEO
/ | \
DOM SAMIR MICHAEL
/ \ \
Peter Bob Porter
/ \
Milton Nina
Implement Employee closestCommonManager(Employee e1, Employee e2) that will return closest common manager e1 and e2 directly or indirectly reports to.
For example, closestCommonManager(Milton, Nina) = Peter , closestCommonManager(Nina, Porter) = Dom, closestCommonManager(Nina, Samir) = Bill, closestCommonManager(Peter, Nina) = Peter, etc.
How do we solve this problem? This should be straightforward enough to figure out that this is an LCA problem. We solved the LCA for binary trees in a previous post by a simple recursion. We also solved it in an iterative manner using parent pointer. However, in this problem we need to find LCA of two nodes in an n-array tree where a node can have zero or many children. It would be straightforward if we had a parent pointer, then we could have simply walked upward from the node toward the closest common anchestor. But in this problem, the node (Employee) doesn’t have a parent pointer. How do we solve it then?
Idea is same as finding the ancestor path from the node upward to the root. Instead of finding this path through parent pointers we can do a DFS traverse from root down to the node and save the path in upward fashion using a stack. Now, we will apply same technique described in here to find the LCA. First, we will walk upward along the longer path upto diff of the two paths. Then we traverse upward concurrently along both of the paths until a common parent is reached, which is in turn the LCA i.e. the common boss.
Below is the implementation if the above idea that runs in O(n) time and O(n) space.
public static Employee closestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee) {
Stack<Employee> firstPath = new Stack<Employee>();
Stack<Employee> secondPath = new Stack<Employee>();
Employee root = ceo;
DFS(root, firstEmployee, firstPath);
DFS(root, secondEmployee, secondPath);
if(firstPath.peek().getId() == firstEmployee.getId() && secondPath.peek().getId() == secondEmployee.getId()){
int size1 = firstPath.size();
int size2 = secondPath.size();
int diff = Math.abs(size2-size1);
if(size1 > size2){
moveUp(firstPath, diff);
}
else{
moveUp(secondPath, diff);
}
while(firstPath.peek().getId() != secondPath.peek().getId()){
firstPath.pop();
secondPath.pop();
}
if(firstPath.size() > 0){
return firstPath.pop();
}
}
return null;
}
private static boolean DFS(Employee root, Employee target, Stack<Employee> path){
path.push(root);
if(root.getId() == target.getId()){
return true;
}
for(Employee r : root.getReports()){
boolean res = DFS(r, target, path);
if(res){
return true;
}
}
path.pop();
return false;
}
private static void moveUp(Stack<Employee> path, int diff){
while(diff > 0 && !path.isEmpty()){
path.pop();
diff--;
}
}