Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
class Employee():
def __init__(self,id,name,employees):
self.id = id
self.name = name
self.employees = employees
def find_manager(manager, e1, e2):
ret = 0
for e in manager.employees:
if e.id == e1.id or e.id == e2.id:
ret = 1
ret += find_manager(e, e1, e2)
if ret == 2:
print manager.name
return ret
The first step is to build the employee tree.
1. take any employee 'A' in the list given and check if any other employee is a manager of 'A'. If yes, mark the new manager as 'A' and repeat the exercise until you get the root Manager.
2. Take the root manager and start constructing the employee tree in a recursive way.
Additional conditions:
1. Let every tree node have a pointer to it's parent - so we can trace back from a leaf node to common managers
2. For every employee that you add in the Tree - maintain an additional hashmap with a pointer to the node in the Tree. This is so that you can look up for the 2 input employees given in O(1)
With the tree and hashmap created - you now try and find the common manager for the 2 employees.
Cases:
1. If employee 'A' is manager of 'B' or vice versa - return the corresponding manager as the common manager needed.
2. If parent of 'A' is same as Parent of 'B' - return the parent as the common manager needed
3. If not 1) and 2) - do a recursive search again by passing A->Parent and B->Parent to the same function.
the function will return the common manager for the two employees A, B.
The first step is to build the employee tree.
1. take any employee 'A' in the list given and check if any other employee is a manager of 'A'. If yes, mark the new manager as 'A' and repeat the exercise until you get the root Manager.
2. Take the root manager and start constructing the employee tree in a recursive way.
Additional conditions:
1. Let every tree node have a pointer to it's parent - so we can trace back from a leaf node to common managers
2. For every employee that you add in the Tree - maintain an additional hashmap with a pointer to the node in the Tree. This is so that you can look up for the 2 input employees given in O(1)
With the tree and hashmap created - you now try and find the common manager for the 2 employees.
Cases:
1. If employee 'A' is manager of 'B' or vice versa - return the corresponding manager as the common manager needed.
2. If parent of 'A' is same as Parent of 'B' - return the parent as the common manager needed
3. If not 1) and 2) - do a recursive search again by passing A->Parent and B->Parent to the same function.
the function will return the common manager for the two employees A, B.
The first step is to build the employee tree.
1. take any employee 'A' in the list given and check if any other employee is a manager of 'A'. If yes, mark the new manager as 'A' and repeat the exercise until you get the root Manager.
2. Take the root manager and start constructing the employee tree in a recursive way.
Additional conditions:
1. Let every tree node have a pointer to it's parent - so we can trace back from a leaf node to common managers
2. For every employee that you add in the Tree - maintain an additional hashmap with a pointer to the node in the Tree. This is so that you can look up for the 2 input employees given in O(1)
With the tree and hashmap created - you now try and find the common manager for the 2 employees.
Cases:
1. If employee 'A' is manager of 'B' or vice versa - return the corresponding manager as the common manager needed.
2. If parent of 'A' is same as Parent of 'B' - return the parent as the common manager needed
3. If not 1) and 2) - do a recursive search again by passing A->Parent and B->Parent to the same function.
the function will return the common manager for the two employees A, B.
The first step is to build the employee tree.
1. take any employee 'A' in the list given and check if any other employee is a manager of 'A'. If yes, mark the new manager as 'A' and repeat the exercise until you get the root Manager.
2. Take the root manager and start constructing the employee tree in a recursive way.
Additional conditions:
1. Let every tree node have a pointer to it's parent - so we can trace back from a leaf node to common managers
2. For every employee that you add in the Tree - maintain an additional hashmap with a pointer to the node in the Tree. This is so that you can look up for the 2 input employees given in O(1)
With the tree and hashmap created - you now try and find the common manager for the 2 employees.
Cases:
1. If employee 'A' is manager of 'B' or vice versa - return the corresponding manager as the common manager needed.
2. If parent of 'A' is same as Parent of 'B' - return the parent as the common manager needed
3. If not 1) and 2) - do a recursive search again by passing A->Parent and B->Parent to the same function.
the function will return the common manager for the two employees A, B.
This problem is same as common ancestor problem.
/*
* Lowest common ancestor of a tree whose two nodes are given
*/
public class LowestCommonAncestor {
private static Tree findLCA(Tree ptr, String n1, String n2){
if(ptr == null){
return null;
}
if (ptr.getValue().equals(n1) || ptr.getValue().equals(n2)){
return ptr;
}
Tree left = findLCA(ptr.getLeft(), n1, n2);
Tree right = findLCA(ptr.getRight(), n1, n2);
if(left !=null && right !=null){
return ptr;
}
else {
if(left == null && right !=null){
return findLCA(ptr.getRight(), n1, n2);
}
else if(right == null && left !=null){
return findLCA(ptr.getLeft(), n1, n2);
}
else {
return null;
}
}
}
public static void main(String args[]){
Tree child11 = new Tree("D", null, null);
Tree child22 = new Tree("E", null, null);
Tree child33 = new Tree("F", null, null);
Tree child44 = new Tree("G", null, null);
Tree child1 = new Tree("B", child11, child22);
Tree child2 = new Tree("C", child33, child44);
Tree root = new Tree("A", child1, child2);
Tree lcaNode = findLCA(root, "D", "F");
System.out.println("LCA(D,F) is ->" + lcaNode!=null?lcaNode.getValue():"No LCA");
}
}
According to the question description, the root pointer is not given, only two employees are given. If there is no mistake in the question then the solution might be different.
1- Loop on employees vector in all the employees classes and build a hash table, the key will be the employee from the vector and the value will be the ID of the employee class
2- Take one of the two employees that we want to get the common manager and create another hash by tracing up the managers using hash built in step 1.
3- Do the same for the second employee but instead of building another hash, just trace up the second employee parents and check one by one from the hash built in step 2 until you find the first common manager
similar to lowest common ancestor but for list of node, e.g. employees
public Employee getLCM(Employee employee, String first, String second) {
if (employee == null || employee.reporters == null) {
return null;
}
for (Employee reporter : employee.reporters) {
if (reporter.name.equals(first) || reporter.name.equals(second)) {
return employee;
}
}
Employee firstEmployee = null;
Employee secondEmployee = null;
for (Employee reporter : employee.reporters) {
if (firstEmployee != null) {
secondEmployee = getLCM(reporter, first, second);
if (secondEmployee != null) {
return reporter;
}
} else {
firstEmployee = getLCM(reporter, first, second);
}
}
return firstEmployee;
}
This is finding common ancestor for an N-ary tree
public static class NaryNode<T> {
T value = null;
List<NaryNode<T>> children = new ArrayList<NaryNode<T>>();
public NaryNode(T value) {
this.value = value;
}
public void setChildren(List<NaryNode<T>> children) {
this.children = children;
}
public void addChild(NaryNode<T> child) {
this.children.add(child);
}
public String toString() {
return value.toString();
}
}
public static NaryNode<String> findLowestCommonAncestor(NaryNode<String> root, NaryNode<String> p, NaryNode<String> q) {
NaryNode<String> lca = LCAHelper(root, p, q, new int[1]);
return lca;
}
private static NaryNode<String> LCAHelper(NaryNode<String> node, NaryNode<String> p, NaryNode<String> q, int[] holder) {
NaryNode<String> lca = null;
if (node == null) return node;
int cnt = 0;
if (node.value.equals(p.value)) {
cnt++;
}
if (node.value.equals(q.value)) {
cnt++;
}
for (NaryNode<String> child : node.children) {
int[] temp = new int[1];
NaryNode<String> parent = LCAHelper(child, p, q, temp);
if (parent != null) return parent;
cnt += temp[0];
if (cnt >= 2) {
break;
}
}
holder[0] += cnt;
if (cnt >= 2) {
return node;
}
return lca;
}
}
struct TreeNode{
int id;
string name;
vector<string> children;
};
TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *n1, TreeNode *n2){
if(root == NULL){
return NULL;
}
vector<TreeNode*> res;
for(int i = 0; i < root->children.size(); i++){
res.push_back(lowestCommonAncestor(root->children[i], n1, n2));
}
if(root == n1 || root == n2){
return root;
}
int isN1 = -1, isN2 = -1;
for(int i = 0; i < res.size(); i++){
if(res[i] != NULL)
isN1 = i;
if(res[i] != NULL)
isN2 = i;
}
if(isN1 != -1 && isN2 != -1){
return root;
}
else{
if(isN1 != -1)
return res[isN1];
else if(isN2 != -1)
return res[isN2];
else
return NULL;
}
}
This problem is actually a version of finding the common parent node when we are given 2 nodes randomly in a binary tree. The thing that is missing in this question is how do we move up. By that I mean if a manger has one of the "given" ids in his vector and that id happens to the manager of the 2nd "given" id. We have know way of moving up 2 verify this.
- amitsriv9 October 10, 2015