Microsoft Interview Question Software Engineer / Developers


Country: India
Interview Type: In-Person


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

do inoder traversal iteratively, and store the values in array A
say array A contains  values (5,9,u,6,11,v,22,10)
and u and v are the nodes for which we have to find LCA.
now only thing remains is to check for every node between u and v, 
(we can use devide and conquer in nodes between u and v)
the node from which we can reach both u and v is LCA.

- ankit manit on August 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the worst case n-steps in-order traversal gives you (u,5,9,6,11,22,10,v) and then you should check n-2 nodes using devide and conquer method.
My thoughts are there is no need to do in-order traversal at first. Just start devide and conquer immidiately.

- Aleksey.M on December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class LeastCommonAncestor {
    
    private int[] tree;
    
    public LeastCommonAncestor(int[] tree)
    {
        this.tree= new int[tree.length+1];
        System.arraycopy(tree,0, this.tree, 1, tree.length);
    }
    
    public int getLCA(int a, int b)
    {
        int apos=-1, bpos=-1;
        
        for(int i=0; (apos==-1||bpos==-1) && i<tree.length; i++)
        {
            apos= tree[i]==a?i:apos;
            bpos= tree[i]==b?i:bpos;
        }
        
        if(apos*bpos<0)
            return -1;
        
        while(apos!=bpos)
        {
            if(apos>bpos)
                apos/=2;
            else bpos/=2;
        }
        
        return apos;
    }
    
    public static void main(String args[]) throws FileNotFoundException, IOException            
    {
        BufferedReader br= new BufferedReader(new InputStreamReader( new FileInputStream(new File("C:\\LCA.txt"))));
        System.out.println("Enter tree");
        String[] treestring= br.readLine().split(" ");
        int[] tree= new int[treestring.length];
        
        for(int i=0; i<treestring.length; i++)
        {
            tree[i]= treestring[i].equals("NULL")?-1:Integer.parseInt(treestring[i]);
        }
        System.out.println("Enter A and B");
        int a= Integer.parseInt(br.readLine());
        int b= Integer.parseInt(br.readLine());
        
        LeastCommonAncestor lca= new LeastCommonAncestor(tree);
        int pos= lca.getLCA(a, b);

        System.out.println(lca.tree[pos]);
    }
}

- nj on August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@nj, Can you please explain what exactly is happening inside getLCA ??

Especially here

while(apos!=bpos)
        {
            if(apos>bpos)
                apos/=2;
            else bpos/=2;
        }

- crystal.rishi2 on October 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

LCA(node* root,p,q)
{
        //finding ancestors...
	vector<node*> a,b;
	while(p->parent)
	{
          a.push_back(p->parent);
	  p = p->parent;
     	}
        while(q->parent)
	{
          b.push_back(q->parent);
	  q = q->parent;
     	}
	vector<node*> &c,&d;
        if(a.size() > b.size())
	{
	  a.erase(a.size()-b.size());
	}
	else
	{
	  b.erase(b.size()-a.size());
	}
        
        //binary search for first equal elements...
        int u = 0;
        int v = a.size();
	while(u<v)
        {
	    int mid = (u+v)/2;
            if(a[mid] == b[mid])
            v = mid;
            else
            u = mid;
	}
        return a[u];
}

- ash.rokks on August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

DFS

NodeType* findLCA(NodeType* root, NodeType* e1, NodeType* e2)
{
    if(root == NULL) return NULL;
    if(root == e1 || root == e2) return root;
    NodeType* lRet = findLCA(root->l, e1, e2);
    NodeType* rRet = findLCA(root->r, e1, e2);
    if(lRet && rRet) return root;
    if(!lRet) return rRet;
    return lRet;
}

- wangxuyang on September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great! Only one case is not handled here: what if one or even both elemnts are not in the tree?

- Aleksey.M on December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You weren't supposed to use recursion

- Anonymous on January 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You need to use iterative solution

- hashiqi on January 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

It seems that we could use post-order traversal of the binary tree to solve the problem. A c++ solution could be like below:

