## Sunday, January 24, 2016

### Who is our Boss? LCA for n-array Tree - Algorithms and Problem SolvingAlgorithms and Problem Solving

Who is our Boss? LCA for n-array Tree - Algorithms and Problem SolvingAlgorithms and Problem Solving
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.
```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--;
}
}```
Read full article from Who is our Boss? LCA for n-array Tree - Algorithms and Problem SolvingAlgorithms and Problem Solving