Microsoft Interview Question for Software Engineer / Developers






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

is the node typical sturcuture with left and right? or some other representation?

- king_k July 09, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If LCA(root->left,nd1,nd2)!=NULL, then dont try LCS(root->right,nd1,nd2)

- s.c.harish August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes, typical binary tree - each node has a left and right node pointer, as well as a pointer to it's parent.

Anonymous - you cannot take as a parameter the root.

My solution (after being told that I cannot store each parent in a hash table was to raise the lower of the 2 nodes to the level of the other node, and traverse up the tree until r->parent == l->parent)

- anon July 09, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

another one:-
Node * LCA(Node *t , Node *n1,Node * n2)
{
if (!t) return NULL ;

if ((n1->val < t->val)) && (n2->val < t->val))
return LCA(t->left,n1,n2);

if ((n1->val > t->val)) && (n2->val > t->val))
return LCA(t->right,n1,n2);

if ( (n1->val <= t->val)) && (n2->val >= t->val))
return t;
}

- contact.jbhalla July 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

is this right ? i am not sure .. since it seems its doing compares, it seems the question clearly states that its not a BST and its a normal binary tree.

- what August 01, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

is this right ? i am not sure .. since it seems its doing compares, it seems the question clearly states that its not a BST and its a normal binary tree.

I hate this captcha, they are keeping the images so complex that it takes 5-6 tires to get it right .. please remove this .. its more of a pain than useful.

- what August 01, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will work only for BST

- Anonymous August 01, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will work only for BST

- Anonymous August 01, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Remember - you only have node1 and node2 at the start. Each node contains a reference to the parent, so you can get the root by traversing to the root, but you start out with only node1 and node2.

- anon July 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* LCA(node* nd1, node* nd2){

node* cur1 = nd1;
node* cur2 = nd2;

// calculate nd1 height
int nd1_height = 0;
while(cur1->parent!=NULL){
nd1_height++;
cur1 = cur1->parent;
}

// calculate nd2 height
int nd2_height = 0;
while(cur2->parent!=NULL){
nd2_height++;
cur2 = cur2->parent;
}

int diff = nd1_height - nd2_height;

cur1 = nd1;
cur2 = nd2;

if(diff>0){
while(diff--){
cur1 = cur1->parent;
}
} else{
diff = -diff;
while(diff--){
cur2 = cur2->parent;
}
}

while(1){
if(cur1==NULL || cur2==NULL) break;
if(cur1 == cur2)
return cur1;
cur1 = cur1->parent;
cur2 = cur2->parent;
}

return NULL;
}

- Anonymous1 July 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a very good algorithm - to figure out the depths and then 2 pointers. Runtime is O(h) - h is the tree height

- acoader November 04, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good Algo..it should work fine

- NewGuy October 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This should work thanks for sharing, my only question is do we always have a parent pointer in our node object in a non-BST. What if the interviewer put a limitation that you are not allowed to have a parent pointer? how would we go about it?

- SHAD November 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

while calculating the height of node1 and node2...we can check if the other node comes on the way to the root...if yes then return that immediatley...

- king_k July 12, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this case, 'node2' is a parent of 'node1', so returning it would not be correct - because 'node2' cannot be a parent of itself.

- anon July 13, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Google tarjan's offline LCA algorithm

- tb July 12, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

People really misguide and confuse. The question clearly states its not a BST, but lot of people have given solution assuming its a BST. Its easy to do in a BST.

- toobad July 26, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

also i see another solution that talks about parent pointer. Does a normal binary tree have parent pointer ? no is the clear answer.

So the solution should be for a Binary Tree (not BST) , (of course that can be unbalanced, and incomplete)), which means there is only a left and right pointer. No parent or up, no rule that left should be less than parent and right greater than parent. - so a simple binary tree.

Somehow people have byhearted solutions and they dump that in interviews and they get selected.

- toobad July 26, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

toobad,

