Amazon | Onsite | Find Common Manager

4757

This problem is based on the LCA in the binary tree. In the AWS technical coding round, surely in onsite, they ask this question in their org, which is same as finnding LCA in n-ary tree.
Here is my solution.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Employee {
    List<Employee> managed = new ArrayList<>();
    int employeeId;

    Employee(int employeeId) {
        this.employeeId = employeeId;
    }
}

public class CommonManager {

    public static void main(String[] args) {

        Map<Integer, Employee> employeeHashMap = new HashMap<>();
        for (int i = 1; i <= 1000; i++)
            employeeHashMap.put(i, new Employee(i));

        Employee first = employeeHashMap.get(606);
        Employee second = employeeHashMap.get(808);

        Employee ceo = new Employee(1);
        for (int i = 2; i <= 6; i++)
            ceo.managed.add(employeeHashMap.get(i));

        List<Employee> firstList = new ArrayList<>();
        for (int i = 600; i <= 700; i++)
            firstList.add(employeeHashMap.get(i));

        List<Employee> secondList = new ArrayList<>();
        for (int i = 800; i <= 900; i++)
            secondList.add(employeeHashMap.get(i));

        employeeHashMap.get(5).managed = firstList;
        employeeHashMap.get(4).managed = secondList;

        int commonManager = commonManager(ceo, first, second);
        System.out.println(commonManager);
    }

    public static int commonManager(Employee ceo, Employee first, Employee second) {

        if (ceo == null) return -1;

        Employee[] commonManager = new Employee[1];
        commonManagerHelper(ceo, first, second, commonManager);
        return commonManager[0].employeeId;
    }

    private static int commonManagerHelper(Employee manager, Employee first, Employee second, Employee[] commonManager) {
        if (manager == null) return 0;

        int foundEmployees = 0;

        if (manager == first || manager == second) {
            foundEmployees++;
        }

        for (Employee managedEmployee : manager.managed) {
            foundEmployees += commonManagerHelper(managedEmployee, first, second, commonManager);
        }

        if (foundEmployees == 2 && commonManager[0] == null) {
            System.out.println("Manager " + manager.employeeId);
            commonManager[0] = manager;
        }
        return foundEmployees;
    }
}

Feel free to like this post to share the common awareness. Thank you!

The solution could be further generalized, by saying that k number of employees are given and you need to find out their common manager. :) That is also easy, as you need to modify this part only.

if (manager == first || manager == second) {
	foundEmployees++;
}

and the method signature accordingly.

private static int commonManagerHelper(Employee manager, Employee[] employees, Employee[] commonManager)

Comments (7)