Google Interview Question
Software EngineersCountry: UK
Interview Type: In-Person
Part 1 is easy - just go through all records and list the record if the ManagerID is equal to the given ID
Part 2 - one solution is to build a (hierarchy) tree of all employees, search for the entry for employee with the given ID and then list its subtree depth-first. This is no problem for 250 employees, but if there were more then we might want to explore different solution.
Use the nested hash tables (map with managerId as a key and set of employeeIds as a value). Or even unsigned char company[250][250] in C if you want (assuming it's initially zeroed and a non-zero value means accessory). You traverse the input and add corresponding employee to a particular manager (like company[managerId].add(employeeId)). Now printing direct reporters is trivial. Printing all reporters is just BFS starting from direct reporters of a particular manager.
Build a tree from the input:
class Node {
Employee employee;
ArrayList<Node> manages = new ArrayList<>();
Node(Employee e){
employee = e;
}
}
Node root = null;
HashMap<Integer, Node> byId;
for(Employee e: employees){
Node node = new Node(e);
byId.put(e.id, node);
if(e.managerId == null){
root = node;
}
}
for(Employee e: employees){
Node node = byId.get(e.id);
if(node == root){
continue;
}
Node managerNode = byId.get(node.employee.managerId);
managerNode.manages.add(node);
}
Part 1:
Node node = byId.get(id);
for (Node n: node.manages){
Employee e = n.employee;
System.out.println(e.id);
}
Part 2:
void traverseAndPrint(Node node, Node root){
if(node != root){
System.out.println(node.employee.id);
}
for(Node child: node.manages){
traverse(child, root);
}
}
traverseAndPrint(byId.get(id), root);
Create a directed graph of managers and their reporters.
How to create.
Ans.
Create a HashMap<Integer, ArrayList<Integer>> //Key: ManagerID value array of empids
For each record 1 To N
if HashMap contains managerID
get the ArrayList as value for this key
enter the empId into the ArrayList
if the HashMap does not contain the empId as key, insert it
else
create an ArrayList
append the employee in the ArrayList
put this ArrayList for the key as ManagerId in this record
if the HashMap does not contain the empId as key, insert it
Run BFS for any key of the HashMap
use strict;
open(FH,"Employee_list.txt");
my @employee_list = <FH>; #format as: employee_ID \t manager_ID
close FH;
my %hash_employee;
foreach (@employee_list) {
chomp;
@list = split("\t",@employee_list);
if (scalar(@list)>1){ #should have a manager ID or it will be the boss!
$hash_employee{$list[0]}=$list[1]; # $list[0] is employee ID, $list[1] is manager ID
}else {
$hash_employee{$list[0]}='boss';
}
}
$calling_ID = ARGV[0];
# section 1: find direct reporting ID
my @direct_reporting_ID;
foreach (keys %hash_employee) {
push @direct_reporting_ID, $_ if ($list{$_} eq $calling_ID);
}
print "direct reporting IDs: \n";
foreach (@direct_reporting_ID) {
print $_."\n";
}
# section 2: find all related reporting ID
my @all_related_reporting_ID;
foreach (keys %hash_employee) {
my $signal = 1;
my $origin_id = $_;
my $temp_id = $_;
while ($signal == 1) {
if ($list{$temp_id} eq $calling_ID) #match the case
push @all_related_reporting_ID, $origin_id ;
$signal=0;
}elsif($list{$temp_id} eq 'boss'){ #stop when reached the boss
$signal=0;
}else{ #find its manager's manager.
$temp_id = $list{$temp_id};
}
}
}
print "all including indirect reporting IDs: \n";
foreach (@all_related_reporting_ID) {
print $_."\n";
}
The managers id seems unnecessary depending how your tree is built. Hierarchical organization is usually searched with a breadth first search.
- CareerCupDom March 23, 2015Assuming your tree is setup as root links to a set of employees, then employees that report to those nodes are linked to it, etc.
You would:
1) Do a BFS until you find your matching employee id in the queue
2) Save off a pointer to that node and clear the queue because we dont care about anyone that this employee reports to, only who reports to him
3) Push all the nodes that are connected to this node onto the stack and list them out, this answers part 1 and lists all directly reporting employees
4) Continue doing a bfs until the queue is empty. Every time you push a node you will list out this employee. This answers part two and will report all indirectly reporting employees.
It seems like there should be a quicker way to getting to the first node without having to search the first part of the tree. If space isn't a concern you could have a hashmap with a kv pair of employee id to a pointer to his node. This would give you a fast lookup to start. You could limit the size of the table by only including ids that have at least one report.
There is no way to avoiding walking every node after the starting id is found since you want to list out all of those nodes.