let us consider the worst case of the nodes not having the pointers to its parents, the tree is unbalanced and incomplete . And, ofcourse, it is not a BST..do you have any solution my your mind..this would definitely increase the complexity of the problem...I am working on it...If I get a solution, I would definitely post it here.

- anonymous August 12, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

toobad,

let us consider the worst case of the nodes not having the pointers to its parents, the tree is unbalanced and incomplete . And, ofcourse, it is not a BST..do you have any solution in your mind..this would definitely increase the complexity of the problem...I am working on it...If I get a solution, I would definitely post it here.

(a typo in my previous comment)

- anonymous August 12, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what anonymous said is true,but I was not able to come up with a solution for a binary tree. So the following program is assuming a BST and the program is to find the common nodes of the two nodes given.


/*Given 2 nodes in a binary tree (not a binary search tree), find the first common parent node.
You are not allowed to store any nodes in a data structure.*/

#include <stdio.h>
#include <stdlib.h>

struct NODE{
int data;
struct NODE* left;
struct NODE* right;
};

typedef struct NODE* node;

node constructBST(node root,int data){
node cur,mytemp;

if(!root){
node temp;
temp=(node)malloc(sizeof(struct NODE));
temp->data=data;
temp->left=NULL;
temp->right=NULL;
root=temp;
return root;
}

cur=root;
while(cur->data>data){
if(cur->left)
cur=cur->left;
else
break;
}

while(cur->data<=data){
if(cur->right)
cur=cur->right;
else
break;
}

if(data<cur->data){
mytemp=(node)malloc(
sizeof(struct NODE));
mytemp->data=data;
mytemp->left=NULL;
mytemp->right=NULL;
cur->left=mytemp;
}

if(data>cur->data){
mytemp=(node)malloc(
sizeof(struct NODE));
mytemp->data=data;
mytemp->left=NULL;
mytemp->right=NULL;
cur->right=mytemp;
}

return root;
}

int deapth(node root, node node1){
node cur;
int len=0;

if(!root){
printf("\nEmpty list");
return(0);
}
cur=root;
while(node1->data<=cur->data){
if(cur->left){
cur=cur->left;
len++;
}
else
break;
}

while(node1->data>cur->data){
if(cur->right){
cur=cur->right;
len++;
}
else break;
}
return len;
}

node findCommonParent(node root,node node1,node node2){
int data1,data2;
node larger,smaller;
node cur;
cur=root;

if(!cur){
printf("\nEmpty List");
return NULL;
}

data1=node1->data;
data2=node2->data;
if(data1>data2){
larger=node1;
smaller=node2;
}
else{
larger=node2;
smaller=node1;
}

while(cur->data > larger->data){
if(cur->left)
cur=cur->left;
else
break;
}

while(cur->data <= smaller->data){
if(cur->right)
cur=cur->right;
else
break;
}

//printf("\n The common parent is %d ",cur->data);
return cur;
}

int main()
{
int i=0;
node root,commonParent,node1,node2;
commonParent=NULL;
root=NULL;
node1=(node)malloc(sizeof(struct NODE));
node2=(node)malloc(sizeof(struct NODE));
node1->data=1;
node2->data=3;
i=5;
root=constructBST(root,i);
i=2;
root=constructBST(root,i);
i=3;
root=constructBST(root,i);
i=1;
root=constructBST(root,i);
i=9;
root=constructBST(root,i);
i=7;
root=constructBST(root,i);
i=11;
root=constructBST(root,i);
commonParent=findCommonParent(root,node1,node2);
printf("\n The common parent is %d \n",commonParent->data);
return 0;
}

- violinlakshmi August 15, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this code does not have comments, so its hard to figure out what it does. Also, seems like its constructing a BST, which is not part of the question... It would be great if the author explained what is being done..

- acoader November 03, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since we are not allowed to store the nodes in a DS, the first thing that comes to my mind is the traversals. We can find the common root from two traversals.

Construct the preorder and inorder traversals. The common root is the one which has the follg two properties:
a) Should be present in between the two nodes in the inorder traversal
b) If there is more than one in a), then the common root is the one which occurs the left-most in the pre-order traversal.

