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.
Read full article from 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--; } }