CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for SDE1s


Country: Hong Kong



Comment hidden because of low score. Click to expand.
2
of 2 vote

public class CommonManagerTopBottom {
    static class Employee {
        final String name;
        List<Employee> reporters;

        public Employee(final String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return "Employee{" +
                    "name='" + name + '\'' +
                    '}';
        }
    }

    public static Employee closestCommonManager(final Employee ceo, final Employee firstEmployee, final Employee secondEmployee) {
        if (ceo == null || firstEmployee == null || secondEmployee == null)
            return null;
        if (!covers(ceo, firstEmployee) && covers(ceo, secondEmployee))
            return null;
        final Queue<Employee> workingQueue = new LinkedList<>();
        workingQueue.offer(ceo);
        Employee closestKnownManager = null;
        while (!workingQueue.isEmpty()) {
            Employee employee = workingQueue.poll();
            if (covers(employee, firstEmployee) && covers(employee, secondEmployee)) {
                closestKnownManager = employee;
                for (Employee em : employee.reporters) {
                    workingQueue.offer(em);
                }
            }
        }
        return closestKnownManager;
    }

    public static boolean covers(final Employee manager, final Employee employee) {
        if (manager == null)
            return false;
        if (manager.name.equals(employee.name))
            return true;
        if (manager.reporters == null)
            return false;

        boolean covers = false;
        for (Employee em : manager.reporters) {
            covers = covers || covers(em, employee);
        }
        return covers;
    }

    public static void main(String[] args) {
        Employee samir = new Employee("samir");
        Employee dom = new Employee("dom");
        Employee michael = new Employee("michael");


        Employee peter = new Employee("peter");
        Employee porter = new Employee("porter");
        Employee bob = new Employee("bob");

        dom.reporters = Arrays.asList(bob, peter, porter);

        Employee milton = new Employee("milton");
        Employee nina = new Employee("nina");

        peter.reporters = Arrays.asList(milton, nina);

        Employee bill = new Employee("bill");
        bill.reporters = Arrays.asList(dom, samir, michael);

        System.out.println(closestCommonManager(bill, milton, nina));
        System.out.println(closestCommonManager(bill, nina, porter));
        System.out.println(closestCommonManager(bill, nina, samir));
        System.out.println(closestCommonManager(bill, peter, nina));
    }
}

- Coder February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

c# solution:

public class Employee
        {
            public int Id { get; set; }
            public string Name { get; set; }
            public List<Employee> Reports { get; set; }
        }

 public static Employee ClosestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee)
        {
            Employee currentClosestManager = ceo;

            if (!Covers(ceo, firstEmployee) || !Covers(ceo, secondEmployee))
                return null;
            
            Queue q = new Queue();
            q.Enqueue(ceo);

            while (!q.IsEmpty())
            {
                var emp =(Employee) q.Dequeue();
                if (emp != null)
                {
                    foreach (var employee in emp.Reports)
                    {
                        if (Covers(employee, firstEmployee) && Covers(employee, secondEmployee) 
                            && (employee.Id != firstEmployee.Id && employee.Id != secondEmployee.Id))
                        {
                                currentClosestManager = employee;
                                q.Enqueue(employee);
                        }
                    }
                }
            }
            return currentClosestManager;

        }

        public static bool Covers(Employee root, Employee p)
        {
            if (root == null)
                return false;

            if (root.Id == p.Id)
                return true;

            foreach (var employee in root.Reports)
            {
                if (Covers(employee, p))
                {
                    return true;
                }
            }
            return false;
        }

//Driver program

public static void Test()
        {
            var bill = new Employee{Id = 1,Name = "Bill",Reports = new List<Employee>()};
            var dom = new Employee { Id = 2, Name = "Dom",Reports = new List<Employee>() };
            var samir = new Employee { Id = 3, Name = "Samir" ,Reports = new List<Employee>()};
            var michael = new Employee { Id = 4, Name = "Michael",Reports = new List<Employee>() };
            var bob = new Employee { Id = 5, Name = "Bob",Reports = new List<Employee>() };
            var peter = new Employee { Id = 6, Name = "Peter",Reports = new List<Employee>() };
            var porter = new Employee { Id = 7, Name = "Porter",Reports = new List<Employee>() };
            var milton = new Employee { Id = 8, Name = "Milton",Reports = new List<Employee>() };
            var nina = new Employee { Id = 9, Name = "Nina",Reports = new List<Employee>() };

            peter.Reports.Add(milton);
            peter.Reports.Add(nina);

            dom.Reports.Add(bob);
            dom.Reports.Add(peter);
            dom.Reports.Add(porter);

            bill.Reports.Add(dom);
            bill.Reports.Add(samir);
            bill.Reports.Add(michael);

            var ccm = ClosestCommonManager(bill, milton, nina);
            Console.WriteLine(ccm.Name);

            ccm = ClosestCommonManager(bill, nina, porter);
            Console.WriteLine(ccm.Name);

            ccm = ClosestCommonManager(bill, nina, samir);
            Console.WriteLine(ccm.Name);

            ccm = ClosestCommonManager(bill, peter, nina);
            Console.WriteLine(ccm.Name);
        }

