Microsoft Interview Question for Software Engineer Interns


Country: United States
Interview Type: Written Test




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

Pythonic version

def IsBST(tree):
    if tree == None:
        return True, None, None
       
    left, left_min, left_max = IsBST(tree.left)
    if not left or tree.value < left_max:
        return False, min(left_min, tree.value), max(left_max, tree.value)
    right, right_min, right_max = IsBST(tree.right)
    if not right or tree.value > right_min:
        return False, min(left_min, tree.value), max(tree.value, right_max)
    return True, min(left_min, tree.value), max(right_max, tree.value)
}

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

Wow. I posted this, and it looks ugly!

- Anonymous November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

def IsBST(tree):
    if tree == None:
        return True, None, None
          
    left, left_min, left_max = IsBST(tree.left)
   
    if not left or tree.value < left_max:
        return False, min(left_min, tree.value), max(left_max, tree.value)
   
    right, right_min, right_max = IsBST(tree.right)
   
    if not right or tree.value > right_min:
        return False, min(left_min, tree.value), max(tree.value, right_max)
   
    return True, min(left_min, tree.value), max(right_max, tree.value)

- Anonymous November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Most of the answers are wrong. As @msft pointed out the solutions will return the following BST is valid

5 <- 10 ->15
Left child of 5 is 20. This is not a BST but the solutions would validate this case..

The simplest solution is to perform inorder traversal and check if every node is greater than the previous node. If the inorder traversal is sorted then it is a BST.

- raam December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I got asked this question, after a long time tracking minimums and maximums, the interviewer asked me why couldn't I consider something with in order traversal. Then I felt really stupid.

- sambatyon December 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

int isBST(struct node* node) { 
  return(checkIsBST(node, INT_MIN, INT_MAX)); 
}

int checkIsBST(struct node* node, int min, int max) { 
  if (node==NULL) 
	return true;

  if (node->data<min || node->data>max) 
	return false;

  return 
     ( checkIsBST(node->left, min, node->data) && 
       checkIsBST(node->right, node->data+1, max) ); 
}

- R@M3$H.N December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

One has to make a mistake once in their life to get the small trap in this problem.

If you have not coded this ever, you will most likely come up with (in nervous interview) checking that every left child is less than and ever right child is greater than current node (then recurse to children).

But we have to check that WHOLE left subtree is less than and WHOLE right subtree is greater than.

Basically google you should question and study the pitfalls and the correct inefficient and efficient solutions.

- msft needs to improve hiring methods November 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Basically you should google question*

- msft needs to improve hiring methods November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can't judge hiring methods based on just one question. This might be more of a coding question etc.

Anyways, you are right though.

Microsoft needs to improve, not just in their hiring methods.

- Anonymous November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Still trying to understand what you meant here. If we check
Note: We will check if root/left/right node is not null every time.
1) LeftChild is less than root
2) RightChild is greater than root
3) Apply recursive way for bot left and right subtree(which will be passing leaft and right node again following same pattern)

why it will be incorrect solution? Can you help me here?

- NewUser December 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@NewUser
consider a situation where the root node is 5 - its left child is 3 - right child of the left one is 6.

. 5
. / \
3
./\
6

and your code checks if the right node is greater than its parent which is true in ur case and so you will return true for binary tree integrity

do u get the point?

I guess according to msft we are supposed to start comparing bottom up and not top down

- ko December 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry the tree structure should be

. 5
. / \
. 3
. /. \
. 6

- ko December 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

I didn't test it. hope It works

public static void isValidBST(Node node,int minValue, int maxValue)
{
	if(node == null)
	{
		return true;
	}else
	{	if(node.value < minValue && node.value > maxValue)
		{
			return false;
		}
		return isValidBST(node.left,minValue,node.value) && isValidBST(node.right,node.value,maxValue);
	}

	
}

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

It seams you wanted to write OR instead of AND:

if(node.value < minValue || node.value > maxValue)

- Alex November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

what should be the intial values for minValue & maxValue

- navi November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If the values stored at tree are ints then we can set inital min/maxValues by INT_MIN and INT_MAX values. Else we should add two flags minValueSet, maxValueSet and improve the condition when the false value is returned

- Alex November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for sharing guys.

