## Microsoft Interview Question for Software Engineer / Developers

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

If we are talking about a binary search tree where the following holds true,

left child value <= parent value < right child value

then, an in-order tree walk would give us a sorted list. If we verify that the list is in non-decreasing order then we are done.

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

what is the exact meaning of wellordered BT??

A tree by itself cant be ordered( plz correct me if i am wrong).The output from the traversals show whether it results in ascending sorted manner or not (i.e inorder traversal of BST). So its the traversal not the tree

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

yeah... well-ordered? what does that mean? do you mean a balanced-tree?

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

Assuming that its a BST. I think the following code should do it :

void RetInfixArray(node* parent, int arr[])
{
static int index = 0;
if(parent == null)
return;
RetInfixArray(node->left);
arr[index++] = node->data;
RetInfixArray(node->right);

}

int IsBalanced(node *root)
{
int* arr;
int length = 0;

if(!root)
return;

//use some method to find the number of nodes of the BT
length = NodesNum(root);

arr = (int *) malloc(sizeof(int) * length);
if(!arr)
return;

RetInfixArray(root, arr);

for(i = 0;i <length-1;i++)
{
if(arr[i]>arr[i+1])
return 0;
}

return 1;
}

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

Well ordered ... mmm...
As long as a BT follows one of Pre, In, Post-Order, it is well ordered.
So one of three traverse ways should generate a monotonic sequence.
Just my guess hehe

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

bool verifyBST(Node* aNode)
{
if((aNode->left) && (aNode->left->value > aNode->value))
return false;
if((aNode->right) && (aNode->right->value < aNode->value))
return false;
verifyBST(aNode->left);
verifyBST(aNode->right);
return true;
}

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

Your idea is good, but there is some minor bug in your code. I modified it.

boolean verifyBST(Node* aNode)
{
if((aNode->left) && (aNode->left->value > aNode->value))
return false;
if((aNode->right) && (aNode->right->value < aNode->value))
return false;

if(!(aNode->left&&aNode->right)) return true;
else {
if(verifyBST(aNode->left) && verifyBST(aNode->right))
return true;
else
return false;
}
}

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

I just found that there is some bug even in the idea. ;-)

for example, the following tree will return true for your code.
5
/ \
3 9
/ \ / \
1 6 4 10

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

I think the problem just want you to check whether this tree is a BST or not.

bool isBSTHelper(BinaryTree *p, int low, int high) {
if (!p) return true;
if (low < p->data && p->data < high)
return isBSTHelper(p->left, low, p->data) &&
isBSTHelper(p->right, p->data, high);
else
return false;
}

bool isBST(BinaryTree *root) {
// INT_MIN and INT_MAX are defined in C++'s <climits> library
return isBSTHelper(root, INT_MIN, INT_MAX);
}

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

looking only at left and right children will not prove that it is well ordered. We need to see the ordering of all the nodes during an inorder traversal.

Here is a code to check for well ordered property.

bool well_ordered(node *root)
{
int largest;
if (!root)
return true;
else
return inorder(root,largest);
}

bool inorder(node *root, int &largest)
{
int left,right;
bool result;

largest = root->data;
if (root->left) {
result = inorder(root->left,left);
if (!result) return false;
if (left > largest) return false;
}
if (root->right) {
result = inorder(root->right,right);
if (!result) return false;
if (largest > right) return false;
else largest = right;
}
return true;
}

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

Good idea, but I doubt your algo can fix the issue brought up by Nirvanatiger.
Let's say in your recursion we are at the *root=5 levle, and look at the right branch. largest=5, and
result=true, and largest(5)<right(10), so it will return true. However, it should return false. The point is:
1. when comparing the left brach, you should assert(currentNode.value>left.largest)
2. when comparing the right brach, assert ((currentNode.value<right.smallest)), note it is the smallest other than largest.
You got the first comparison right, but the 2nd comparison wrong.

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

