Microsoft Interview Question for Software Engineer / Developers






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

May be we can find the LCA (will take log n for BST) then do a preorder traversal till we find the two numbers.

- insigniya February 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

void printBST(Struct node* node, int k1, int k2)
{
    if(node==NULL) return;
    if(node->data<=k2 && node->data>=k1)
    {   
       printf("%d", node->data);
    }
    else if(node->data<k1)  printBST(node->left, k1, k2);
    else if(node->data>k2)  printBST(node->right, k1, k2);
}

The logic here is that, we print the node's data if it is in the range. Else, if the node's data is lesser than the first key value, we call the print function recursively in the left subtree, else if it is greater than the second key value, we call it recursively on the right subtree.

- qwerty March 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

almost correct...couple of mistakes though.
1) there should be no else ifs but ifs..because we have to recurse even if the current node falls in range.
2) the operators in the last two if conditions should be reversed...e.g we have to recurse in left subtree if current node value is > k1.

- v March 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the above code we are doing kind of pre-order traversal, shouldn't it be in-order traversal?

- Abhishek July 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

void printNodes(node *ptr,int low,int high)
{
    if(ptr==NULL) return;
    if(ptr->data<low) printNodes(ptr->right,low,high);

    else if(ptr->data>=low && ptr->data<=high)
    {
        printNodes(ptr->left,low,high);
        printf("%d ",ptr->data);
        printNodes(ptr->right,low,high);
    }
    else printNodes(ptr->right,low,high);
}

- abhijith March 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node{
int vaule;
Node left;
Node right;
}

public print(Node root,int val1,int val2){
print(Node root,int val1,int val2,false);
}

private boolean(Node root,int val1,int val2,boolean oneNodeFound){
if(null==root)
return false;
if(root.value==val1||root.value=val2)
{ oneNodeFound?return true:oneNodeFound=true;
 
}
boolean anotherNodeFound=print(root.left,val1,val2,oneNodeFound)||print(root.left,val1,val2,oneNodeFound);
if(anotherNodeFound && oneNodeFound)
system.out.println(root.value);

return anotherNodeFound;

}

- Sourabh February 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node{
int vaule;
Node left;
Node right;
}

public print(Node root,int val1,int val2){
print(Node root,int val1,int val2,false);
}

private boolean print(Node root,int val1,int val2,boolean oneNodeFound){
if(null==root)
return false;
if(root.value==val1||root.value=val2)
{ oneNodeFound?return true:oneNodeFound=true;
 
}
boolean anotherNodeFound=print(root.left,val1,val2,oneNodeFound)||print(root.left,val1,val2,oneNodeFound);
if(anotherNodeFound && oneNodeFound)
system.out.println(root.value);

return anotherNodeFound;

}

- Sourabh February 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse from root and find common ancestor of small and big. (That node will be in between small and big). To find this, if we assume a number line, the value at the current node can be smaller than both, or in between or greater than both. Choose the right move "move left" or "current node" or "move right" to find the ancestor node.

Now traverse on the left subtree with the knowledge that maximum on a left subtree will be less than current value. Also minimum on the right subtree will be greater than current value.

Will this approach work?

- anno February 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It wont work

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

I think this can be achieved in time complexity of O(logN + r), where n size of BST and r is the range size of values.

Suppose we would like to print the values in ranges VAL1 to VAL2. (Range r = VAL2-VAL1)

1. Reach to node with value VAL1 in BST, which takes O(logN) time.
2. Print this node value and do In Order Traversal of its right child, comparing for the upper bound value VAL2 each time we print. Then print its parent and then In Order Traversal of parents right child, if at any moment upper bound value is met, terminate the traversal.. It will take O(r) time.

So, in total it will take a time complexity of O(logN + r).

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

@Anon: this may not work in all cases. It works only if VAL1 is the child of the root. Take the case where VAL1 is the least element in the tree - [left most child node from root] and VAL2 is the largest element in the tree and the tree has a height = n, where n>2.
1) your step 1 locates the left most child of the tree, say x
2) your step 2 will yield say alpha elements [x's right subtree].
3) your next step is printing x's parent, say px.
4) your next step is printing px's right subtree say beta elements.

