Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
just a little optimization
public static TNode FCA(TNode root, int a, int b){
if(root == null) return null;
if(root.value == a || root.value == b) return root;
if(!exist(root,a) || !exist(root,b)) return null;
return FCA_helper(root,a,b);
}
public static TNode FCA_helper(TNode root,int a , int b){
if(root == null) return null;
boolean is_a_on_left = exist(root.left,a);
boolean is_b_on_left = exist(root.left,b);
if(is_a_on_left != is_b_on_left){
return root;
}else{
if(is_a_on_left) // or is_b_on_left
{
return FCA(root.left,a,b);
}else{
return FCA(root.right,a,b);
}
}
}
public static boolean exist(TNode root, int value){
if(root == null){
return false;
}else{
if(root.value == value){
return true;
}else{
return exist(root.left,value) || exist(root.right,value);
}
}
}
If we know depth of both nodes:
Then if we are allowed to use an additional data structure, we can solve this in O(logn)
-Find the node with the smaller depth, store it and all its parents in a linked list. Like - (node1,node1.parent,node1.parent.parent....root), which can easily be done using recursion in O(logn).
Then store the same for the other node in another linked list. Find the node with the greater depth lets say n1, and find the difference of their depths lets say d. Then skip d nodes from linkedlist of n1 and then we will reach the depth of the second node we have to find. Compare the two values from the linkedlist, if same, then return that as first ancestor, otherwise iterate through both linkedlists by increasing both counters by 1 and find first match. The running time for this would be O(logn) + O(logn) + O(logn) which is O(logn). Space complexity is also O(logn).
Now if we don't know the depth, then we make the linkedlist for both the nodes, and compare each nodes of the linkedlist starting with the first node, and this will take O(logn)^2, which is still smaller than O(n) unless n is small.
This problem can also be solved using recursion if we are not allowed to use another data structure, in logn time.
boolean found1, found2 = false;
current=root;
firstancestor=null;
ancestor(current, node1, node2) {
ancestor(current.left, node1, node2);
ancestor(current.right, node1, node2);
if (firstancestor==null)
if (found1 && found2)
firstancestor = current;
return;
}
This will reach the bottom of the tree and work from there, and the first node that contains both the nodes in its subtree will be the firstancestor.
However, then this would solve the problem in (logn) as it will be going through all the nodes.
Please let me know if there are any errors in my reasoning or code, as I did it quite fast.
Thanks..
We use one recursive function to bubble up the common ancestor if found, and whether the sub tree has either of the two nodes. When we're at an ancestor for which the left sub tree has one of the nodes, and the right sub tree also has one, then we've found the first common ancestor.
Node* first_common_ancestor(Node* a, Node* b, Node* curr, bool& has_node) {
if (curr == a || curr == b) { has_node = true; return NULL; }
bool has_left = false;
bool has_right = false;
if (curr->left) {
Node* fca = first_common_ancestor(a, b, curr->left, has_node);
if (fca) return fca;
has_left = has_node;
}
if (curr->right) {
Node* fca = first_common_ancestor(a, b, curr->right, has_node);
if (fca) return fca;
has_right = has_node;
}
has_node = has_right || has_left;
if (has_left && has_right) return curr;
else return NULL;
}
Lowest Common ancestor can be reduced to RMQ problem...because it is an interview problem, I dont think they require your coding implementation. Give each node a number from 0 - n in a BFS way. Then just use an Euler tour to construct the array and scan through the corresponding number to find the smallest. That's the easiest way
FIrst get the depths. Call them d1 and d2. Suppose d1<d2. From the node with d2, go towards the parent d2-d1 steps. From that point on go up from both 1 step at a time until you find a common node.
memo:
Your solution assumes that each node has a reference to its parent. What about the case where each node only knows its children!!
here is what can be,
Step1 find all root nodes that take you to first finding node
Stack st = Method(n,f1,new Stack());
bool isFound = false;
//once you have all root nodes, back track
while(st is not empty || !isSecondFound)
{
find(st.pop(),f2,st.peek()) // peek and pop to traverse from peek till pop, initially pop to be null
}
Method(Node n, Node f1,Stack st)
{
if(n==null || isFound) return;
if(n==f1) isFound = true; return;
st.push(n)
method(n.left);method(n.right);
st.pop(n);
return st;
}
//
find(Node prevNode,Node findNode,Node currentNode)
{
//use inorder traversing and exclude prevnode and all branches from it
}
I have given the logic, but they wanted complete working code.
Logic:
* For both node find all ancestors up to root. (ancestor = node's parent or parent's parent)
* Add ancestors in a 2 separate queues then find the first common node from both queue.
* OR we can add into 2 separate stacks and start popping nodes from both stack until we get different nodes.The last common node will be the answer.
public static boolean findK(BSTNode root,int k){
if(root.val==k) return true;
else {
return ( (root.left!=null?findK(root.left,k):false) || (root.right!=null?findK(root.right,k):false));
}
}
----------------------
public static BSTNode LCA(BSTNode root, int a,int b)
{
if(a==root.val||b==root.val){
return root;
}
else{
if(findK(root.left, a)){
if(findK(root.right,b)){
return root;
}
else{
return LCA(root.left,a,b);
}
}
else{
if(findK(root.left,b)){
return root;
}
else{
return LCA(root.right,a,b);
}
}
}
}
first function findK() finds whether a node is present in subtree with given root.
and second function LCA() finds the Least common ancestor
how about this......
public Tree commonAncestor(Tree root, Tree p, Tree q)
{
if (covers(root.left, p) && covers(root.left, q))
return commonAncestor(root.left, p, q);
if (covers(root.right, p) && covers(root.right, q))
return commonAncestor(root.right, p, q);
return root;
}
private boolean covers(Tree root, Tree p)
{ /* is p a child of root? */
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}
int getHeight(Node p) {
int height = 0;
while (p) {
height++;
p = p->parent;
}
return height;
}
Node Ancestor(Node p, Node q) {
int h1 = getHeight(p);
int h2 = getHeight(q);
if (h1 > h2) {
swap(h1, h2);
}
for (int h = 0; h < |h2-h1|; h++)
q = q->parent;
while (p && q) {
if (p == q) return p;
p = p->parent;
q = q->parent;
}
return null;
}
public static int NO_NODES_FOUND = 0;
public static int ONE_NODES_FOUND = 1;
public static int TWO_NODES_FOUND = 2;
public int covers(TreeNode root,TreeNode p, TreeNode q){
int ret = NO_NODES_FOUND;
if(root == null){
return ret;
}
if(root == p || root == q){
ret += 1;
}
ret += covers(root.left,p,q);
if(ret == TWO_NODES_FOUND){
return ret;
}
return ret+=covers(root.right,p,q);
}
public TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
if( p == q && (root.left == q || root.right == p)){
return root;
}
int nodesFromLeft = covers(root.left,p,q);
if(nodesFromLeft == TWO_NODES_FOUND){
if(root.left == p || root.left == q){
return root;
}else{
return commonAncestor(root.left,p,q);
}
}else if(nodesFromLeft == ONE_NODES_FOUND){
if(root == p){
return p;
}else if(root == q){
return q;
}
}
int nodesFromRight = covers(root.right,p,q);
if(nodesFromRight == TWO_NODES_FOUND){
if(root.right == p || root.right == q){
return root;
}else{
return commonAncestor(root.right,p,q);
}
}else if(nodesFromRight == ONE_NODES_FOUND){
if(root == p){
return p;
}else if(root == q){
return q;
}
}
if(nodesFromLeft == ONE_NODES_FOUND && nodesFromRight == ONE_NODES_FOUND){
return root;
}else{
return null;
}
}
Firstly, the question is to find the first common factor not the least common factor. I've used a simple recursive approach:
Given p and q nodes.
Check If p.parent == q.parent
- if yes, return p
- if no, traverse p and q upwards. (i.e p.parent, q.parent), until we find a equal nodes.
public static Node<int> CheckCommonAncestor(Node<int> p, Node<int> q)
{
if (p.Parent == q.Parent)
{
if (p.Parent == null)
return p;
else
return p.Parent;
}
else
{
if (p.Parent != null && q.Parent != null)
{
return CheckCommonAncestor(p.Parent, q.Parent);
}
else if (p.Parent == null)
{
return CheckCommonAncestor(p, q.Parent);
}
else if (q.Parent == null)
{
return CheckCommonAncestor(p.Parent, q);
}
}
return null;
}
Here is an implementation in C#. Note that since it is not a BST, worst case running time is O(n).
- berkaypamir November 04, 2012public static TNode LeastCommonAncestor(TNode root, TNode first, TNode second) { if (root == null) return null; if (root == first || root == second) return root; TNode left = LeastCommonAncestor(root.left, first, second); TNode right = LeastCommonAncestor(root.right, first, second); if (left != null && right != null) return root; if (left != null) return left; if (right != null) return right; return null; }