Closet Common Manager

-- 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

ImplementEmployee 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.

Solution

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--;
    }
}

Approach - LCA Recursive for N-Ary Tree

public static Employee comManagerTree(Employee ceo, Employee emp1, Employee emp2) {
    if (ceo == null || ceo == emp1 || ceo == emp2) {
        return ceo;
    }
    boolean judgeemp1 = false;
    boolean judgeemp2 = false;
    for (Employee em: ceo.getReports()) {
        Employee result = comManagerTree(em, emp1, emp2);
        if (result == emp1) {
            judgeemp1 = true;
        } else if (result == emp2) {
            judgeemp2 = true;
        } else if (result != null) {
            return result;
        }
    }
    if (judgeemp1 == true && judgeemp2 == true) {
        return ceo;
    } else if (judgeemp1 == true) {
        return emp1;
    } else if (judgeemp2 == true) {
        return emp2;
    }
    return null;

}

Reference

Problems and Solution: http://www.zrzahid.com/who-is-the-boss-lca-for-n-array-tree/