Node *find_lowest_common_ancestor(N ode * root, Node *node1, Node *node2, int &flag) {
  if (node1 == node2) {
    return node1;
  }
  if (root == NULL) {
    flag = 0;
    return NULL;
  }
  else if (root == node1) {
    flag = 1;
    return NULL;
  }
  else if (root == node2) {
    flag = 2;
    return NULL;
  } 
  int flag1, flag2;
  Node *retNode1 = find_lowest_common_ancestor(root->left, flag1);
  if (retNode1 != NULL) {
    return retNode1;
  } 
  Node *retNode2 = find_lowest_common_ancestor(root->right, flag2);
  if (retNode2 != NULL) {
    return retNode2;
  }
  if (flag1 == 1 && flag2 == 2 || flag1 == 2 && flag2 == 1) {
    return root;
  }
  flag = flag1 + flag2;
  return NULL;
}

- Jeff on August 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ITERATIVELY !!

- anon on August 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

You have a Binary Tree and Two node p , q.
You have to find the first common parent of p and q.

tree_node_type *LowestCommonAncestor(
tree_node_type *root , tree_node_type *p , tree_node_type *q)
{
	tree_node_type *l , *r , *temp;
	if(root==NULL)
	{
		return NULL;
	}

	if(root->left==p || root->left==q || root->right ==p || root->right ==q)
	{
		return root;
	}
	else
	{
		l=LowestCommonAncestor(root->left , p , q);
		r=LowestCommonAncestor(root->right , p, q);

		if(l!=NULL && r!=NULL)
		{
			return root;
		}
		else
		{
			temp = (l!=NULL)?l:r;
			return temp;
		}
	}
}

- Saikat Sarkar on August 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think this is wrong.

- Anonymous on August 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

which word of iterative is not clear to u all

- why_so_serious on August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the iterative part.... God i love the answers u get on here some times

- akamel001 on August 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

Which part of the word "iterative" is not clear ...........

- Anonymous on August 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS

- nsdxnsk on August 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Initialise a And b to Zero In Main Program

Com_Anc(struct Node *root, struct Node *p, struct Node *q, int &a, int &b){
struct Node *temp ;
if(root){
if(! (*a) && root == p)
*a = 1;

if(! (*b) && root == q)
*b = 1;

if(!(a&&b)){
if(root->l)
temp = Com_Anc(root->l, p, q, a, b);
if(root->r)
temp = Com_Anc(root->r, p, q, a, b);
}

if(a&&b) return root;
else return NULL;
}
return NULL;
}

- Abhijeet Rokade on August 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Initialise a And b to Zero In Main Program

Com_Anc(struct Node *root, struct Node *p, struct Node *q, int &a, int &b){
struct Node *temp ;
if(root){
if(! (*a) && root == p)
*a = 1;

if(! (*b) && root == q)
*b = 1;

if(!(a&&b)){
if(root->l)
temp = Com_Anc(root->l, p, q, a, b);
if(root->r && !(a&&b))
temp = Com_Anc(root->r, p, q, a, b);
}

if(a&&b) return root;
else return temp;
}
return NULL;
}

- Abhijeet Rokade on August 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are two approaches that could work here:
1) Starting from the root node, recursively determine whether the children belong to the same branch or different branche. If same, then you walk along that branch, if different, the root is your Lowest common ancestor.
2) Find a list of all the parents from the root to each child. And then iterate through them from the top level to bottom level, you result lies in the one before when it becomes unequal to each other.

- Anonymous on August 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Convert the tree into list where
left child->2n
right child->2n+i
while traversing and converting to a list, note the indexes of the list where the data of the nodes are saved say IndexX and IndexY.

then all you have to do is match IndexX/2 and IndexY/2 by using left shift operator.
and your job is done in O(n)
with an efficiency with worst case: n+log(n)

- shantanu.msp on August 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Convert the tree into list where
left child->2n
right child->2n+i
while traversing and converting to a list, note the indexes of the list where the data of the nodes are saved say IndexX and IndexY. this is done in O(log n) base 2.

then all you have to do is match IndexX/2 and IndexY/2 by using left shift operator which is done in O(log n) base 2.

Total efficiency with worst case: 2log(n) base 2

- shantanu.msp on August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Start with the root compare both nodes data with root if one is smaller and other is larger than root then root is answer. 2.else move the left or right branch where the data lies and repeat step 1 and so on.

- Ankur garg on August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its a binary tree not BST.

- Anonymous on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int LCA(struct treenode* root,int a,int b)
{
if(root==NULL)
return 0;

if(((root->data < a) && (root->data >b))|| ((root->data > a) && (root->data <b)) ||(root->data == a) || (root->data ==b))
return root->data;
if((root->data < a) && (root->data <b))
LCA(root->right,a,b);
if((root->data > a) && (root->data >b))
LCA(root->left,a,b);
}