We need not store the nodes per se in the DS but just their values from the traversals in say a array/vector...I believe thats allowed...

- nanmaga October 31, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just realized, the method using traversals doesn't work in all cases. Say, if the tree has only left children...then all traversals gives us the same sequence and its not possible to find the common node...So, I guess the only way is through the RMQ method...using DP...

- nanmaga November 05, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this- travel along the path from one of the 2 nodes to the root, and check each time if the other node occurs in the other subtree, i.e., if current node is left child, check the right child subtree or vice-versa.

Let the nodes be (a,b)

findLca( Node *a, Node *b )
{
bool found = false;
Node *p = findParentOf( a );

//try finding b in the tree rooted at p->left
if ( findNodeIn( b, p->left ) ) {
return p;
}
Node *otherSubTree = p->right;

// the other node has to be in otherSubTree
// or a subtree of an ancestor of p, unless
// the other node is p itself, in which case
// return its parent
while ( 1 ) {
if ( findNodeIn( b, otherSubTree ) ) {
return p;
}

// Here we know LCA is either p or
// in a subtree of p's ancestor
Node *newP = findParentOf( p );
if ( !newP || p == b ) {
return newP;
}
if ( p == newP->left ) {
otherSubTree = newP->right;
}
else {
otherSubTree = newP->left;
}
p = newP;
}
}

- acoader November 04, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why do people get carried away and give all kind of weirdo answers! and half of the page long codes dont make any sense without description. Please avoid doing that.

Coming to the problem. We know that root is not given and it is not a BST. But one thing is that it has pointer to the parent.

*This problem is similar to finding the intersection of two linked lists*.
Now use the same logic of finding the intersection of two linked lists here and find it. you would get it.

- Devil170 February 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Devil170,

This requires you to have parent pointers. What if we are not given that, you cant store them as they violate the constraint:"no additional DS"

- peace November 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

LCA(*node A, *node B){
  *node t1 = A;
  *node t2 = B;

  while (t1 != t2){    
    if (t2->parent == null)
       if (t1-> parent == null)
          return NoCommonParent
       else
          t1 = t1->parent;
    else
       t2=t2->parent;
  }
  return t1;

}

- SK April 23, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* LCA(node* root, int a, int b)
{
if (!root || root->data == a || root->data == b)
return NULL;

node* lcaNode = NULL;
int tmp = findLCA(root, a, b, &lcaNode);
return lcaNode;
}

int findLCA(node* root, int a, int b, node** lcaNode)
{
if (!root)
return 0;
int l = findLCA(root->left, a, b, lcaNode);
int r = findLCA(root->right, a, b, lcaNode);

if (l + r == 2)
{
if (*lcaNode == NULL)
{
*lcaNode = root;
}
return 2;
}
else
{
return l + r + ((root->data == a) || (root->data == b) ? 1 : 0);
}
}

- Kiran August 06, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This looks like the best algorithm.
1. no parent pointer
2. not BST
3. No storage overhead
4. complexity O(n)

- ly March 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Properties:
1. Binary tree. not necessarily BST.
2. No parent node;

---code---

class Ancestor{
	static Node leftNode,rightNode;
	static String leftCode,rightCode;
	static private void inorderTraversal(Node n, String code){
	  if(n==leftNode)
		leftCode=code;
	  
	  if(n==rightNode)
		rightCode=code;
	 
	  if(n.left!=null)
		inorderTraversal(n.left,code + "0");

	  if(n.right!=null)
		inorderTraversal(n.right,code + "1");
	   
	}

	static public Node findCommonAncestor(Node root, Node left, Node right){
	  leftNode=left; rightNode=right;
	  inorderTraversal(root,""); //empty string
	  Nodeparent=root;
	  for(int i=0;i<leftCode.length&&i<rightCode.length;i++)
	  {
		 if(leftCode.charAt(i)!=rightCode.charAt(i))
		   break;
		 else{
		   if(leftCode.charAt(i)=='0')
			   parent = parent. left;
		   else
			   parent = parent. right;
		 }
	  }
	  if(i==leftCode.size()||i==rightCode.size())
		 return null;
	  else
		 return parent;
	}
}

