Amazon Interview Question for Developer Program Engineers

Team: Love Film
Country: UK
Interview Type: Phone Interview

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

``````/* check for BST */
private static boolean isBST(BSTNode root) {
if (root == null)
return true;

if (root.getLeft() != null && findMax(root.getLeft()) > root.getData())
return false;
if (root.getRight() != null
&& findMin(root.getRight()) < root.getData())
return false;

if (!(isBST(root.getLeft())) || (!isBST(root.getRight())))
return false;
return true;
}``````

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

``````/* Check for binary tree whether its binary search tree */
private static boolean isBST(BSTNode root, int prev) {
if(root==null)
return true;
if(!isBST(root.getLeft(),prev))
return false;
if(root.getData()<prev)
return false;
prev=root.getData();

return isBST(root.getRight(),prev);
}``````

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

The inorder traversal of the tree should be sorted.

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

``````BOOL IsBST(Node *Root)
{
If(NULL == Root) return TRUE;
int min = findMin(Root);
int max = findMax(Root);
return IsBST(Root, min-1, max+1);
}
BOOL IsBST(Node *Root, int MIN, int MAX)
{
If(NULL == Root) return TRUE;
return ( (Root->info > MIN) &&
(Root->info < MAX) &&
IsBST(Root->Left, MIN, Root->Info+1) &&
IsBST(Root->Right, Root->Info-1, MAX) );
}``````

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

I think this : "
IsBST(Root->Left, MIN, Root->Info+1) &&
IsBST(Root->Right, Root->Info-1, MAX) );"
Should be :

IsBST(Root->Left, MIN, Root->Info) &&
IsBST(Root->Right, Root->Info, MAX) );
Because BST doesn't allow for the nodes to have the same value.

What do you think?

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

Its right.!

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

``````bool isBST(struct node *node)
{
return( isBSTHelper(node, INT_MIN, INT_MAX));
}
bool isBSTHelper(struct node *node, int min, int max)
{
if( node == NULL)
return true;
if( node->data < min || node->data > max )
return false;
return ( isBST(node->left, min, node->data) &&
isBST(node->right, node->data, max));
}``````

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

boolean isBst(Node root){
if (root == null) return true;
else{
bool temp;
if(node->left != null && node->left->value < node->value)
temp = true;
if(node->right != null && node->right->value > node->value)
temp = true;
if(temp)
return isBst(node->left) && isBst(node->right) ;
else
return false;
}
}

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

/**correction**/
boolean isBst(Node root){
if (root == null) return true;
else{
bool temp = true;
if(node->left != null && node->left->value > node->value)
temp = false;
if(node->right != null && node->right->value < node->value)
temp = false;
if(temp)
return isBst(node->left) && isBst(node->right) ;
else
return false;
}
}

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

@anonymous: this is wrong since you are not comparing with the value of ancestor. Checking only with parent is not enough. Eg:
6
4 9
3 7

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

This algorithm does not work because you are not checking whether entire left-sub tree is lesser than the 'node->value' and entire right subtree is greater than the 'node->value'.

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

True, this doesn't work. Thanks for pointing it out.

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

``````bool flag  = true;
int max_encountered = NEGATIVE_INFINITY;
void checkInorder(Node root){
if(root == null) return;
if(!flag){
println("Not a BST");
}
if(  flag && root.left != null)
checkInorder(root.left);
if( flag && root.data > max_encountered){
max_encountered = root.data
}else{
flag = false;
}
if( flag && root.right != null)
checkInorder(root.right);
}``````

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

public Boolean IsBst(Node node) {

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

Please disregard my previous comment. Following is the solution as I thought:

public Boolean IsBst(Node nd) {
return IsBstI(nd, int.MinVal, int.MaxVal;
}

public Boolean IsBstI(Node nd, int min, int max) {
if (node.left != null) {
if (node.left < min || !IsBst(node.left, min, node.val) {
return false;
}
}

if (node.right != null) {
if (node.right > max || !IsBst(node.right, node.val, max) {
return false;
}
}

return true;
}

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

Suppose the LEFTnodes from top to bottom are 10, 6, 4, 5
root
/
10
/
6
/
4
/
5

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

IsValidBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);

bool IsValidBST(BinaryNode node, int MIN, int MAX)
{
if(node == null)
return true;
if(node.element > MIN
&& node.element < MAX
&& IsValidBST(node.left,MIN,node.element)
&& IsValidBST(node.right,node.element,MAX))
return true;
else
return false;
}

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

boolean isBst(Node n, int min, int max) {
if(n == null) return true;
if( n.data <= max || n.data > min) return false;
else return ( isBst(n.left, min, n.data) |&&
isBst(n.right, n.data, max));
}

first call will be isBst(root, -sentinel, sentinel); // sentinel = largest possible value.

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

If inorder traversal is in sorted order, then the tree is BST. Am I missing any other scenarios to consider ?

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

bool isBST(node* root)
{
bool isBst = true;
if (NULL == root)
return true;
if (root != NULL)
{
if (root->lchild != NULL && ((root->data) < (root->lchild->data))) {
isBst = false;
}
if (root->rchild != NULL && ((root->data) > (root->rchild->data))) {
isBst = false;
}
isBST(root->lchild);
isBST(root->rchild);
}
return isBst;
}

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

Its wrong, as you are not considering the cases when left subtree may have a right child which is bigger than right subtree node. e.g.
40
20 60
0 80

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.