- Anonymous on August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public TreeNode LowestCommonAncestor(TreeNode a, TreeNode b){
while (a != b && (a != null) && (b != null)){
if (a.depth == b.depth){
a = a.parent;
b = b.parent;
}

if (a.depth > b.depth){
a = a.parent;
}else{
b = b.parent;
}
}

if ( a == b){
return a;
}
throw new RuntimeException(“Two input nodes aren’t in the same binary tree”);
}

- Matthew Zhao on August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node* LCA_itr(Node *root, Node *n1, Node  *n2){
        while(root!=NULL){
                if(root->val==n1->val || root->val==n2->val){
                        return root;
                }
                if((root->val > n1->val && root->val < n2->val) || (root->val < n1->val && root->val > n2->val)){
                        return root;
                }
                if(root->val > n1 && root->val > n2->val){
                        root=root->left;
                }
                if(root->val < n1->val && root->val < n2->val){
                        root=root->right;
                }
        }
        return NULL;
}

- Pratiksha on August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node* LCA_itr(Node *root, Node *n1, Node  *n2){
        while(root!=NULL){
                if(root->val==n1->val || root->val==n2->val){
                        return root;
                }
                if((root->val > n1->val && root->val < n2->val) || (root->val < n1->val && root->val > n2->val)){
                        return root;
                }
                if(root->val > n1 && root->val > n2->val){
                        root=root->left;
                }
                if(root->val < n1->val && root->val < n2->val){
                        root=root->right;
                }
        }
        return NULL;
}

- pratiksha.dake on August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iteratively find pre-order and post-order and in-order sequence of the tree.
now, if u , v are the given tree nodes, LCA of u,v should occur :
1) between u, v in in-order sequence
2) before u, v in pre-order
3) after u, v in post order.
find the common node (unique) following all these rules. this will be the LCA.

- Sudhanshu on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tnode *LCA(Tnode *a,Tnode *b)
{
Tnode *p=a;
while (p!=root)
{
p->flag=a->key;
p=p->father;
}
root->flag=a->key;

*p=b;
while (p->flag!=a->key) p=p->father;

return p;
}

- yhk on August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void LCA_dfs(int u)
{
int tmp=++depth;
b[++bn]=tmp; f[tmp]=u; at[u]=bn;
for (int i=0; i<son[u].size(); i++)
{
int v=son[u][i];
LCA_dfs(v);
b[++bn]=tmp;
}
}

inline void RMQ_init(int n)
{
for (int i=1; i<=n; i++) d[i][0]=b[i];
int m=floor(log(n*1.0)/log(2.0));
for (int j=1; j<=m; j++)
for (int i=1; i<=n-(1<<j)+1; i++)
d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}

inline int RMQ(int l,int r)
{
int k=floor((log(r-l+1)*1.0)/log(2.0));
return min(d[l][k],d[r-(1<<k)+1][k]);
}

inline int LCA(int a,int b)
{
if (at[a]>at[b]) swap(a,b);
return f[RMQ(at[a],at[b])];
}

- huikangyi on August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is the property of the binary tree? If it is like Binary Search Tree i.e. left < root < right, then just iteratively go up from node with lower key until encounter the first ancestor whose key is greater than the other node's key. If it is only normal tree, find the path from each node to the root, then go back and find the early common node of two paths.

If there is only pointers from parent to child nodes, we can use the property of Binary search tree to search from the root and choose to search the left or right subtree.

