Microsoft Interview Question for Development Support Engineers






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

while(treenode!=null){
if(treenode.data> node1.data && treenode.data<node2.data){
return treenNode;
}else if(treeNode.data < node1.data && treenode.data > node2.data) {
return treeNode;
}else if(treeNode.data > node1.data && treeNode.data > node2.data){
treeNode= treeNode-> left;
}else if(treeNode.data<node2.data && treeNode.data> node1.data){
treeNode=treeNode->right;
}
}

- GKS June 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

GKS...atleast read the question fully...its binary tree,not BST, search Lowest common ancestor in old posts.

- XYZ June 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
while(node!=null){
if(findNode(node.left,node1)&&findNode(node.right,node2))
return node ;
elseif(findNode(node.left,node1)&&findNode(node.left,node2))
node = node.left ;
elseif(findNode(node.right,node1)&&findNode(node.right,node2))
node = node.right ;
}
}

- zzg June 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool findNode(Node root, Node node){
if(root==null)
reutrn False;
elseif(root==node)
return True;
elseif(findNode(root.left,node)||findNode(root.right,node))
return True;
else
return False
}

- zzg June 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how does this find the least common parent. you are finding the path from the root node.

- Sidharth Kashyap June 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Brute force: use zzg's solution to find the all the parents of the 2 nodes to be searched.

starting from the two nodes, traverse back till you find a common parent.

Root will be the common parent if there is no common ancestor.

- Sidharth Kashyap June 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

first find the length of te path from root to node1 using pointer1...
similarly find for node2 usng pointer2..
subtract both the pathlengths...
and tat gives how many times the pointer2 from te node2 has to be traversed back towards root....
after this both the pointers will b in te same level...
now just find the parent for either of te nodes...........and tis ll give the common ancestor for both the nodes

- vigneshk.cit June 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the same problem as finding the intersection of two linked list.

- IamR June 24, 2010 | 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;
}

- seeker7 June 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cheating! there is no parent in each tree node. you can't make this assumption.

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

imagine this as i can't draw a figure here...this strategy will fail if the two nodes are deep down in different sub-trees of the root node itself.

- Anonymous July 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tree* ClosestAnscestor(int Rdata, int lData, Tree *node)
{
if(node != NULL)
{
if(findnode(node->left, lData) && findnode(node->right, Rdata))
return node;
else
{
ClosestAnscestor(Rdata,lData,node->left);
ClosestAnscestor(Rdata,lData,node->right);
}
}
else
return NULL;
}

bool findnode(Tree *node, int data)
{
if(node != NULL)
{
if(node->data == data)
return true;
else if(data < node->data)
findnode(node->left, data);
else
findnode(node->right, data);
}
else
return false;
}

- DashDash July 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

its not a BST that they have asked for......

- Anonymous September 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

lca using xor

- adi October 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct node *LCA(struct node *R,struct node *c1,struct node *c2)
{
struct node *l,*r;

if(!c1 ||!c2)
return NULL;
if(R->left==c1||R->left==c2||R->right==c1||R->right==c2)
return R;
l=NULL:
r=NULL;
l=LCA(R->left,c1,c2);
r=LCA(R->right,c1,c2);
if(!l && !r)
return NULL;
if(l!=NULL && r!=NULL)
return R;
l=l==NULL?r:l;
return l;
}

- geeks July 19, 2011 | 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