## Microsoft Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

``````private static BinaryTreeNode LCA(BinaryTreeNode root,
BinaryTreeNode alpha, BinaryTreeNode beta) {
BinaryTreeNode left,right;

if(root==null)
return root;

if(root.getData()==alpha.getData() || root .getData()==beta.getData())
return root;

left=LCA(root.getLeft(),alpha,beta);
right=LCA(root.getRight(),alpha,beta);

if(left!=null && right!=null)
return root;
else
return left!=null?left:right;

}``````

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

I guess the tree is not BST, because if it is, the problem becomes finding the first node in BST which is in the middle of two nodes, this is O(log N).

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

I guess the question is to find the first common ancestor.

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

This can be done in O(n), the same question I hv done in Amz .

Algo here.
1> Trace the path of node one from the root to child and store all the values in an array1. O(n).
2> Trance the path of node two from the root to child and store all the values in array 2. O (n).

Now U gotto check Index by Index in array 1 and array 2. Just before first index that mismatched is the common ancestor.

Total Time is . O(n)+O(n)+ O(n) = 3*O(n) ~O(n)..
Remember assuming the tree is completely unordered we requires O(n) coz we are assuming its flat out. else if we hv any pattern we can utilize the same..

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

Actually i have also done in microsoft on site interview last week.

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

Was that the same Approach ?? If not what your complexity ?

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

same approach. what's about you amz interview? did you get the offer ?

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

This is not an optimized solution you are using extra memory . There has been no constraint mentioned in the question but this solution can be optimized of course.
Here is an approach
public TreeNode LCAHelp(TreeNode root, TreeNode a, TreeNode b)
{
bool checka = false;
bool checkb = false;
if(!checka && !checkb)
Node LCA = LCAHelp(root,a,b,ref checka, ref check b);
}
if (checka || checkb)
{
Node validated = LCAHelp(root,a,b,ref checka, ref check b);
}

if (checka && checkb)
return LCA;
else
return null;
public TreeNode LCAHelp(TreeNode root, TreeNode a, TreeNode b, ref bool checka, ref bool checkb)
{
if(root == null){
return null;
}
if(root == a && checka= false){
return root;
}

if(root == b && checkb= false){
return root;
}
TreeNode leftSide = LCAHelp(root.left, a, b);
TreeNode rightSide = LCAHelp(root.right, a, b);
if(leftSide!=null && rightSide!=null){
return root;
}
return leftSide==null?rightSide:leftSide;
}
}

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

@hprem991.this solution is only valid if u hv the parent node pointer present.otherwise difficult to trace the path.

Comment hidden because of low score. Click to expand.
1
of 3 vote

if we have access to the parent of each node .. we can go up in the tree and then see where the 2 arrays of parents intersect. Instead of an array we will use hashmaps to store the parents. O(n) complexity

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

Thats not an option.. Coz the question clearly says it binary Tree.. So we DON'T have any extra pointer

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

I concur ancestor for given two nodes can be found in lg(n) for a binary tree.

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

@Anonymous can you explain how to get it in (logn)

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

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

struct Node *Ancestor(struct Node *node,struct Node *p,struct Node *q)
{
if(!node)
return NULL;
if(node==p || node==q)
return node;
struct Node *left=Ancestor(node->left,p,q);
struct Node *right=Ancestor(node->right,p,q);
if(left && right)
return node;
return(left?left:right);
}

Comment hidden because of low score. Click to expand.
1
of 3 vote

Class Solution{
public TreeNode LCA(TreeNode root, TreeNode a, TreeNode b){
if(root == null){
return null;
}
if(root == a || root == b){
return root;
}
TreeNode leftSide = LCA(root.left, a, b);
TreeNode rightSide = LCA(root.right, a, b);
if(leftSide!=null && rightSide!=null){
return root;
}
return leftSide==null?rightSide:leftSide;
}
}

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

This fails if one of the node is not present in the Binary Tree

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

Find out whether the two nodes are in the left of root, right of root or one in left and other in right.

