Microsoft Interview Question
Software Engineer / Developersyeah well i didnt get the job :(, i was interviewing for New College grad position in Tools and Server Division with Windows Workflow Foundation team of .Net Framework.
bool Search (Node *root, int key)
{
while (root != NULL)
{
if (root-> no == key) {return true;}
else if (root->no > key) {root = root->right;}
else {root = root->left; }
}
return false;
}
Node * LowestCommonAncestor(Node *root, int a, int b)
{
if (root == NULL) {return ; }
if (a < root-> no && b > root->no )
{
if ( Search(root->left, a) && Search(root->right, b) )
{
return root;
}
else
{
return NULL;
}
}
else if ( a < root-> no && b < root-> no)
{
return LowestCommonAncestor(root->left, a, b);
}
else if ( a > root-> no && b > root-> no)
{
return LowestCommonAncestor(root->right, a, b);
}
else
{
return NULL;
}
}
one clarification:
one check is missing:
OLD :
if (a < root-> no && b > root->no )
SUGGESTED:
if ((a < root-> no && b > root->no ) ||
(a > root-> no && b < root->no ))
{
SAME CODE
}
else-part is SAME as written by you
I took a while to reach to ans as this was binary tree , the solution i had given there was
1) get preoder and inorder
2) take first element in prorder and search it into inorder all the element to left of it is left subtree and on right are right subtree
3)find the index of node1 and node2 in inorder , if one appears on the left of root and other on the right then return root as ans
4) if both appear on left side , discard all the elements right to root , same with if they appear on the right of root
5) increament index in preorder
6) continue this recursively
node * LCA(node *n1,node *n2,node * root) {
if (!root || !n1 || !n2) return null;
if ((n1->val <= root->val) && (n2->val > root->val)) return root;
else if (n1->val > root->val) return LCA(n1,n2,root->right);
else if (n2->val < root->val) return LCA(n1,n2,root->left);
}
Above code is for BST and with assumption that :
n1->val < n2->val
n1 and n2 are present in the BST
typedef struct node{
int val;
struct node *left;
struct node *right;
} tNode;
tNode * ClosestCommonAnscestor( tNode *root, tNode *key1, tNode *key2)
{
if( root == NULL )
{
return NULL;
}
else if( root == key1 || root == key2 )
{
return root;
}
else
{
tNode *l= NULL, *r = NULL ;
l = ClosestCommonAnscestor( root->left, Key1, key2 );
r = ClosestCommonAnscestor( root->right, Key1, key2 );
if( (l != NULL) && (r != NULL) )
{
return root;
}
else
{
return l ? l : r;
}
}
}
If you find any mistakes in my code please let me know.
your space complexity is not O(1), because it implicitly use stack (recursive call), so it is O(log(n))
hey sachin, i have an interview with Server and Tools as well. could you please tell me some of the other questions you were asked? I would really appreciate your assistance.
Best,
DK
You must have done well to get to the Director. I assume he was the last person in the loop.
- Anonymous December 08, 2010