Microsoft Interview Question for SDE1s


Country: United States
Interview Type: In-Person




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

Is it possible to get the solution this way ?
Get the path from root to node a and b. (Use 2 stacks)
And start popping the node out until you find a common node.

- Anonymous May 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, this solution should work in O(N), and can be done using a single stack.
do a pre-order of the first node, and Push every node in the stack.
Now take the second node, do the same Pre-order traversal, and this time visiting every node do a POP from the stack if the Popped value doesn't match with the current node value then the last Pop value was the lowest common ancestor.

- ABC May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose if node a is parent of node b, what should be the output?

- Anonymous May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

node a

- Anonymous May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can't be done in O(n) without extra space.
Down voting can't change the facts

- EK MACHCHAR May 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Algo:
At any node, check if either of its children or both of its children has return true (got keys)
i) if both elements are found, then this current node is common ancestor. return current node
ii) if either of children has return true and this current node is another key then return this current node
iii) if either of children has return true & this current node is not another key, return NULL but update found pointer with true.

Function is called :
found = 0;
tree* node = commonAncestor (root, &found, f, s)

tree *commonAncestor (tree *root, int *found, int f, int s)
{
        if (!root)
                return NULL;

        if (root->key == f && root->key == s)
        {
                *found = 1;
                return root;
        }

        if (root->key == f || root->key == s)
        {
                *found = 1;
        }

        int left = 0;
        int right = 0;

        tree *ret = common (root->left, &left, f, s);
        if (ret != NULL)
                return ret;

        ret = common (root->right, &right, f, s);
        if (ret != NULL)
                return ret;

        if (left == 1 && right == 1)
        {
                *found = 1;
                return root;
        }

        else if (left == 1 || right == 1)
        {
                if (*found == 1)
                        return root;
                *found = 1;
                return NULL;
        }
        return NULL;
}

- SK June 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

time complexity will be O(n) as in worst case we will have to visit all nodes of the tree.
Space complexity will be O(log n) which is required for recursion.

- SK June 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it only a Binary Tree or a Binary Search Tree(BST) ?

- Novice June 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Least common Ancestor Tested this code

struct BinaryTreeNode *LCA(struct BinaryTreeNode *root,struct BinaryTreeNode  *a,struct BinaryTreeNode *b) { 
struct BinaryTreeNode *left,*right;
if (root == NULL) return NULL;
if(root == a || root == b) return root;
left = LCA(root->left,a,b)
right = LCA(root->right,a,b)
if(left && right)
  return root;
else
  return (left? left:right)
}

- pirate May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this code, if node a or node b doesn't exist, it returns the node that exists.

- Anonymous May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

It looks like the last line should be return null instead of return (left? left:right)

- recursion July 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@anonymous: if node a or node b doesn't exist
if (root == NULL) return root;
it returns NULL after travelling the entire tree...

- pirate July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

static int findLowestCommonAncestor(final TreeNode node, int first, int second){
		if((node.getValue() < first) == (node.getValue() < second)){
			return findLowestCommonAncestor(node.getValue() < first ? node.getRight() : node.getLeft(), first, second);
		} else if(node.getValue() == first || node.getValue() == second){
			return node.getValue() == first ? first : second;
		} else
			return node.getValue();
	}

- emalaj23 May 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Its not BST just Binary tree

- pirate May 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

In a binary tree, there is no way to avoid O(n^2)

- EK MACHCHAR May 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This problem can ben solved in O(N), and using a single stack.
do a pre-order of the first node, and Push every node in the stack.
Now take the second node, do the same Pre-order traversal, and this time visiting every node do a POP from the stack if the Popped value doesn't match with the current node value then the last Pop value was the lowest common ancestor.
Note: we need another variable to hold the last matched node.

- Anonymous May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

bool findLCA(Node* node, int minC, int valA, int valB)
{
  if(!node) return MAXINT;

  minC = min(node->val, minC);

  bool bFoundL = findLCA(node->left, minC, valA, valB);
  bool bFoundR = findLCA(node->right, minC, valA, valB);
  if(bFoundL && bFoundR)
  {
    printf("Lowest Common Ancestor is: %d", minC);
    return false;
  }

  return bFoundL || bFoundR || node->val == valA || node->val == valB;
}

// call like this
findLCA(root, MAXINT, value1, value2);

- Shaibujan Kamalamma May 10, 2013 | 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