- David on September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Here is my code, I implement two solutions:


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Problem_7_find_lowest_common_ancessstor {
// I implement two solutions, Solution1() and Solution2()

public static BinaryTreeNode return_first_common_ancesstor(
BinaryTreeNode head,BinaryTreeNode o1,BinaryTreeNode o2){
BinaryTreeNode parent=null;
parent=Solution1(head,o1,o2);
parent=Solution2(head,o1,o2);
return parent;
}

public static BinaryTreeNode Solution1(BinaryTreeNode head,BinaryTreeNode o1,BinaryTreeNode o2){

HashMap<BinaryTreeNode,BinaryTreeNode> parentmap=new HashMap<BinaryTreeNode,BinaryTreeNode>();
Solution1_createParentmap(head,parentmap);

HashMap<BinaryTreeNode,Boolean> o1parent=new HashMap<BinaryTreeNode,Boolean>();
o1parent.put(o1, true);
BinaryTreeNode currentParento1=parentmap.get(o1);
while(currentParento1!=null){
o1parent.put(currentParento1, true);
currentParento1=parentmap.get(currentParento1);
}
BinaryTreeNode currentParento2=o2;
while(currentParento2!=null){
if(o1parent.containsKey(currentParento2)){
return currentParento2;
}
currentParento2=parentmap.get(currentParento2);
}

return null;
}

public static void Solution1_createParentmap(BinaryTreeNode head,HashMap<BinaryTreeNode,BinaryTreeNode> parentmap){
if(head==null){
System.out.println("This tree is empty!");
return ;
}
Queue<BinaryTreeNode> nodeQueue=new LinkedList<BinaryTreeNode>();
nodeQueue.add(head);
parentmap.put(head, null);
while(!nodeQueue.isEmpty()){
BinaryTreeNode currentNode=nodeQueue.poll();
if(currentNode.leftchild!=null){
parentmap.put(currentNode.leftchild,currentNode);
nodeQueue.add(currentNode.leftchild);
}
if(currentNode.rightchild!=null){
parentmap.put(currentNode.rightchild,currentNode);
nodeQueue.add(currentNode.rightchild);
}
}
}



public static BinaryTreeNode Solution2(BinaryTreeNode head,BinaryTreeNode o1,BinaryTreeNode o2){
if((!Solution2_contains_node(head,o1))||(!Solution2_contains_node(head,o2))){
return null;
}
if(o1==o2){
return o1;
}
BinaryTreeNode current=head;
while(Solution2_contains_node(current,o1)&&Solution2_contains_node(current,o2)){

if(Solution2_contains_node(current.leftchild,o1)&&Solution2_contains_node(current.leftchild,o2)){
current=current.leftchild;
continue;
}
if(Solution2_contains_node(current.rightchild,o1)&&Solution2_contains_node(current.rightchild,o2)){
current=current.rightchild;
continue;
}
break;
}

return current;
}
public static boolean Solution2_contains_node(BinaryTreeNode head,BinaryTreeNode node){
if(head==null){
return false;
}
if(head==node){
return true;
}
boolean lefthas=Solution2_contains_node(head.leftchild,node);
boolean righthas=Solution2_contains_node(head.rightchild,node);
if((lefthas)||(righthas)){
return true;
}
else{
return false;
}
}

// main function for test
public static void main(String[] args) {
BinaryTreeNode head=new BinaryTreeNode(16);
head.insertleft(new BinaryTreeNode(12));
head.insertright(new BinaryTreeNode(18));
head.leftchild.insertleft(new BinaryTreeNode(6));
head.leftchild.insertright(new BinaryTreeNode(14));
head.leftchild.rightchild.insertleft(new BinaryTreeNode(13));
head.leftchild.rightchild.insertright(new BinaryTreeNode(15));
head.rightchild.insertleft(new BinaryTreeNode(17));
head.rightchild.insertright(new BinaryTreeNode(24));

BinaryTreeNode results = return_first_common_ancesstor(
head,head.leftchild.rightchild.leftchild,head.rightchild.leftchild);
System.out.println(results.value);



}

}

- Chengyun Zuo on August 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

node* lowestCommonAncestor(node *root, node *n1, node*n2)
{
  if(root==NULL)
    return NULL;
  else if((n1==root) || (n2==root))
    return root;
  node *itr = root;
  while(itr != NULL)
  {
    if(itr->val < n1->val && itr->val <n2->val)
      itr=itr->right;
    else if (itr->val > n1->val && itr->val  > n2->val)
      itr=itr->left;
    else
      return itr;
  }
}

Idea is to find the node where one node value is larger then the other node value.

- Anonymous on August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry wrong description idea is to find a node for which node value is between two given node values.

- Anonymous on August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

would work if it's a binary search tree, in this case it's a binary tree; need not have the key value based arrangement of nodes the way we have in BST

- maverick on August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

tNode* binaryTree::__findComAnsc(tNode * root, tNode * a, tNode * b)
{
    if(root == NULL)
        return NULL;

    if(root == a)
        return root;

    if(root == b)
        return root;

    tNode * n1 = __findComAnsc(root->left, a, b);
    tNode * n2 = __findComAnsc(root->right, a, b);

    if(n1 && n2)
        return root;
    else if(n1 && !n2)
        return n1;
    else if(!n1 && n2)
        return n2;
    else if(n1 == n2)
        return n1;
    else
        return NULL;
}

- Test on August 10, 2012 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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