- sandeepparekh9 January 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Lowest common ancestor direct application
Here is my implementation.

public class Employee {
	  private String name;
	  private List<Employee> reportee;
	  private Employee manager;
	  Employee(String name) {
		  this.name = name;		
		  reportee = new ArrayList<>();
	  }
	  public  void setManager(Employee m) {
		  manager = m;
	  }
	  public  void addReprotee(Employee e) {		 
			  reportee.add(e);
			  e.manager = this;
	  }	  
	  
	  //O(log(n)) time complexity, O(1) memory
	  static Employee closestCommonManager2(Employee a, Employee b) {
		  Employee e1 = a;
		  Employee e2 = b;
		  int h1 = 0;
		  int h2 = 0;
		  while (e1 != null || e2 != null) {
			  if (e1 != null) {				
			  	e1 = e1.manager ;
			  	h1++;
			  }
			  if (e2 != null) {				
				  	e2 = e2.manager ;
				  	h2++;
			  }	  
		  }				  
		  int diff = Math.abs(h1 - h2);
		  if(h1 > h2) {
			  e1 = a;
			  e2 = b;			  
		  } else {			 
			  e1 = b;
			  e2 = a;
		  }
		  while (diff > 0) {
			  e1 = e1.manager;
			  diff--;
		  }
		  while (e1 != e2) {
			  e1 = e1.manager ;
			  e2 = e2.manager ;
		  }
		  return e1;
	  }
	  
	  //O(log(n)) time complexity, O(log(n)) memory
	  static Employee closestCommonManager(Employee a, Employee b) {
		 
		  Stack<Employee> ls1 = new Stack<Employee>();
		  Stack<Employee> ls2 = new Stack<Employee>();		
		  while (a != null || b != null) {
			  if (a != null) {
				ls1.push(a);
			  	a = a.manager ;
			  }
			  if (b != null) {
				  ls2.push(b);
				  b = b.manager;
			  }
			  
		  }		
		  while(!ls1.isEmpty() && !ls2.isEmpty()) {
			  if (ls1.peek() != ls2.peek()) {
				  break;
			  }
			  a = ls1.pop();
			  ls2.pop();			  
		  }
		  return a;
	  }
	  
	  public String toString() {
		  return name;
	  }
  }

- EPavlova January 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static Node lca(Node node, Node nodeA, Node nodeB) {
if (node == null)
return null;
if (node.data == nodeA.data || node.data == nodeB.data)
return node;

List<Node> children = node.chidren;
int count = 0;
Node lca = null;
for (Node n : children) {
Node tmpNode = lca(n, nodeA, nodeB);

if (tmpNode != null) {
lca = tmpNode;
count++;
}
}
if (count == 2) {
return node;
}

return lca;
}

- Vishal Mehta January 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static Node lca(Node node, Node nodeA, Node nodeB) {
		if (node == null)
			return null;
		if (node.data == nodeA.data || node.data == nodeB.data)
			return node;

		List<Node> children = node.chidren;
		int count = 0;
		Node lca = null;
		for (Node n : children) {
			Node tmpNode = lca(n, nodeA, nodeB);

			if (tmpNode != null) {
				lca = tmpNode;
				count++;
			}
		}
		if (count == 2) {
			return node;
		}

		return lca;
	}

- Vishal Mehta January 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are definitely better approaches to traversing the Boss->employee tree, but this is a decent working solution that passes a wide enough arrangement of tests.

//level.h
#include <string>
#include <vector>

using namespace std;




class level
{
	public:
		struct node
		{
			string Name;
			level* Down;
			node(string Name_):Name(Name_),Down(NULL){};
		};