@Alex: Correct, You got it. I meant using || instead of &&. that's correct. Thx
@Navi: Initial values should be: Integer.MIN_VALUE and Integer.MAX_VALUE ( in case we are dealing with integers.
@Alex, can you elaborate more on your improvement please.

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

C++ version.

#include <iostream>
#include <limits>

template <typename T>
struct bst_node {
	bst_node() : left_(nullptr), right_(nullptr), data_() { }
	bst_node(const T& data) : left_(nullptr), right_(nullptr), data_(data) { }
	~bst_node() { delete left_; delete right_; }
	
	bst_node *left_;
	bst_node *right_;
	T data_;
};

template <typename T>
bool is_valid_bst_r(const bst_node<T>* root, const bst_node<T>*& prev) {
	if (!root)
		return true;
    
	if (!is_valid_bst_r(root->left_, prev))
		return false;
    
	if (prev && root->data_ <= prev->data_)
		return false;
	prev = root;
    
	return is_valid_bst_r(root->right_, prev);
}

template <typename T>
bool is_valid_bst(const bst_node<T>& root) {
    const bst_node<T>* prev = nullptr;
    return is_valid_bst_r(&root, prev);
}

int main() {
	std::cout << std::boolalpha;
	bst_node<int> root(5);
	root.left_ = new bst_node<int>(4);
	root.right_ = new bst_node<int>(6);
	root.left_->left_ = new bst_node<int>(1);
	//root.right_->left_ = new bst_node<int>(3);
	std::cout << is_valid_bst(root) << std::endl;
	return 0;
}

- Diego Giagio November 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if T is a custom type with just a compare function? Don't think std::numeric_limits will work.

If you want to make this generic. Make it truly generic.

One possible way: Write a wrapper around T, which has two boolean flags min and max and the compare function of the wrapper looks at those flags.

- Subbu. November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Diego: How does that even help?

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

1. Check to see if the node is greater than or equal to max value of the left subtree
2. Check to see if the node is less than the minvalue of the right subtree
3. Check to see if the left or right subtrees are invalid
4. if all tests pass, then return true

template <class T>
bool validateBST(BinaryNode<T> *node){
	if(node == NULL){
		return true;
	}

	//If the max value of the left subtree is bigger than the node return false
	//If the min value of the right subtree is smaller than the node return false
	if(node->right != NULL && node->data < maxValue(node->right) ||
		node->left != NULL && node->data >= minValue(node->left))
	{
		return false;
	}

	//check if either of the trees are invalid
	//if any subtree is invalid, return false
	if(!validateBST(node->left) || !validateBST(node->right)){
		return false;
	}

	//we passed all the tests, so its valid :)
	return true;
	
}

//Caller must make sure to not pass a NULL node
template <class T>
int maxValue(BinaryNode<T> *node){

	//Recursively traverse down to the right node
	//When we're at the current node, check if it's right child is null
	//if the right child is null, then that means were the max
	return (node->right == NULL) ? node->data : maxValue(node->right);

}

//Caller must make sure to not pass a NULL node
template <class T>
int minValue(BinaryNode<T> *node){
	//Recursively traverse down to the left node
	//When we're at the current node, check if it's left child is null
	//if the left child is null, then that means the current node is the min
	return (node->left == NULL) ? node->data : minValue(node->left);

}

- Nii Mante December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Basically you should google question*

- msft needs to improve hiring methods November 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why so?

- Srigopal Chitrapu January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int Pre = INT_MIN;
bool IsValidBST(root)
{
	Pre = INT_MIN;
	return IsValidBST(root)
}
bool Verify(TreeNode* root)
{
	if( !root ) return true;
	if( !Verify(root->left) ) return false;
	if( root->data < Pre ) return false;
	Pre = root->data;
	if( !Verify(root->left) ) return false;
	return true;

}

- woxujiazhe November 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What you guys think about this?

boolean isBST(node root)
{
	if(root==null) return true;

	if((root->left  !=null && root->left->data  > root->data) || 
           (root->right !=null && root->right->data < root->data) )
		return false;

	return isBST(root-left) && isBST(root->right);
}

- Anon November 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey, it doesn't work. as it aways return true because of first condition. Look for solution below.

- Mallan November 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Mallan for your input. Below is corrected code. I like your solution, except I don't want to pass additional parameter. Please let me know if you see any issue.

bool isBST(Node root)
{
	if(node==null) return true;

	if(node->left !=null && node->left->data  > node->data) return false;
	if(node->right!=null && node->right->data < node->data) return false;

	if(!isBSTR(root->left) || !isBST(root->right) return false;

	return true;
}

- Anon December 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the tree below, the value of each parent always falls between the values of its children, yet this is not a BST (sorry I couldn't format a tree properly here, even with the braces)

root: 3
left-child: 2
right-child: 4
left-left-grandchild: 1
left-right-grandchild: 5

- Sunny December 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not just push the root node into a stack, say stack A. Then, until A is empty, pop A into some node variable n, validate that n->left is less than n->value and n->right is greater than n->value. If both are true, push n->right then push n->left. Else, return false. If A becomes empty, return true.

- NameGoesHere December 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct Node
{
	int val;
	Node* left;
	Node* right;
};

bool checkIntegrityRec(Node* node, int& prevVal)
{
	if (!node)
		return true;
	if (!checkIntegrityRec(node->left, prevVal))
		return false;
	if (node->val < prevVal)
		return false;
	prevVal = node->val;
	if (!checkIntegrityRec(node->right, prevVal))
		return false;
	return true;
}

bool checkIntegrity(Node* root)
{
	Node* n = root;
	while (n->left)
		n = n->left;
	int prevVal = n->val - 1;
	return checkIntegrityRec(root, prevVal);
}

- Viacheslav December 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do in order traversal and check if the list is sorted.

- Anonymous December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do in order traversal and check if the list is sorted.

- Anonymous December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isValidBST(TreeNode root) {
return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isValidBSTHelper(TreeNode node, int minValue, int maxValue) {
if (node == null) {
return true;
}
if (node.val > minValue && node.val < maxValue) {
return isValidBSTHelper(node.left, minValue, node.val) && isValidBSTHelper(node.right, node.val, maxValue);
} else {
return false;
}
}

- yshanstar1988 December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isValidBST(TreeNode root) {
		return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}

	private boolean isValidBSTHelper(TreeNode node, int minValue, int maxValue) {
		if (node == null) {
			return true;
		}
		if (node.val > minValue && node.val < maxValue) {
			return isValidBSTHelper(node.left, minValue, node.val) && isValidBSTHelper(node.right, node.val, maxValue);
		} else {
			return false;
		}

}

- yshanstar1988 December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isValidBST(TreeNode root) {
	return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isValidBSTHelper(TreeNode node, int minValue, int maxValue) {
	if (node == null) {
		return true;
	}
	if (node.val > minValue && node.val < maxValue) {
		return isValidBSTHelper(node.left, minValue, node.val) && isValidBSTHelper(node.right, node.val, maxValue);
	} else {
		return false;
	}
}

- yshanstar1988 December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we not do a traversal ( say inorder ) and while are visiting the node compare the left and right node values. Do this recursively for all node.

- ElBee December 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Got this question on Outlook Desktop team interview. The extra challenge was that duplicates are allowed and they should be on the left from parent - 5 < 5 > 10 is valid, but 4 < 5 > 5 is not. Here's solution (using inorder traversal)

typedef struct BinaryTree
{
    struct BinaryTree *Left;
    struct BinaryTree *Right;

    int Data;
} BTree, *PBTree;


bool IsBinaryTreeBST(PBTree root, PBTree *prev)
{
    bool fBSTTree = true;

    if (root && prev)
    {
        if (root->Right && root->Right->Data == root->Data)
        {
            fBSTTree = false;
        }

        if (fBSTTree)
        {
            fBSTTree = IsBinaryTreeBST(root->Left, prev);
            if (fBSTTree)
            {
                if (*prev && (*prev)->Data > root->Data)
                {
                    fBSTTree = false;
                }
                *prev = root;

                if (fBSTTree)
                {
                    fBSTTree = IsBinaryTreeBST(root->Right, prev);
                }
            }
        }
    }

    return fBSTTree;
}

- AK October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

void IsBST(Node* current,bool& isBST)
{
if(current == 0 || isBST == false) return;

if(current->Left != NULL && current->Left->Data > current->Data)
{
isBST = false;
return;
}
if(current->Right!= NULL && current->Right->Data < current->Data)
{
isBST = false;
return;
}
IsBST(current->Left,isBST);
IsBST(current->Right,isBST);
}

- Mallan November 30, 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