Morgan Stanley Interview Question
Senior Software Development EngineersCountry: India
Interview Type: In-Person
public class Employee {
String name;
Integer id;
Employee manager;
public Employee(String name, Integer id, Employee manager) {
super();
this.name = name;
this.id = id;
this.manager = manager;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public Employee getManager() {
return manager;
}
public void setManager(Employee manager) {
this.manager = manager;
}
}
import java.util.ArrayList;
import java.util.Scanner;
public class Employee_Util {
public static void main(String[] args) {
Employee ceo = new Employee("CEO", 1, null);
Employee e1 = new Employee("emp1", 1, ceo);
Employee e2 = new Employee("emp2", 1, e1);
Employee e3 = new Employee("emp3", 1, e1);
Employee e4 = new Employee("emp4", 1, e2);
ArrayList<Employee> al = new ArrayList<>();
al.add(ceo);
al.add(e1);
al.add(e2);
al.add(e3);
al.add(e4);
System.out.println("enter the manager");
Scanner s = new Scanner(System.in);
String name = s.nextLine();
int count = 0;
for (Employee i : al) {
if (i.getName().equalsIgnoreCase(name)) {
count++;
}
}
if (count > 0)
getReportees(name, al);
else
System.out.println("Invalid Input!! ");
}
private static void getReportees(String name, ArrayList<Employee> al) {
for (Employee e : al) {
if (e.getName().equalsIgnoreCase("ceo"))
;
else if (e.getManager().getName().equalsIgnoreCase(name)) {
System.out.println(e.getName());
getReportees(e.getName(), al);
}
}
}
}
public class Employee {
String name;
Integer id;
Employee manager;
public Employee(String name, Integer id, Employee manager) {
this.name = name;
this.id = id;
this.manager = manager;
}
public String getName() {
return name;
}
public Integer getId() {
return id;
}
public Employee getManager() {
return manager;
}
}
public class EmployeeUtils {
public static List<String> getReportees (List<Employee> employees, Employee managerToFind) {
Map<Employee, List<Employee>> managerToReportees = new WeakHashMap<>();
for (Employee employee: employees) {
Employee manager = employee.manager;
if (manager != null) {
List<Employee> reportees = managerToReportees.get(manager);
if (reportees == null) {
reportees = new LinkedList<>();
managerToReportees.put(manager, reportees);
}
reportees.add(employee);
}
}
List<Employee> result = recGetReportees(managerToReportees, managerToFind);
List<String> toReturn = new ArrayList<>();
for (Employee employee: result) {
toReturn.add(employee.getName());
}
return toReturn;
}
private static List<Employee> recGetReportees(Map<Employee, List<Employee>> managerToReportees, Employee managerToFind) {
List<Employee> toReturn = new ArrayList<>();
if (!managerToReportees.containsKey(managerToFind)) {
return toReturn;
} else {
for (Employee employee: managerToReportees.get(managerToFind)) {
toReturn.addAll(recGetReportees(managerToReportees, employee));
toReturn.add(employee);
}
return toReturn;
}
}
}
public class EmployeeUtilsTest {
@Test
public void testGetReportees() {
List<Employee> toTest = new ArrayList<>();
Employee arie = new Employee("arie", 0, null);
Employee libby = new Employee("libby", 1, arie);
Employee geva = new Employee("geva", 2, libby);
Employee regev = new Employee("regev", 3, libby);
Employee netush = new Employee("netush", 4, arie);
Employee shelly = new Employee ("shelly", 5, netush);
Employee ayala = new Employee("ayala", 6, netush);
Employee shay = new Employee("shay", 7, netush);
Employee firemanSam = new Employee("firemanSam", 8, regev);
Employee princess = new Employee("princess", 9, shelly);
toTest.addAll(Arrays.asList(regev, shelly, arie, netush, libby, geva, firemanSam, shay, ayala, princess));
System.out.println("arie->" + EmployeeUtils.getReportees(toTest, arie));
System.out.println("netush->" + EmployeeUtils.getReportees(toTest, netush));
System.out.println("libby->" + EmployeeUtils.getReportees(toTest, libby));
System.out.println("geva->" + EmployeeUtils.getReportees(toTest, geva));
System.out.println("regev->" + EmployeeUtils.getReportees(toTest, regev));
}
}
public class EmployeeProcessor {
public List<Employee> setEmployees(){
Employee ceo = new Employee("Nitin A", 10, null);
Employee e1 = new Employee("Nitin B", 1, ceo);
Employee e2 = new Employee("Nitin C", 2, e1);
Employee e3 = new Employee("Nitin D", 3, e1);
Employee e4 = new Employee("Nitin E", 4, e2);
Employee e5 = new Employee("Nitin F", 5, e2);
Employee e6 = new Employee("Nitin G", 6, e3);
Employee e7 = new Employee("Nitin H", 7, null);
return new ArrayList<Employee>(Arrays.asList(ceo,e1,e2,e3,e4,e5,e6));
}
public void findEmployees(Employee e1){
List<Employee> employees = setEmployees();
List<Employee> finalList = new ArrayList<Employee>();
finalList = addElements(finalList,e1,employees);
finalList.forEach(f -> StaticUtils.println(f.getName()));
}
public List<Employee> addElements(List<Employee> finalList, Employee employee, List<Employee> employees){
List<Employee> passedEmployeeList = employees.stream().filter(e -> (null!= e.getManager()) && e.getManager().equals(employee)).collect(Collectors.toList());
if(passedEmployeeList.size() != 0){
finalList.addAll(passedEmployeeList);
for(Employee e : passedEmployeeList){
addElements(finalList,e,employees);
}
}
return finalList;
}
}
public class EmployeeProcessor {
public List<Employee> setEmployees(){
Employee ceo = new Employee("Nitin A", 10, null);
Employee e1 = new Employee("Nitin B", 1, ceo);
Employee e2 = new Employee("Nitin C", 2, e1);
Employee e3 = new Employee("Nitin D", 3, e1);
Employee e4 = new Employee("Nitin E", 4, e2);
Employee e5 = new Employee("Nitin F", 5, e2);
Employee e6 = new Employee("Nitin G", 6, e3);
Employee e7 = new Employee("Nitin H", 7, null);
return new ArrayList<Employee>(Arrays.asList(ceo,e1,e2,e3,e4,e5,e6));
}
public void findEmployees(Employee e1){
List<Employee> employees = setEmployees();
List<Employee> finalList = new ArrayList<Employee>();
finalList = addElements(finalList,e1,employees);
finalList.forEach(f -> StaticUtils.println(f.getName()));
}
public List<Employee> addElements(List<Employee> finalList, Employee employee, List<Employee> employees){
List<Employee> passedEmployeeList = employees.stream().filter(e -> (null!= e.getManager()) && e.getManager().equals(employee)).collect(Collectors.toList());
if(passedEmployeeList.size() != 0){
finalList.addAll(passedEmployeeList);
for(Employee e : passedEmployeeList){
addElements(finalList,e,employees);
}
}
return finalList;
}
}
public class EmployeeProcessor {
public List<Employee> setEmployees(){
Employee ceo = new Employee("Nitin A", 10, null);
Employee e1 = new Employee("Nitin B", 1, ceo);
Employee e2 = new Employee("Nitin C", 2, e1);
Employee e3 = new Employee("Nitin D", 3, e1);
Employee e4 = new Employee("Nitin E", 4, e2);
Employee e5 = new Employee("Nitin F", 5, e2);
Employee e6 = new Employee("Nitin G", 6, e3);
Employee e7 = new Employee("Nitin H", 7, null);
return new ArrayList<Employee>(Arrays.asList(ceo,e1,e2,e3,e4,e5,e6));
}
public void findEmployees(Employee e1){
List<Employee> employees = setEmployees();
List<Employee> finalList = new ArrayList<Employee>();
finalList = addElements(finalList,e1,employees);
finalList.forEach(f -> StaticUtils.println(f.getName()));
}
public List<Employee> addElements(List<Employee> finalList, Employee employee, List<Employee> employees){
List<Employee> passedEmployeeList = employees.stream().filter(e -> (null!= e.getManager()) && e.getManager().equals(employee)).collect(Collectors.toList());
if(passedEmployeeList.size() != 0){
finalList.addAll(passedEmployeeList);
for(Employee e : passedEmployeeList){
addElements(finalList,e,employees);
}
}
return finalList;
}
}
public class EmployeeProcessor {
public List<Employee> setEmployees(){
Employee ceo = new Employee("Nitin A", 10, null);
Employee e1 = new Employee("Nitin B", 1, ceo);
Employee e2 = new Employee("Nitin C", 2, e1);
Employee e3 = new Employee("Nitin D", 3, e1);
Employee e4 = new Employee("Nitin E", 4, e2);
Employee e5 = new Employee("Nitin F", 5, e2);
Employee e6 = new Employee("Nitin G", 6, e3);
Employee e7 = new Employee("Nitin H", 7, null);
return new ArrayList<Employee>(Arrays.asList(ceo,e1,e2,e3,e4,e5,e6));
}
public void findEmployees(Employee e1){
List<Employee> employees = setEmployees();
List<Employee> finalList = new ArrayList<Employee>();
finalList = addElements(finalList,e1,employees);
finalList.forEach(f -> StaticUtils.println(f.getName()));
}
public List<Employee> addElements(List<Employee> finalList, Employee employee, List<Employee> employees){
List<Employee> passedEmployeeList = employees.stream().filter(e -> (null!= e.getManager()) && e.getManager().equals(employee)).collect(Collectors.toList());
if(passedEmployeeList.size() != 0){
finalList.addAll(passedEmployeeList);
for(Employee e : passedEmployeeList){
addElements(finalList,e,employees);
}
}
return finalList;
}
}
1. Build a Directed graph such that there is a directed edge from manager to each of its reportees.
2. Do a DFS with the manager in question.
cpp implementation:
class employee_hierarchy{
vector<vector<int>> graph;
public:
employee_hierarchy(int N){
graph.resize(N);
}
void addEmployee(int m, int r){
graph[m].push_back(r);
}
void getReportees(int e, vector<int>& reportees){
reportees.push_back(e);
auto direct_reportees = graph[e];
for_each(graph[e].begin(), graph[e].end(), [&reportees, this] (int x) -> void { getReportees(x, reportees); });
}
};
In C:
- dearayushraj April 09, 2017