		string Boss;
		int Depth;
		vector<node*> Sub;
		
		level(string Boss_, vector<node*> sub_,int d_):Boss(Boss_),Sub(sub_),Depth(d_){};

		vector<node*> insertNode(string IDone, string IDtwo, string IDthree)
		{
			vector<node*> Sub(3);
			Sub[0] = new node(IDone);
			Sub[1] = new node(IDtwo);
			Sub[2] = new node(IDthree);
			return Sub;
		}

};

//main.cpp
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include "level.h"

using namespace std;


class Hierarchy
{
	private:

		/*
		level* findEmployee(level* t,string Boss_)
		{
			for(int i=0;i<3;i++)
			{
				if(t!=NULL && t->Sub[i]->Name.compare(Boss_)==0)
					if(t->Sub[i]->Down==NULL)
					{
						return t;
						break;
					}
					else 
						cout<<"ERROR: This employee is already a manager";
				if(t->Sub[i]->Down)
					findEmployee(t->Sub[i]->Down,Boss_);
			}
		}
		*/
		
		void printEmployeeChart(level* t)
		{	
			cout<<"DEPTH: "<<t->Depth<<"   "<<t->Boss<<" -> [ ";
			for(int i=0; i<3; i++)
				cout<<t->Sub[i]->Name<<" ";
			cout<<"]"<< endl ;
			

			for(int i=0; i<3; i++)
			{
				if(t->Sub[i]->Down)
					printEmployeeChart(t->Sub[i]->Down);
			}

		}


		level* root;
	public:
		Hierarchy()
		{
			root = NULL;
		}

		void insertCEO(string Boss_, string IDone, string IDtwo, string IDthree)
		{
			if(root==NULL)
				root = new level(Boss_, root->insertNode(IDone,IDtwo,IDthree), 1);
			else
				cout<<"ERROR: CEO already declared.";
		}
		
		void printEmployeeChart()
		{
			printEmployeeChart(root);
		}

		void insertLevel(string Boss_, string IDone, string IDtwo, string IDthree,level* t)
		{
			for(int i=0;i<3;i++)
				if(t->Sub[i]->Down)
					insertLevel(Boss_,IDone,IDtwo,IDthree,t->Sub[i]->Down);
			for(int i=0;i<3;i++)
			{
				if(t->Sub[i]->Name.compare(Boss_)==0)
					if(t->Sub[i]->Down==NULL)
					{
						t->Sub[i]->Down = new level(Boss_,t->insertNode(IDone,IDtwo,IDthree),(t->Depth+1));
						break;
					}
					else 
						cout<<"ERROR: This employee is already a manager";
			}
		}
		void insertLevel(string Boss_, string IDone, string IDtwo, string IDthree)
		{
			insertLevel(Boss_,IDone,IDtwo,IDthree,root);
		}

		void findEmployee(string ID, level* t, stack<level*> &s,string &Boss)
		{
			s.push(t);
			for(int i=0;i<3;i++)
			{
				if(t->Sub[i]->Name.compare(ID)==0)
				{
					Boss = t->Boss; 
					return;
				}
				if(t->Sub[i]->Down)
					findEmployee(ID,t->Sub[i]->Down,s,Boss);
			}
			if(s.top()->Boss.compare(Boss)!=0)
				s.pop();
		}

		string closestCommonManager(string IDone,string IDtwo)
		{
			stack<level*> s1;
			stack<level*> s2;
			string Boss = "";
			findEmployee(IDone,root,s1,Boss);
			Boss = "";
			findEmployee(IDtwo,root,s2,Boss);
			
			while(s1.size()!=s2.size())
			{
				
				if( (s1.size()==(s2.size()+1)) && s1.top()->Boss==IDtwo )
					return IDtwo;
				else if( (s1.size()+1)==s2.size() && s2.top()->Boss==IDone )
					return IDone;

				if(s1.size()>s2.size())
					s1.pop();
				else if(s2.size()>s1.size())
					s2.pop();
			}
			while(s1.top()->Boss!=s2.top()->Boss)
			{
				s1.pop();
				s2.pop();
			}
			
			return s1.top()->Boss;
		}
};


