## Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

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

Comment hidden because of low score. Click to expand.
1
of 3 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.``````

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

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.

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
{
System.out.println("Enter tree");
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");

LeastCommonAncestor lca= new LeastCommonAncestor(tree);
int pos= lca.getLCA(a, b);

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

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

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

Especially here

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

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];
}``````

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;
}``````

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

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

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

You weren't supposed to use recursion

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

You need to use iterative solution

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)

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

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

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);
}

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”);
}

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;
}``````

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.

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;
}

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]=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])];
}

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.

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.Queue;

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

public static BinaryTreeNode return_first_common_ancesstor(
BinaryTreeNode parent=null;
return parent;
}

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

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

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){
System.out.println("This tree is empty!");
return ;
}
while(!nodeQueue.isEmpty()){
BinaryTreeNode currentNode=nodeQueue.poll();
if(currentNode.leftchild!=null){
parentmap.put(currentNode.leftchild,currentNode);
}
if(currentNode.rightchild!=null){
parentmap.put(currentNode.rightchild,currentNode);
}
}
}

public static BinaryTreeNode Solution2(BinaryTreeNode head,BinaryTreeNode o1,BinaryTreeNode o2){
return null;
}
if(o1==o2){
return o1;
}
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){
return false;
}
return true;
}
if((lefthas)||(righthas)){
return true;
}
else{
return false;
}
}

// main function for test
public static void main(String[] args) {

BinaryTreeNode results = return_first_common_ancesstor(
System.out.println(results.value);

}

}

Comment hidden because of low score. Click to expand.
-1
of 3 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;
}``````

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

ITERATIVELY !!

Comment hidden because of low score. Click to expand.
-1
of 5 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;
}
}
}``````

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

i think this is wrong.

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

which word of iterative is not clear to u all

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

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

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

DFS

Comment hidden because of low score. Click to expand.
-1
of 1 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;
}

Comment hidden because of low score. Click to expand.
-1
of 1 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;
}

Comment hidden because of low score. Click to expand.
-1
of 1 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.

Comment hidden because of low score. Click to expand.
-1
of 1 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.

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

Its a binary tree not BST.

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.

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

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

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

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

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;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 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;
}``````

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.