good tiger

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

To continue with my comment posted to NM on Tuesday September 23, 2008, here is a inefficient algo, I believe the LeftLargest and RightSmallest function can be saved with some reference parameters.
Anyway, I just leave it as is because it looks more straightforward and understandable.
========================================================
//find the largest value in the left brach.
int LeftLargest(Node* root)
{
..if (root->left==NULL)
....return root->value;
..Node* left=root->left;
..while (left->right)
....left=left->right;
..return left->value;
}

//find the smallest value in the right brach.
int RightSmallest(Node* root)
{
..if (root->right==NULL)
....return root->value;
..Node* right=root->right;
..while (right->left)
....right=right->left;
..return right->value;
}

//compare
bool compare(Node* root){
..if ((root->value >= LeftLargest(root))&&
....(root->value <= RightSmallest(root)))
......return true;
..else
....return false;
}

bool postOrder(Node* root)
{
..if (!root)
....return true;
..else if (postOrder(root->left) && postOrder(root->right) && compare(root))
....return true;
..else
......return false;
}

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

well ordered=monotonic inorder?

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

well ordered is when all the leaf nodes are at the same depth or max 1 level apart, isnt it?!?!?!!??!?!?!?!?!

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

I think the following algo will work though written in C#

/// <summary>
///
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public bool IsBST(Node node)
{
if (node == null)
return true;
else
{
if (!IsBSTUtil(node))
return false;
}

return true;
}

/// <summary>
/// /
/// </summary>
/// <param name="node"></param>
/// <param name="data"></param>
/// <returns></returns>
public bool IsBSTUtil(Node node)
{
if (node == null)
return true;
else
{

if (node.Left != null && node.Left.Data > node.Data)
return false;
if (node.Right != null && node.Right.Data <= node.Data)
return false;

if (!IsBSTUtil(node.Left) || !IsBSTUtil(node.Right))
return false;
}

return true;
}

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

// Method to check if binary tree is actually a binary search tree
// Check if the max in the left tree is is less than root node
// Check if the min in the right tree is greater than the root node
// Do this sort of validation for all the nodes.
// Not a better approach as we are calling max and min for each and every
// node
public Integer maxValue(binaryTreeNode b) {
if (b == null)
return 0;
return Math.max(Math.max(maxValue(b.left), maxValue(b.right)), b.value);
}

public Integer minValue(binaryTreeNode b) {
if (b == null)
return Integer.MAX_VALUE;
return Math.min(Math.min(minValue(b.left), minValue(b.right)), b.value);
}

public boolean isBST_1() {
return isBST_1(root);
}

public boolean isBST_1(binaryTreeNode b) {
if (b == null)
return true;
if (b.left != null && b.value <= maxValue(b.left))
return false;
if (b.right != null && b.value >= minValue(b.right))
return false;
return isBST_1(b.left) && isBST_1(b.right);
}

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

// Making sure number of traversals are less
public boolean isBST_2() {
return isBST_2(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

public boolean isBST_2(binaryTreeNode b, int min, int max) {
if (b == null)
return true;
if (b.value >= max || b.value <= min)
return false;
return isBST_2(b.left, min, b.value) && isBST_2(b.right, b.value, max);
}

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

// Making sure number of traversals are less than previous approach
public boolean isBST_2() {
return isBST_2(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

public boolean isBST_2(binaryTreeNode b, int min, int max) {
if (b == null)
return true;
if (b.value >= max || b.value <= min)
return false;
return isBST_2(b.left, min, b.value) && isBST_2(b.right, b.value, max);
}

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

// Making sure number of traversals are less
public boolean isBST_2() {
return isBST_2(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

public boolean isBST_2(binaryTreeNode b, int min, int max) {
if (b == null)
return true;
if (b.value >= max || b.value <= min)
return false;
return isBST_2(b.left, min, b.value) && isBST_2(b.right, b.value, max);
}

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.

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

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