If (on left)------ call the same function for (root->l)
if(on right)----- call the same function for (root->r)
if(on different)--return root.

This will take O(n).

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

Why would this be O(n)? because i see that this will repeatedly traverse nodes down the same path over and over until you diverge?

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

This is not O(N)...

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

Class Solution{
public TreeNode LCA(TreeNode root, TreeNode a, TreeNode b){
if(root == null){
return null;
}
if(root == a || root == b){
return root;
}
TreeNode leftSide = LCA(root.left, a, b);
TreeNode rightSide = LCA(root.right, a, b);
if(leftSide!=null && rightSide!=null){
return root;
}
return leftSide==null?rightSide:leftSide;
}
}

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

I think it is a classic problem in career cup.
The solution is: (assumption is we have the parent pointer)
1. keep move up both nodes by using parent pointer, and keep 2 counters.
after both of them reach the root. Then we have the two counters that
stores the steps which the node need to move to root.
2. By this we can get the difference between two counters. then move up the
larger-counter node only with the different steps. Finally, move both nodes
step by step, when they meet, that is the common ancestor.

Any problem with this method? or the time complexity is bad?

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

I think it is possible to solve the problem with O(lgn) with extra memory and parent pointer. Here is the solution

``````TNode *LCA(TNode *u, TNode *v)
{
stack <TNode *> us, vs;
TNode *tmp_u= u, *tmp_v=v, *tmp_lca=NULL;
while (tmp_u->getParent()!=NULL)
{
us.push(tmp_u->getParent());
tmp_u=tmp_u->getParent();
}

while (tmp_v->getParent()!=NULL)
{
vs.push(tmp_v->getParent());
tmp_v=tmp_v->getParent();
}

while((us.empty()!=true) && ((vs.empty()!=true)) && (us.top()==vs.top()))
{
tmp_lca=us.top();
us.pop();
vs.pop();
}

return tmp_lca;
}``````

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

Following is a solution in O(n) running time.
1. If Node A is a parent of Node B, return Node A regardless if Node B exists, and visa-versa.
3. Else, do LCS.

Disclaimer: this is rather tricky to do in an in-person interview without a debugger ;o)

``````static Node findLCA(final Node root, final Node nodeA, final Node nodeB,final SearchResult searchResult)
{

/**
* base case
*/

boolean foundA=false,foundB=false;

if(root==null || nodeA==null || nodeB==null)return null;
else if(nodeA==nodeB)return nodeA;

if(searchResult.node!=null && searchResult.foundA && searchResult.foundB)
{
return searchResult.node;
}

else if(root.equals(nodeA) || root.equals(nodeB))
{

return root;
}

if(root.left!=null)
{
Node foundNode = findLCA(root.left,nodeA,nodeB,searchResult);

if(searchResult.node!=null && searchResult.foundA && searchResult.foundB)return searchResult.node;

else if(foundNode!=null)
{
foundA=foundA||foundNode.equals(nodeA);
foundB=foundB||foundNode.equals(nodeB);

}

if(foundA && foundB)
{

searchResult.node=root;
searchResult.foundA=true;
searchResult.foundB=true;
return root;
}

}

if(root.right!=null)
{
Node foundNode = findLCA(root.right,nodeA,nodeB,searchResult);
if(searchResult.node!=null && searchResult.foundA && searchResult.foundB)return searchResult.node;

else if(foundNode!=null)
{
foundA=foundA||foundNode.equals(nodeA);
foundB=foundB||foundNode.equals(nodeB);

}

if(foundA && foundB)
{
searchResult.node=root;
searchResult.foundA=true;
searchResult.foundB=true;
return root;
}
}

if(foundA)
return nodeA;
else if(foundB)
return nodeB;
else
return null;
}

static class SearchResult
{
Node node;
boolean foundA,foundB;
}

static class Node implements Comparable<Node>{
Node left;
Node right;
Integer value;

public int compareTo(Node o) {

return value.compareTo(o.value);
}

public boolean equals(Object o){
Node target = (Node)o;
return this.compareTo(target)==0;
}

public String toString()
{
return "Node("+value+")";
}
}``````

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