int main()
{
	Hierarchy h;
	
	h.insertCEO("Mark","Alan","Jeff","Jacob");
	h.insertLevel("Alan","Ryan","Josh","Jon");
	h.insertLevel("Jeff","Cody","Cameron","Kyle");
	h.insertLevel("Kyle","Kevin","Christian","Dan");
	h.insertLevel("Dan","Derk","Dylan","Jordon");
	h.insertLevel("Dylan","Becca","Bobbi","Brit");
	h.insertLevel("Ryan","Sam","Charlie","Lisa");

	h.printEmployeeChart();
	
	cout<<endl;

	//Case 1: Both ID share the same the boss;
	cout<<h.closestCommonManager("Ryan","Josh")<<endl; //expect Alan
	//Case 2: Same level one ID is The boss;
	cout<<h.closestCommonManager("Becca","Dylan")<<endl; //expect Dylan
	//Case 3: One ID is deeper than other, both IDs follow along the same branch, neither are bosses.
	cout<<h.closestCommonManager("Cody","Kevin")<<endl; //expect jeff
	//Case 4: One ID is deeper than other, both IDs follow along the same branch, one is a boss.
	cout<<h.closestCommonManager("Kevin","Dylan")<<endl; //expect kyle
	//Case 5: IDs follow different branches.
	cout<<h.closestCommonManager("Ryan","Cody")<<endl; //expect mark

	
	system("pause");
}

- Dmp January 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are definitely better approaches to traversing the Boss->employee tree, but this is a decent working solution that passes a wide enough arrangement of tests.

//level.h
#include <string>
#include <vector>

using namespace std;




class level
{
	public:
		struct node
		{
			string Name;
			level* Down;
			node(string Name_):Name(Name_),Down(NULL){};
		};

		string Boss;
		int Depth;
		vector<node*> Sub;
		
		level(string Boss_, vector<node*> sub_,int d_):Boss(Boss_),Sub(sub_),Depth(d_){};

		vector<node*> insertNode(string IDone, string IDtwo, string IDthree)
		{
			vector<node*> Sub(3);
			Sub[0] = new node(IDone);
			Sub[1] = new node(IDtwo);
			Sub[2] = new node(IDthree);
			return Sub;
		}

};

//main.cpp
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include "level.h"

using namespace std;


class Hierarchy
{
	private:

		/*
		level* findEmployee(level* t,string Boss_)
		{
			for(int i=0;i<3;i++)
			{
				if(t!=NULL && t->Sub[i]->Name.compare(Boss_)==0)
					if(t->Sub[i]->Down==NULL)
					{
						return t;
						break;
					}
					else 
						cout<<"ERROR: This employee is already a manager";
				if(t->Sub[i]->Down)
					findEmployee(t->Sub[i]->Down,Boss_);
			}
		}
		*/
		
		void printEmployeeChart(level* t)
		{	
			cout<<"DEPTH: "<<t->Depth<<"   "<<t->Boss<<" -> [ ";
			for(int i=0; i<3; i++)
				cout<<t->Sub[i]->Name<<" ";
			cout<<"]"<< endl ;
			

			for(int i=0; i<3; i++)
			{
				if(t->Sub[i]->Down)
					printEmployeeChart(t->Sub[i]->Down);
			}

		}


		level* root;
	public:
		Hierarchy()
		{
			root = NULL;
		}

		void insertCEO(string Boss_, string IDone, string IDtwo, string IDthree)
		{
			if(root==NULL)
				root = new level(Boss_, root->insertNode(IDone,IDtwo,IDthree), 1);
			else
				cout<<"ERROR: CEO already declared.";
		}
		
		void printEmployeeChart()
		{
			printEmployeeChart(root);
		}

		void insertLevel(string Boss_, string IDone, string IDtwo, string IDthree,level* t)
		{
			for(int i=0;i<3;i++)
				if(t->Sub[i]->Down)
					insertLevel(Boss_,IDone,IDtwo,IDthree,t->Sub[i]->Down);
			for(int i=0;i<3;i++)
			{
				if(t->Sub[i]->Name.compare(Boss_)==0)
					if(t->Sub[i]->Down==NULL)
					{
						t->Sub[i]->Down = new level(Boss_,t->insertNode(IDone,IDtwo,IDthree),(t->Depth+1));
						break;
					}
					else 
						cout<<"ERROR: This employee is already a manager";
			}
		}
		void insertLevel(string Boss_, string IDone, string IDtwo, string IDthree)
		{
			insertLevel(Boss_,IDone,IDtwo,IDthree,root);
		}