- RahulParundekar March 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is same as finding common node in Y linked list. Parent pointers correspond to next pointer in this case.

- ashishkaila@hotmail.com November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
Career Cup book suggests the following solution: {{{ 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); } with this solutions,some nodes are touched once and some multiple times.Can anyone please help me in finding the complexity of this? - amitverma.info April 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int commonparent(struct node *node,struct node *one,struct node *two,int*cparent)
{
int i,j;
if(node==NULL)
return 0;
i=commonparent(node->left,one,two,cparent);
j=commonparent(node->right,one,two,cparent);
if(node==one || node==two)
return 1;
if(i & j)
{
*cparent=node->data;
}
if(node==one)
return *cparent;
return(i | j);
}

- satish May 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if we have the parent link of each node, it's easy. the code is as following:
private treenode findCommonAncestor(treenode n1, treenode n2){
if(n1.parent.data == n2.parent.data)
return n1.parent;

return null;

}
But the pre-condition is that we don't have link to parent and the tree is not BST.

- emma July 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class TreeNode
{

public TreeNode Right;
public TreeNode Left;
public TreeNode Parent;
public int key;
}

static TreeNode FindNode(TreeNode root, int key)
{
TreeNode RetNode = null;

if (root == null)
{
return null;
}

if (root.key == key)
{
return root;
}



RetNode = FindNode(root.Left, key);
if (RetNode == null)
{
RetNode = FindNode(root.Right, key);
}

return RetNode;

}


static TreeNode FindCommonParent(TreeNode root, int nodeKey1, int nodeKey2)
{
if (root == null) return null;
if (root.key == nodeKey1) return FindNode(root, nodeKey1);
if (root.key == nodeKey2) return FindNode(root, nodeKey2);

int hieght1 = 0;
int hieght2 = 0;

TreeNode node1 = FindNode(root, nodeKey1);
TreeNode node2 = FindNode(root, nodeKey2);

if (node1 == null || node2 == null) return null;

TreeNode Cur1 = node1;
TreeNode Cur2 = node2;

while (Cur1.Parent != null)
{
hieght1++;
Cur1 = Cur1.Parent;
}

while (Cur2.Parent != null)
{
hieght2++;
Cur2 = Cur2.Parent;
}

Cur1 = node1;
Cur2 = node2;

if (hieght1 > hieght2)
{
int diff = hieght1 - hieght2;

while (diff-- != 0)
{
Cur1 = Cur1.Parent;
}

}
else if (hieght1 < hieght2)
{
int diff = hieght2 - hieght1;

while (diff-- != 0)
{
Cur2 = Cur2.Parent;
}
}


while(Cur1.Parent != null && Cur2.Parent != null)
{
if (Cur1.Parent == Cur2.Parent)
{
return Cur1.Parent;
}

Cur1 = Cur1.Parent;
Cur2 = Cur2.Parent;
}

return Cur1.Parent;
}
}

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

BinaryTree LCA(BinaryTree a, BinaryTree b, BinaryTree root)
{
 if (root == null)
  return root;
 if (root.left == a || root.right == b)
  return root;
  
 left = LCA(a, b, root.left);
 right = LCA(a, b, root.right);
  
 if (left && right)
  return root;
 else
  return (left? left : right);
}

- Nits January 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool NodeInTree(TreeNode* root, TreeNode* given)
{
    if (!root || !given)
        return false;

    if (root == given)
        return true;

    bool found = (root->left ? NodeInTree(root->left, given) : false);
    return found ? true : (root->right ? NodeInTree(root->right, given) : false);
}

