Bloomberg LP Interview Question
Senior Software Development EngineersCountry: United States
This is a Directed Acyclic Graph, and the list given here is an adjacency list. Thus, standard BFS or DFS techniques work. There is no guarantee that it would be a tree ( there can be multiple managers to an employee ( what surprise) ). Matters not.
org_map = { 1: [2, 3, 4],
3: [5, 6, 7],
5: [8, 9, 10] }
def find_all_minions( gru ){
// gru before the minions ?
if ( !(gru @ org_map) ){ return [] }
minions = list()
// cool, let gru get's his groove back
despicable_me = list ( org_map[gru] )
while ( !empty(despicable_me) ){
// yes, bob was always faithful
bob = despicable_me.dequeue()
if ( bob @ org_map ){
// enqueue all the lesser minions
despicable_me += org_map[bob]
}
minions += bob // add bob the minions
}
minions // return value
}
printf( '%s -> %s %n', 1, find_all_minions( 1 ) )
printf( '%s -> %s %n', 2, find_all_minions( 2 ) )
printf( '%s -> %s %n', 3, find_all_minions( 3 ) )
Get the input in a string variable. Scan the string until you come across the symbol ':'. You can take a sub string of the string after the colon and then scan the string for comas and remove the comas. Then print the number reporting to the number before the colon in the main string. Hope you get the idea :)
import java.util.*;
public class Subordinates {
public static List<Integer> findSubordinates(int managerID){
Map<Integer,List<Integer>> empMap = new HashMap<>();
empMap.put(1, Arrays.asList(2,3,4));
empMap.put(3, Arrays.asList(5,6,7));
empMap.put(5, Arrays.asList(8,9,10));
empMap.put(9, Arrays.asList(11,12,13));
List<Integer> subordinates = new ArrayList<>();
for(Map.Entry<Integer, List<Integer>> emp1 : empMap.entrySet()){
if (emp1.getKey() == managerID){
for (int i=0 ; i < emp1.getValue().size(); i++) {
subordinates.add(emp1.getValue().get(i));
System.out.println("We just added emp1: "+emp1.getValue().get(i));
}
}
// System.out.println("emp1 value "+emp1.getValue());
for(Map.Entry<Integer, List<Integer>> emp2 : empMap.entrySet()){
if (emp1.getValue()!= emp2.getValue()) {
// System.out.println("emp2 value "+emp2.getValue());
if ((emp1.getKey() == managerID) || subordinates.contains(emp1.getKey())) { // Second condition is for multiple level hierarchy
for (int i=0 ; i < emp1.getValue().size(); i++) {
if ( emp1.getValue().get(i) == emp2.getKey() ) {
// we found another level of hierarchy
// add all subordinates of emp2 as indirect subordinates of emp1
for (int j=0 ; j < emp2.getValue().size(); j++) {
subordinates.add(emp2.getValue().get(j));
System.out.println("We just added emp2: "+emp2.getValue().get(j));
}
}
}
}
}
}
}
return subordinates;
}
public static void main(String[] args) {
System.out.println( findSubordinates(3));
}
}
//organization structure stored in HashMap<Integer, Iterable<Integer>> hierarchy
public LinkedList<Integer> getSubordinates(Integer id) {
LinkedList<Integer> result = new LinkedList<>();
if(hierarchy.containsKey(id)) {
for(Integer i : hierarchy.get(id)) {
result.add(i);
for(Integer j : getSubordinates(i)) {
if(result.indexOf(j) != -1) {
result.add(j);
}
}
}
}
return result;
}
void GetReporters(Employee *e, int id, vector<Employee *> &reporters, bool found = false, bool processed = false)
{
if (!processed &&
e)
{
if (found) {
reporters.push_back(e);
}
if (e->id_ == id) {
found = true;
}
for (auto reporter : e->reporters_) {
GetReporters(reporter, id, reporters, found, processed);
}
if (e->id_ == id) {
processed = true;
}
}
}
package com.practice.algo.and.ds.graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Graphs_CareerCup_EmployeeReporting {
public static void main(String[] args) {
Map<Integer,List<Integer>> empMap = new HashMap<>();
empMap.put(1, Arrays.asList(2,3,4));
empMap.put(3, Arrays.asList(5,6,7));
empMap.put(5, Arrays.asList(8,9,10));
empMap.put(9, Arrays.asList(11,12,13));
Graphs_CareerCup_EmployeeReporting o = new Graphs_CareerCup_EmployeeReporting();
System.out.println(o.getReportees(empMap,3));
}
public List<Integer> getReportees(Map<Integer,List<Integer>> empMap,int manager){
List<Integer> result = new ArrayList<>();
getReporteesHelper(result,empMap,manager);
return result;
}
private void getReporteesHelper(List<Integer> result, Map<Integer, List<Integer>> empMap, Integer manager) {
List<Integer> reportees = empMap.get(manager);
if(reportees==null)
return;
for (Integer i: reportees) {
result.add(i);
getReporteesHelper(result,empMap,i);
}
}
}
package com.practice.algo.and.ds.graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Graphs_CareerCup_EmployeeReporting {
public static void main(String[] args) {
Map<Integer,List<Integer>> empMap = new HashMap<>();
empMap.put(1, Arrays.asList(2,3,4));
empMap.put(3, Arrays.asList(5,6,7));
empMap.put(5, Arrays.asList(8,9,10));
empMap.put(9, Arrays.asList(11,12,13));
Graphs_CareerCup_EmployeeReporting o = new Graphs_CareerCup_EmployeeReporting();
System.out.println(o.getReportees(empMap,3));
}
public List<Integer> getReportees(Map<Integer,List<Integer>> empMap,int manager){
List<Integer> result = new ArrayList<>();
getReporteesHelper(result,empMap,manager);
return result;
}
private void getReporteesHelper(List<Integer> result, Map<Integer, List<Integer>> empMap, Integer manager) {
List<Integer> reportees = empMap.get(manager);
if(reportees==null)
return;
for (Integer i: reportees) {
result.add(i);
getReporteesHelper(result,empMap,i);
}
}
}
import java.util.Scanner;
public class EmpReport {
public static void main(String[] args){
Scanner sc= new Scanner(System.in);
System.out.println("enter the Employee id");
int id = sc.nextInt();
int n1=(id/2)+1+id;
int n2=n1+1;
int n3=n2+1;
System.out.println(id+":"+ n1 +","+ n2 +","+ n3 +".");
}}
import java.util.*;
/*
A company's organizational structure is represented as
1: 2, 3, 4
In the above employees with id 2, 3 and 4 report to 1
Assume the following hierarchy.
1: 2, 3, 4
3: 5, 6, 7
5: 8, 9, 10
Given an employee Id, return all the employees reporting to him directly or indirectly
*/
public class EmployeeHierarchy {
private String[] hierarchyData;
private Map<Integer, Set<Integer>> hierarchy = new HashMap<>();
public EmployeeHierarchy(String[] hierarchyData) {
this.hierarchyData = hierarchyData;
populateHierarchy(hierarchyData);
}
private void populateHierarchy(String[] hierarchyData){
for(String levelData : hierarchyData){
parseAndAddLevel(hierarchy, levelData);
}
}
private void parseAndAddLevel(Map<Integer, Set<Integer>> hierarchy, String levelData){
String[] managerEmployesPair= levelData.split(":");
//TODO: when no one reports to an employee, will we have a level data
String[] employees = managerEmployesPair[1].split(",");
Integer manager = Integer.valueOf(managerEmployesPair[0]);
Set<Integer> reportingEmployees = hierarchy.get(manager);
if(reportingEmployees==null) {
reportingEmployees = new HashSet<>();
hierarchy.put(manager, reportingEmployees);
}
for(String employee: employees){
reportingEmployees.add(Integer.valueOf(employee));
}
}
public Set<Integer> getAllDirectIndirectReportees(int employeeId){
Set<Integer> reportees = new HashSet<>();
collectAllReportees(reportees, employeeId);
return reportees;
}
private void collectAllReportees(Set<Integer> reportees, int employeeId){
Set<Integer> subReportees = this.hierarchy.get(employeeId);
if(subReportees == null){
//do nothing
}else{
reportees.addAll(subReportees);
for(Integer subEmployeeId : subReportees){
collectAllReportees(reportees, subEmployeeId);
}
}
}
}
import org.junit.jupiter.api.Test;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import static org.junit.jupiter.api.Assertions.assertEquals;
public class EmployeeHierarchyTest {
@Test
public void getDirectReportees(){
int queryEmployeeId = 1;
String[] testData = new String[]{"1:2,3,4"};
Set<Integer> expectedReportees = new HashSet<>(Arrays.asList(2,3,4));
EmployeeHierarchy employeeHierarchy = new EmployeeHierarchy(testData);
assertEquals(expectedReportees, employeeHierarchy.getAllDirectIndirectReportees(queryEmployeeId));
}
@Test
public void getIndirectReportees(){
int queryEmployeeId = 1;
String[] testData = new String[]{"1:2,3,4", "3:5,6"};
Set<Integer> expectedReportees = new HashSet<>(Arrays.asList(2,3,4,5,6));
EmployeeHierarchy employeeHierarchy = new EmployeeHierarchy(testData);
assertEquals(expectedReportees, employeeHierarchy.getAllDirectIndirectReportees(queryEmployeeId));
}
}
# organizational structure - dictionary
# each key is employee
# values are reporting employees
# assume no cycles - handle cycles via 'seen' elements
# recursively obtain all reporting employees
def reporting_employees(employee_id, organization):
employee_store = []
organization = organization
def reporting_employees_helper(employee_id):
if len(organization[employee_id]) == 0:
return
# add underlying employees to store
employee_store.append(organization[employee_id])
# recurse through direct employees
for d_emp in organization[employee_id]:
reporting_employees_helper(d_emp)
# invoke recursive helper
reporting_employees_helper(employee_id)
# flatten store of underlying employees
employee_store = sum(employee_store, [])
return employee_store
Javascript answer:
const reports = {
1: [2, 3, 4],
3: [5, 6, 7],
5: [8, 9, 10]
};
function determineReports(employeeId) {
if (typeof employeeId !== 'number' ||
!reports[employeeId]) {
return [];
}
let directReports = reports[employeeId];
for (let report of directReports) {
directReports = directReports.concat(determineReports(report));
}
return directReports;
}
#include<iostream>
#include<vector>
#include<map>
using namespace std;
void getWorkersHelper(const int& worker, map<int, vector<int>>& bosses, vector<int>& curList) {
auto it = bosses.find(worker);
if (it != bosses.end()) {
for (int x : bosses[worker]) {
if (bosses.find(worker) != bosses.end()) {// see if this worker is a boss
getWorkersHelper(x, bosses, curList);
}
curList.push_back(x);
}
}
}
vector<int> getWorkers(const int& worker, map<int, vector<int>>& bosses) {
vector<int> curList;
getWorkersHelper(worker, bosses, curList);
return curList;
}
int main() {
map<int, vector<int>> bosses;
bosses[1] = { 2,3,4 };
bosses[3] = { 5,6,7 };
bosses[5] = { 8,9,10 };
vector<int> workersOf1 = getWorkers(3, bosses);
for (int x : workersOf1) {
cout << x << ' ';
}
std::cout << std::endl;
system("PAUSE");
return 0;
}
In python we can do it easily, not only for 3 emplyoee{1,2,3}, we can do it n number of employee:
correct me if any error.
The below code will give output for around 500 employee:
if u want to increase, kindly increase the count in both for loop(i.e 10001).
x1=int(input("ENter the reportable person's ID:"))
dic={}
key=[]
sep=[]
value=[]
for i in range(1,10001,2):
key.append(i)
print(key)
count=1
for i in range(2,10001):
#if count!=3:
sep.append(i)
# print(sep)
if count==3:
value.append(sep[:])
sep.clear()
count=0
count+=1
#print(key)
#print(value)
#print(len(value))
#print(len(key))
#print(value)
for i in range(1,len(value)):
dic[i]=value[i-1]
print(dic.get(x1))
class findHeirarchy
{
Dictionary<int, List<int>> Employees;
public findHeirarchy(Dictionary<int, List<int>> dictionary)
{
Employees = dictionary;
}
internal List<int> findSubs(int parent)
{
List<int> subs = new List<int>();
if (Employees.ContainsKey(parent))
{
foreach (var key in Employees.Where(a => a.Key == parent))
{
foreach (var emp in key.Value)
{
Console.WriteLine(emp);
subs.Add(emp);
if (Employees.ContainsKey(emp))
subs = findSubs(emp);
}
}
}
return subs;
}
}
public List<Integer> companyOrg(HashMap<Integer, List<Integer>> map, int manager){
List<Integer> results = new ArrayList<>();
if(!map.containsKey(manager)) return results;
results.addAll(map.get(manager));
for(Map.Entry<Integer, List<Integer>> entry: map.entrySet()){
if(results.contains(entry.getKey())){
System.out.println(entry.getKey());
results.addAll(entry.getValue());
}
}
return results;
}
public static List<Integer> companyOrg(HashMap<Integer, List<Integer>> map, int manager){
List<Integer> results = new ArrayList<>();
if(!map.containsKey(manager)) return results;
results.addAll(map.get(manager));
for(Map.Entry<Integer, List<Integer>> entry: map.entrySet()){
if(results.contains(entry.getKey())){
System.out.println(entry.getKey());
results.addAll(entry.getValue());
}
}
return results;
}
public static List<Integer> companyOrg(HashMap<Integer, List<Integer>> map, int manager){
List<Integer> results = new ArrayList<>();
if(!map.containsKey(manager)) return results;
results.addAll(map.get(manager));
for(Map.Entry<Integer, List<Integer>> entry: map.entrySet()){
if(results.contains(entry.getKey())){
System.out.println(entry.getKey());
results.addAll(entry.getValue());
}
}
return results;
}
#include <vector>
#include <map>
#include <queue>
using namespace std;
std::vector<int> get_reporters(int id, std::map<int, std::vector<int>>& mp) {
std::vector<int> res;
std::queue<std::map<int, std::vector<int>>::iterator> qu;
auto iter = mp.find(id);
bool bFirst = true;
while (iter != mp.end()) {
if (qu.empty() && !bFirst)
break;
else if (!qu.empty()){
iter = qu.front();
qu.pop();
bFirst = false;
}
for (int i = 0; i < iter->second.size(); ++i) {
auto it = mp.find(iter->second[i]);
res.push_back(iter->second[i]);
if (it != mp.end()) {
qu.push(it);
}
}
}
return res;
}
int main()
{
std::map<int, std::vector<int>> mp = { std::pair<int, std::vector<int> >(1, {2,3,4}) ,
std::pair<int, std::vector<int> >(3, {5,6,7}) ,
std::pair<int, std::vector<int> >(5, {8,9,10}) };
std::vector<int> res = get_reporters(1, mp);
return 0;
}
import java.io.*;
import java.util.*;
class pattern1
{
public static void main(String[] args) throws IOException{
System.out.println("Enter the employee id");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int id=Integer.parseInt(br.readLine());
display(id);
}
public static void display(int empid){
int value=2;
for(int i=1;i<=empid;i+=2){
if(i==empid)
System.out.print(i+":");
for(int j=0;j<3;j++,value++)
if(i==empid)
System.out.print(value+",");
System.out.print("\n");
}
}
}
import java.io.*;
import java.util.*;
class pattern1
{
public static void main(String[] args) throws IOException{
System.out.println("Enter the employee id");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int id=Integer.parseInt(br.readLine());
display(id);
}
public static void display(int empid){
int value=2;
for(int i=1;i<=empid;i+=2){
if(i==empid)
System.out.print(i+":");
for(int j=0;j<3;j++,value++)
if(i==empid)
System.out.print(value+",");
System.out.print("\n");
}
}
}
import java.io.*;
import java.util.*;
class pattern1
{
public static void main(String[] args) throws IOException{
System.out.println("Enter the employee id");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int id=Integer.parseInt(br.readLine());
display(id);
}
public static void display(int empid){
int value=2;
for(int i=1;i<=empid;i+=2){
if(i==empid)
System.out.print(i+":");
for(int j=0;j<3;j++,value++)
if(i==empid)
System.out.print(value+",");
System.out.print("\n");
}
}
}
import java.io.*;
import java.util.*;
class pattern1
{
public static void main(String[] args) throws IOException{
System.out.println("Enter the employee id");
BufferedReader br=new BufferedReader(new
InputStreamReader(System.in));
int id=Integer.parseInt(br.readLine());
display(id);
}
public static void display(int empid){
int value=2;
for(int i=1;i<=empid;i+=2){
if(i==empid)
System.out.print(i+":");
for(int j=0;j<3;j++,value++)
if(i==empid)
System.out.print(value+",");
System.out.print("\n");
}}}
recursive Python 3 solution:
def reporting_employees(id, org_dict):
managers = org_dict.keys()
losers = []
for sub in org_dict[id]:
losers.append(sub)
if sub in managers:
losers.extend(reporting_employees(sub, org_dict))
return losers
if __name__ == '__main__':
s = {
1: [2, 3, 4],
3: [5, 6, 7],
5: [8, 9, 10]
}
reporting_employees(3, s)
}
- algolearner August 15, 2017