Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

bool FindIfIsBST()
{
     return isbst(root, Integer.MIN, Integer.MAX)
}

bool isbst(node n, int p, int q)
{
     if(n == null)
	return true;
	
     if(n.data > p && n.data < q && isbst(n.left, p, n.data)
	&& isbst(n.right, n.data, q))
		return true;

	return false;
}

- Good Stuff October 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good stuff!

- Anonymous October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is a bug in the code. When comparing n.data with p and q, we should use ">=" and "<=" instead of ">" & "<". Other wise, the BST like below is returned false.

0
  -5  7
-5 0 0 7

- leichongchong October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

Rather simple solution. Do an inorder traversal on the Binary tree. Store the value of the node visited in the prev step and compare. if the current node value is greater than prev node value it is a BST. if the encountered node value is less than the prev value it is not a BST.

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

agree

- anonymous October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this algorithm is good, but needs a global variable to hold the prev node value if using recursion.

- leichongchong October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

This comment has been deleted.

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

LOL!

- Anonymous October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is along the lines unfortunately this is going to crash every time unless your root is null

- Gogo October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what u mean by it crash ???

- coder October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is BS. Completely incorrect.

3
  /   \
 1    4
       /
      2

If the above figure does not come out correct:

root is 3, has two child nodes 1 and 4. 4 has a left child 2.

The above code will tell it is a BST, while it is not.

- Anonymous October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here u go

public static boolean checkBST(node Tree){
		Stack<node> s= new Stack<node>();
		node tree= Tree;
		int prev_val=-999;
		while(true){
		while(tree!=null){
			s.push(tree);
			tree=tree.left;
		}	
			if(!s.isEmpty()){
				tree=s.pop();
				if(tree.data < prev_val) return false;
				else{
				prev_val=tree.data;
				System.out.println(tree.data);
				tree=tree.right;
				}
			}
			else break;
	
		}

		return true;
	}

- coder October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This fails almost immediately. this tree (which is a bst) fails when it compares node 3 to prev_val set to 5:
5
/ \
3 6

- Gogo October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No it will not when it pops out 3 from stack prev_val will be -999 not 5 try running it

- Anonymous October 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Node prev = new Node(null,null,0);
boolean isBST(Node n)
{
if(n == null)
return true;
boolean flag = isBST(n.left);
if(prev.value>n.value)
return false;
prev = n;
System.out.println(n.value);
boolean flag1 =isBST(n.right);
return flag&flag1;
}

- Kannan S January 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

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

LOL!

- Anonymous October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

all we need to check is the root node should be greater than the maximum node in the left subtree and it should be less than minimum node of the right subtree then its a binary search tree....

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

This is the only guy who got it right. For each node 1) Check that left tree has max value less than this node
2)Check that right tree has min value greater than this node.
3)Check that left and right subtrees themselves are BSTs using 1), 2) and leaf check (returns true).
Details of 1) and 2)

For 1) Go to left child and then to it's right child, it's right child (Keep going right until leaf is found) - this is the max.
2) same idea for min on right subtree.

- fizzybuzzer October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I get your point. But in a binary tree, the max/min value could be on any side of the node. So how are you saying that keep going right till you hit the leaf? So basically we need to traverse each element on both sides of the tree to make sure that max on left side is lesser than parent and min on right side is greater than parent and repeat it for each node.

- SN October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@fizzybuzzer: Don't be so blind. Read good stuff's answer. You might learn something.

- Anonymous October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@SN: Perhaps I didn't word it clearly? I didn't understand the beginning of your comment fully either..but if I understand your statement: "So basically we need to traverse each element on both sides of the tree to make sure that max on left side is lesser than parent and min on right side is greater than parent and repeat it for each node." correctly, then I think we're saying the same thing.

@Anonymous: Your tone seems impolite Anonymous, but I believe it could be provoked by my "This is the only guy who got it right" :P. I apologize if that was rude - didn't mean it to be.

Now to good stuff's answer: I think it is mostly correct, but not 100% correct. A BST will certainly be declared as one, but it is possible a non-BST also gets marked as a BST.

I could be wrong myself as I haven't tested this..but here's what I am thinking:
In the non-recursive part the 2 checks are only:
1. The node in question vs left child's value
2. The node in question vs right child's value

This is insufficient since a node should not only be bigger than it's left child, it should be bigger than the entire sub-tree rooted at the left child.

Similar idea for the right child.

I don't think the recursion ever takes care of that.

So basically a tree like this : 9
5 12
4 11

I think when 9 and 5 are compared it will be true and the fact that 11 is hiding under the left tree of 9 will never be caught.

- fizzybuzzer October 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just noticed my example tree got completely Fed. Attempt #2:

------------9-----------
----------/----\---------
---------5----12------
-------/--\--------------
-----4---11-----------

- fizzybuzzer October 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//the inorder array stores inorder traversal and we can check whether they are sorted or not..



int check(NODEPTR root,int in_order[],int n)
{
for(i=0;i<n-1;i++)
{
if(in_order[i]>in_order[i+1])
return -1;
}
return 1;
}

- c7c7 October 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in the above code we don't need pointer to root of BT

- c7c7 October 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//without the inorder traversal...
int find_max(NODEPTR root)
{
//using level order traversal we can find maximum
}//end of find max
int find_min(NODEPTR root)
{
//using level order traversal we can find minimum
}//end of find minimum



int check(NODEPTR root,int*max,int*min)
{
if(root==NULL)
return 1;

if(root->data>find_max(root->left))
{
if(root->data<find_min(root->right))
{
return(check(root->left)&&check(root->right));
}
else
return 0;
}
return 0;
}

CAN ANYONE SUGGEST SOMETHING BETTER SUCH THAT WE DON'T HAVE TO CALCULATE MAX AND MINIMUM FOR A NOE AGAIN AND AGAIN

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

PERHAPS YOU CAN JUST READ GOOD STUFF'S ANSWER?

- Anonymous October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

TC : O(n) , SC : O(n)
Do in-order traversal of tree and store each node value in array.
Again traverse through the array to check a[i] < a[i+1] ...
if true for all .... Yes else No.

- mrn October 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

isBST(node *root,node *prev)
{
isBST(root->left,prev);
if(prev==NULL)
prev->data=root->data;
else
{
if(prev->data > root->data)
{ printf("not bst");
exit;
}
else
prev->data=root->data;
}
isBST(root->right,prev);
}

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

Solution with complexity O(n):

bool isBST(node * ptr, int min, int max)
{
if(ptr == 0)
return TRUE;

if(ptr->val < min || ptr->val > max)
return FALSE;

return (isBST(ptr->left,min,ptr->val -1) == TRUE
&& isBST(ptr->right, ptr->val, max) == TRUE)

}

int main()
{
check = isBST(root, INT_MIN , INT_MAX)
}

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

Collapse the tree in an array by Left-root-Right traversing and check if it is sorted array, if sorted answer is BST otherwise not a BST

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

Yay!

- Anonymous October 09, 2012 | Flag


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