TreeNode* FirstCommonAncestor_Rec_Core
    (TreeNode* root, TreeNode* given1, TreeNode* given2)
{
    if (!root)
        return NULL;

    if (root->left == given1 && root->left == given2 ||
        root->right == given2 && root->right == given2)
        return root;

    if (NodeInTree(root->left, given1) && NodeInTree(root->right, given2) ||
        NodeInTree(root->left, given2) && NodeInTree(root->right, given1))
        return root;

    TreeNode* fca = FirstCommonAncestor_Rec_Core(root->left, given1, given2);
    return fca ? fca : FirstCommonAncestor_Rec_Core(root->right, given1, given2);
}

TreeNode* FirstCommonAncestor_Rec
    (TreeNode* root, TreeNode* given1, TreeNode* given2)
{
    if (!root || !given1 || !given2 ||
        root == given1 || root == given2)
        return NULL;

    if (!NodeInTree(root, given1) ||
        !NodeInTree(root, given2))
        return NULL;

    // This following is covered in Core
    // if (given1 == given2)

    return FirstCommonAncestor_Rec_Core(root, given1, given2);
}

- Peter August 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node commonPappa(Node root, Node n1, Node n2) {
	if(root == null) {
		return null;
	}
	char noexist = '';
	char n1Pos = (isExists(root.left,n1)?'l': ((isExists(root.right,n1)?'r':noexist);
	char n2Pos = (isExists(root.left,n2)?'l': ((isExists(root.right,n2)?'r':noexist);
	if(n1Pos == noexist || n2Pos == noexist) {
		return null;
	}

	if(n1Pos != n2Pos) {
		return root;
	}
	else if(n1Pos == 'r') {
		return commonPappa(root.right,n1,n2);
	}
	else {
		return commonPappa(root.left,n1,n2);
	}
}

boolean isExists(Node root, Node n) {
	boolean flag;
	if(root == n) {
		return true;
	}
	if(isExist(root.left,n) {
		return true;
	}
	else {
		return isExist(root.right,n);
	}
}

- Sagar Jhobalia September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

node* LCA(node* root, node* nd1, node* nd2){

if(root==NULL)
return NULL;

if(root->left==nd1 || root->right==nd1 || root->left==nd2 || root->right==nd2)
return root;

node* lc = LCA(root->left,nd1,nd2);
node* rc = LCA(root->right,nd1,nd2);

if(lc!=NULL && rc!=NULL)
return root;

if(lc==NULL) return rc;
else return lc;
}

- Anonymous July 09, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sorry it should have been ...

node* LCA(node* nd, node* nd1, node* nd2){

if(nd==NULL)
return NULL;

if(nd->left==nd1 || nd->right==nd1 || nd->left==nd2 || nd->right==nd2)
return nd;

node* lc = LCA(nd->left,nd1,nd2);
node* rc = LCA(nd->right,nd1,nd2);

if(lc!=NULL && rc!=NULL)
return nd;

if(lc==NULL) return rc;
else return lc;
}


and call
node* parent = LCA(root, nd1, nd2);

- Anonymous July 09, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not correct. Suppose you want to find the LCA of the root and another node. Can your program return the right answer?

- Anonymous August 06, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes it would return to null.... root isnt ancestor of itself

- Anonymous October 01, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is not correct, assume that it stops at the root node. root->l == d1, but you might not find d2 in the right subtree of root.

"if(nd->left==nd1 || nd->right==nd1 || nd->left==nd2 || nd->right==nd2) return nd;"


search(node* root, node* d1, node* d2) {
node1 = searchR(root->l, d1, d2);
node2 = searchR(root->r, d1, d2);
if (node1 && node2) { pirnt root;}
}

node* searchR(node* root, node* d1, node* d2) {
if (root == 0) {return 0;}
if (root == d1 || root == d2) return root;
node1 = searchR(root->l, d1, d2);
node2 = searchR(root->r, d1, d2);
if ( node1 && node2) {print root; return root;}
else if (node1 != 0) {return node1;}
else {return node2;}
}

- ppp October 06, 2008 | Flag


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