is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
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.
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.
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.
Finding LCA for two nodes is totally different from finding LCA for two values. Later is much easier.
- miz March 07, 2012Algorithm for finding LCA for two values:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). if you find a node with value in between n1 and n2 then n is the LCA
Basically just do BSF the compare the value (n2<A.value<n1)
BST implementation is much straightforward, if it is other type of tree for example not sorted multiple child nodes we have to take some assumptions. The algorithm would be very different. So context is first thing we should clear up.
Assume it is a BST,
Node findLCA(Node root, int v1, int v2){
Queue queue = new Queue();
Queue.enque(root);
While(queue.size()>0)
{
Node current = queue.deque();
If(v2<current.value<v1)
Return current;
If(current.left!=null)
Queue.enque(current.left);
If(current.right!=null)
Queue.enque(current.right);
}
}
Finding LCA for two nodes, it does not matter if it is BST or not.
Do a bottom up traversal and record the full path from searched node to root, assume we do not have circular references . use LinkedList to record full path so we keep the insertion order, then result would be the first elements of intersection of two paths .
Node findLCA(Node node, Node n1, Node n2)
{
LinkedList pathNode1 = new LinkedList();
LinkedList pathNode2 = new LinkedList();
findFullPathForNode(root, n1, pathNode1);
findFullPathForNode(root, n2, pathNode2);
//keep the same node;
pathNode1.retainAll(pathNode2);
if(pathNode1.size()>0)
return pathNode1.first();
}
findFullPathForNode(Node current, Node n1, LinkedList path){
if(current==null)
return;
path.add(current);
//find the target node
if(current == n1){
return;
}
findFullPathForNode(current.left, n1, path);
findFullPathForNode(current.right, n1, path);
}