Stupid method:

``````public TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
if(covers(root.left,p) && covers(root,q)){
return commonAncestor(root.left, p , q);
}
if(covers(root.right, p) && covers(root.right, q)){
return commonAncestor(root.right, p , q);
}
return root;
}

public boolean covers(TreeNode root, TreeNode n){
if(root == null){
return null;
}
if(root == n){
return true;
}
return covers(root.left,n) || covers(root.right,n);
}``````

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

smart method(O(n)):

``````static int NO_NODES_FOUND = 0;
static int ONE_NODES_FOUND = 1;
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 == p || root.right == q)){
return root;
}
int nodesFromLeft = covers(root.left,p,q);
if(nodesFromLeft == TWO_NODES_FOUND){
if(root.left == p || root.left == q){
return root.left;
}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.right;
}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;
}

}``````

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

Bear in mind: the question didn't ask for the *closest* common ancestor. Just: an ancestor.

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

if you are sure that the numbers(data) exists in tree, then the following algorithm works in short time.

``````int common_ancestor2(node *n,int n1,int n2)
{
node *t=n;
while(t!=NULL)
{
if(t->data >n1 && t->data >n2)
t=t->left;
else if (t->data <n1 && t->data <n2)
t=t->right;
else
return t->data;

}

return -1;

}``````

With Some modification, we can continue further till elements found. By the time elements found, we are already found the common ancestor.

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

Modified version is here, which returns common ancestor only when the two elements exists in the tree.

``````// Logic is if both moves left, continue
// If both moves right continue
// If one moves left and the other moves right then thats the Ancestor.
// NO Additional space is required.
int common_ancestor3(node *t,int n1,int n2)
{
node *l,*r;
while(t!=NULL)
{
if(t->data >n1 && t->data >n2)
t=t->left;
else if (t->data <n1 && t->data <n2)
t=t->right;
else
break;
}

// We are at junction, then find out existence of elements
r=l=t;
while(l!=NULL)
{
if(n1>l->data)
l=l->right;
else if ( n1 < l->data)
l=l->left;
else
break;
}

while(r!=NULL)
{
if(n2>r->data)
r=r->right;
else if ( n2 < r->data)
r=r->left;
else
break;
}

// There is no point in returning the found ancestor - Dont be fool
if ( l == NULL || r== NULL )
return -1;

return t->data;
}``````

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

``````struct node * getLCABT(struct node *root,int a,int b)
{
struct node *l;
struct node *r;
if(!root)return NULL;
if(root->data == a || root->data==b)
{
return root;
}

l = getLCABT(root->lc,a,b);
r = getLCABT(root->rc,a,b);

if(l!=NULL && r!=NULL)return root;
else if(l!=NULL){

return l;
//return getLCABT(root->lc,a,b);
}
else{
return r;

//getLCABT(root->rc,a,b);
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Is that LCA and BST ?

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

It shouldn't be BST, otherwise the time should be O(logn)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

If the tree is BST, we may use Breath-first search approach.

Here is JavaScript solution:

``````find: function(node, value1, value2) {
var queue = [node];

var index = 0;

var found1 = false;
var found2 = false;

var ancestorIndex;

while (index < queue.length) {
node = queue[index];

if (!found1 && node.value === value1) {
found1 = true;

if (typeof ancestorIndex == 'undefined') {
ancestorIndex = index - 1;
}
}
else if (!found2 && node.value === value2) {
found2 = true;

if (typeof ancestorIndex == 'undefined') {
ancestorIndex = index - 1;
}
}

if (found1 && found2) {
return queue[ancestorIndex].value;
}

if (node.left) {
queue.push(node.left);
}

if (node.right) {
queue.push(node.right);
}

++index;
}

return null;
}``````

Let's have tree with these values:
5, 3, 1, 0 , 2, 4

Ancestor of 1, 2 -> 3
Ancestor of 3, 4 -> 5

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.

### 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.