		void findEmployee(string ID, level* t, stack<level*> &s,string &Boss)
		{
			s.push(t);
			for(int i=0;i<3;i++)
			{
				if(t->Sub[i]->Name.compare(ID)==0)
				{
					Boss = t->Boss; 
					return;
				}
				if(t->Sub[i]->Down)
					findEmployee(ID,t->Sub[i]->Down,s,Boss);
			}
			if(s.top()->Boss.compare(Boss)!=0)
				s.pop();
		}

		string closestCommonManager(string IDone,string IDtwo)
		{
			stack<level*> s1;
			stack<level*> s2;
			string Boss = "";
			findEmployee(IDone,root,s1,Boss);
			Boss = "";
			findEmployee(IDtwo,root,s2,Boss);
			
			while(s1.size()!=s2.size())
			{
				
				if( (s1.size()==(s2.size()+1)) && s1.top()->Boss==IDtwo )
					return IDtwo;
				else if( (s1.size()+1)==s2.size() && s2.top()->Boss==IDone )
					return IDone;

				if(s1.size()>s2.size())
					s1.pop();
				else if(s2.size()>s1.size())
					s2.pop();
			}
			while(s1.top()->Boss!=s2.top()->Boss)
			{
				s1.pop();
				s2.pop();
			}
			
			return s1.top()->Boss;
		}
};


int main()
{
	Hierarchy h;
	
	h.insertCEO("Mark","Alan","Jeff","Jacob");
	h.insertLevel("Alan","Ryan","Josh","Jon");
	h.insertLevel("Jeff","Cody","Cameron","Kyle");
	h.insertLevel("Kyle","Kevin","Christian","Dan");
	h.insertLevel("Dan","Derk","Dylan","Jordon");
	h.insertLevel("Dylan","Becca","Bobbi","Brit");
	h.insertLevel("Ryan","Sam","Charlie","Lisa");

	h.printEmployeeChart();
	
	cout<<endl;

	//Case 1: Both ID share the same the boss;
	cout<<h.closestCommonManager("Ryan","Josh")<<endl; //expect Alan
	//Case 2: Same level one ID is The boss;
	cout<<h.closestCommonManager("Becca","Dylan")<<endl; //expect Dylan
	//Case 3: One ID is deeper than other, both IDs follow along the same branch, neither are bosses.
	cout<<h.closestCommonManager("Cody","Kevin")<<endl; //expect jeff
	//Case 4: One ID is deeper than other, both IDs follow along the same branch, one is a boss.
	cout<<h.closestCommonManager("Kevin","Dylan")<<endl; //expect kyle
	//Case 5: IDs follow different branches.
	cout<<h.closestCommonManager("Ryan","Cody")<<endl; //expect mark

	
	system("pause");
}