What you are missing is parent of px and its right subtree, and its parent and its right subtree etc till the root, because all of them are values between the least and the highest and all of them should be printed.

- Swami June 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does this work?

Array<Node> paths; 
Node root, start, end;

function searchNode(Node node){
	
	if (node.Value greater than end.Value) then 
		return;
	
	if(node.Left is not null) then 
		searchNode(node.Left);
	end if
	
	if(node.Value greater than start.Value AND node.Value less than end.Value) then
		paths.push(node);
	
	if(node.Right != null) then
		searchNode(node.Right)
	end if
}

searchNode(root);

- binrengoog March 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Three conditions:
check root value is in between the range,
if(root->value>k1 && root->value<k2)
{
do in order traversal
While doing Inorder traversal check each nodes values between K1 and K2 and when it reaches value thats greater than K2 stop.
}
if(root->value<k1)
{go to right sub tree
do inorder traversal for just right sub tree and While doing Inorder traversal check each nodes values between K1 and K2 and when it reaches value thats greater than K2 stop.
}
if(root->value>k2)
{
go to left sub tree
do inorder traversal for just left sub tree and While doing Inorder traversal check each nodes values between K1 and K2 and when it reaches value thats greater than K2 stop.
** check if first value in inorder is greater than K2 , if true none of values are present in BST.
}
Worst case Scenario:all values in BST less than k1.

- pirate March 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

print elements in a BST between min. and max.

pseudo code

Print(BST root, int min, int max) {
  insert(root, min);
  while(min->successor < max) {
    print("%d", min->successor);
    min = min->successor;
  }
}

In the code above, min->successor means the successor of the node whose key is equal to min.
The code below is to find the successor of the current node "nd"

node *findMin(node *nd) {
    while (nd->left) {
       nd = nd->left;
    }
    return nd;
}
node *successor(node *nd) {
    if (nd->right) {
        return findMin(nd->right);
    }
    node *y = nd->parent;
    while (y && y->right == nd) {
       nd = y;
       y = y->parent;
    }
    return y;
}

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

simple algorithm

1.get node of val1 in BST
2.In while loop,get its successor until successor==val2

complexity of getting successor is O(ln n).
so overall complexity is O(n ln n)

- rishi t October 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printBSTInRange(BinaryTreeNode* root, int low, int high)
{
if(!root)
return;

if(root->mValue < low)
printBSTInRange(root->mpRight, low, high);
else if(root->mValue > high)
printBSTInRange(root->mpLeft, low, high);
else{
printBSTInRange(root->mpLeft, low, root->mValue);
std::cout << root->mValue << " ";
printBSTInRange(root->mpRight, root->mValue, high);
}
}

- Anonymous May 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printBSTInRange(BinaryTreeNode* root, int low, int high)
{
if(!root)
return;

if(root->mValue < low)
printBSTInRange(root->mpRight, low, high);
else if(root->mValue > high)
printBSTInRange(root->mpLeft, low, high);
else{
printBSTInRange(root->mpLeft, low, root->mValue);
std::cout << root->mValue << " ";
printBSTInRange(root->mpRight, root->mValue, high);
}
}

- Anonymous May 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void printBSTRange(int low, int high, Node root){

	if (root.value() <= low || root.value() >= high){
		print(root.value());
	}
	
	if (root.getLeft().value() > low){
		printBSTRange(low, high, root.getLeft());
	}
	
	
	if (root.getRight().getValue() < high){
		printBSTRange(low, high, root.getRight());
	}
}

- Kade October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

hello kade,how did you deal with null cases..i mean when the node becomes null

- yashwanthduvvuru05 March 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just do an In-order traversal and this gives you the sorted values. If the current node has the value >= than val1 and <= val2, print it (suppose val1 < val2).

- S February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It gives sorted values, but that doesnt help. Check yourself with an example.

- pachunuri January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It gives sorted values, but that doesnt help. Check yourself with an example.

- pachunuri January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

bit dot ly/eJZ34F

- jboss March 11, 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