- Dmp January 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node {
String name;
ArrayList<Node> employees;

public Node(String string, ArrayList<Node> object) {
// TODO Auto-generated constructor stub
name = string;
employees = object;
}

public Node() {
// TODO Auto-generated constructor stub
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public ArrayList<Node> getEmployees() {
return employees;
}

public void setEmployees(ArrayList<Node> employees) {
this.employees = employees;
}
}

public class NodeStatus {
int count;
Node node;

public NodeStatus(int i, Node object) {
// TODO Auto-generated constructor stub
count = i;
node = object;
}

public int getCount() {
return count;
}

public void setCount(int count) {
this.count = count;
}

public Node getNode() {
return node;
}

public void setNode(Node node) {
this.node = node;
}

}

public NodeStatus findLowestCommonAncestor(Node root, Node node1, Node node2) {
if (root == null || node1 == null || node2 == null) {
return new NodeStatus(0, null);
}
if (node1 == node2) {
return new NodeStatus(2, node1);
}
if (root.getEmployees() == null || root.getEmployees().isEmpty()) {
if (root.name == node1.name || root.name == node2.name) {
return new NodeStatus(1, null);
}
return new NodeStatus(0, null);
}

ArrayList<Node> employees = root.getEmployees();
NodeStatus currentNodeStatus, levelNodeStatus = new NodeStatus(0, null);
for (int i = 0; i < employees.size(); i++) {
currentNodeStatus = findLowestCommonAncestor(employees.get(i), node1, node2);
if (currentNodeStatus.getCount() == 2) {
return currentNodeStatus;
}
if (currentNodeStatus.getCount() == 1) {
if (root.name.equals(node1.name) || root.name.equals(node2.name) || levelNodeStatus.getCount() == 1) {
return new NodeStatus(2, root);
}
levelNodeStatus.setCount(currentNodeStatus.getCount());
}
}
return levelNodeStatus;
}

- Anonymous February 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node {
String name;
ArrayList<Node> employees;

public Node(String string, ArrayList<Node> object) {
// TODO Auto-generated constructor stub
name = string;
employees = object;
}

public Node() {
// TODO Auto-generated constructor stub
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public ArrayList<Node> getEmployees() {
return employees;
}

public void setEmployees(ArrayList<Node> employees) {
this.employees = employees;
}
}

public class NodeStatus {
int count;
Node node;

public NodeStatus(int i, Node object) {
// TODO Auto-generated constructor stub
count = i;
node = object;
}

public int getCount() {
return count;
}

public void setCount(int count) {
this.count = count;
}

public Node getNode() {
return node;
}

public void setNode(Node node) {
this.node = node;
}

}

public NodeStatus findLowestCommonAncestor(Node root, Node node1, Node node2) {
if (root == null || node1 == null || node2 == null) {
return new NodeStatus(0, null);
}
if (node1 == node2) {
return new NodeStatus(2, node1);
}
if (root.getEmployees() == null || root.getEmployees().isEmpty()) {
if (root.name == node1.name || root.name == node2.name) {
return new NodeStatus(1, null);
}
return new NodeStatus(0, null);
}

ArrayList<Node> employees = root.getEmployees();
NodeStatus currentNodeStatus, levelNodeStatus = new NodeStatus(0, null);
for (int i = 0; i < employees.size(); i++) {
currentNodeStatus = findLowestCommonAncestor(employees.get(i), node1, node2);
if (currentNodeStatus.getCount() == 2) {
return currentNodeStatus;
}
if (currentNodeStatus.getCount() == 1) {
if (root.name.equals(node1.name) || root.name.equals(node2.name) || levelNodeStatus.getCount() == 1) {
return new NodeStatus(2, root);
}
levelNodeStatus.setCount(currentNodeStatus.getCount());
}
}
return levelNodeStatus;
}

- sandeep February 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

employee = {
    "BILL" : ["DOM", "SAMIR","MICHAEL"],
    "DOM" : ["BOB", "PETER", "PORTER"],
    "PETER" : ["MILTON", "NINA"],
    }
	
def dfs_path(graph, end, start = 'BILL', path=None):
    if path is None:
        path = [start]
    if start == end:
        yield path
    for next in set(graph[start]) - set(path):
        try:
            for i in dfs_path(graph, end, next, path + [next]):
                yield i
        except KeyError:
            continue

def closestCommonManager(name1,name2):
    path_name1 = []
    path_name2 = []
    for name in dfs_path(employee,name1):
        path_name1 += name
    for name in dfs_path(employee,name2):
        path_name2 += name
    max_len = max(path_name1.__len__(),path_name2.__len__())    
##    print path_name1,path_name2,max_len
    for i in range(max_len):
        try:
            if path_name1[i] != path_name2[i]:
                break
        except IndexError:
            print path_name1[i - 1]
            return            
    print path_name1[i -1]

closestCommonManager('MILTON','NINA') :: PETER
closestCommonManager('PORTER','NINA') :: DOM
closestCommonManager('SAMIR','NINA')  :: BILL
closestCommonManager('PETER','NINA')  :: PETER

- praveen pandit March 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

- Ankit March 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

lowest-common-ancestor-binary-tree-set-1

- Ankit March 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Employee:
    def __init__(self,data):
        self.data=data
        self.children=[]
    def add_child(self,obj):
        self.children.append(obj)
    def get_name(self):
        return self.data
    def print_child(self):
        print self.data
    def print_all_child(self):
        for child in self.children:
            print child.data

def get_dict_manager_name(root):
    dict_name_node={}
    dict_name_parent={}
    dict_name_node[root.data]=root
    list_=[root]
    while len(list_) !=0:
        node=list_.pop()
        for child in node.children:
            dict_name_node[child.data]=child
            dict_name_parent[child.data]=node
            list_.append(child)
    return dict_name_parent,dict_name_node
        
def closest_common_manager(name1,name2):
    dict_name_parent,dict_name_node=get_dict_manager_name(root)
    node1=dict_name_node[name1]
    node2=dict_name_node[name2]
    list1=[]
    list2=[]
    common_ancestor=root
    while node1 != root or node2!=root:
        if node1==node2:
            common_ancestor=node1
            break
        if node1 in list2:
            common_ancestor=node1
            break
        if node2 in list1:
            common_ancestor=node2
            break
        list1.append(node1)
        list2.append(node2)
        if node1 !=root:
            node1=dict_name_parent[node1.data]
        if node2 != root:
            node2=dict_name_parent[node2.data]
    print "Ancestor of ",name1," and ",name2," is ", common_ancestor.data
        
#driver program
root=Employee("bill")
dom=Employee("Dom")
root.add_child(dom)
root.add_child(Employee("samir"))
root.add_child(Employee("michael"))

dom.add_child(Employee("bob"))
dom.add_child(Employee("porter"))
peter=Employee("peter")
dom.add_child(peter)

peter.add_child(Employee("milton"))
peter.add_child(Employee("nina"))

closest_common_manager("milton","nina")
closest_common_manager("nina","porter")
closest_common_manager("nina","samir")
closest_common_manager("peter","nina")

- viz March 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code :

class Employee:
    def __init__(self,data):
        self.data=data
        self.children=[]
    def add_child(self,obj):
        self.children.append(obj)
    def get_name(self):
        return self.data
    def print_child(self):
        print self.data
    def print_all_child(self):
        for child in self.children:
            print child.data

def get_dict_manager_name(root):
    dict_name_node={}
    dict_name_parent={}
    dict_name_node[root.data]=root
    list_=[root]
    while len(list_) !=0:
        node=list_.pop()
        for child in node.children:
            dict_name_node[child.data]=child
            dict_name_parent[child.data]=node
            list_.append(child)
    return dict_name_parent,dict_name_node
        
def closest_common_manager(name1,name2):
    dict_name_parent,dict_name_node=get_dict_manager_name(root)
    node1=dict_name_node[name1]
    node2=dict_name_node[name2]
    list1=[]
    list2=[]
    common_ancestor=root
    while node1 != root or node2!=root:
        if node1==node2:
            common_ancestor=node1
            break
        if node1 in list2:
            common_ancestor=node1
            break
        if node2 in list1:
            common_ancestor=node2
            break
        list1.append(node1)
        list2.append(node2)
        if node1 !=root:
            node1=dict_name_parent[node1.data]
        if node2 != root:
            node2=dict_name_parent[node2.data]
    print "Ancestor of ",name1," and ",name2," is ", common_ancestor.data
        
#driver program
root=Employee("bill")
dom=Employee("Dom")
root.add_child(dom)
root.add_child(Employee("samir"))
root.add_child(Employee("michael"))

dom.add_child(Employee("bob"))
dom.add_child(Employee("porter"))
peter=Employee("peter")
dom.add_child(peter)

peter.add_child(Employee("milton"))
peter.add_child(Employee("nina"))

closest_common_manager("milton","nina")
closest_common_manager("nina","porter")
closest_common_manager("nina","samir")
closest_common_manager("peter","nina")

- viz March 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node ccm(Node n1, Node n2){
    n1.visited=true;
    n2.visited=true;
    
    while(n1.parent!=null && n2.parent!=null){
        
        if(n1.parent.visited){
            return n1.parent;
        }
        
        if(n2.parent.visited){
            return n2.parent;
        }
        
        n1=n1.parent;
        n2=n2.parent;
    }
    
    if(n1.parent==null){
        retrun n1;
    }
    if(n2.parent==null){
        return n2; 
    }
}

- Anonymous June 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# - Recursion

private Stack<int> commonManagers = new Stack<int>();

        public int GetClosestCommonManagers()
        {
            return commonManagers.Pop();
        }
        public void ClosestManager(BinaryTree<int> tree, int firstEmp, int secEmp)
        {
            if (tree == null) return;
            if (HasChild(tree, firstEmp) && HasChild(tree, secEmp))
                commonManagers.Push(tree.Node);
            ClosestManager(tree.Right, firstEmp, secEmp);
            ClosestManager(tree.Left, firstEmp, secEmp);
        }

        private bool HasChild(BinaryTree<int> tree, int employee)
        {
            if (tree == null) return false;
            if (tree.Node == employee) return true;
            return HasChild(tree.Left, employee) || HasChild(tree.Right, employee);
        }

- maksymas March 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Import library packages

- Anonymous February 19, 2022 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More