Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

Do inorder traversal of the tree if the inorder traversal is sorted then it is a BST otherwise not.

- khunima March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution is simple but it requires O(N) extra space. Thats its only drawback.

- kr.neerav March 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

public boolean isValid(Node root) {
     return isValidBST(root, Integer.MIN_VALUE,
          Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int MIN, int MAX) {
     if(node == null)
         return true;
     if(node.value > MIN 
         && node.value < MAX
         && isValidBST(node.left, MIN, node.value)
         && isValidBST(node.right, node.value, MAX))
         return true;
     else 
         return false;
}

- ilya March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good one..
to optimize this solution we can have a global flag initialized with true will be set for any mismatch of below mentioned condition:

node.info > node.left.info
&&
node.info < node.right.info

in case of any mismatch set global flag to false and exit;

After execution of method in case flag is still true then binary tree is a BST

- PKT March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good solution. And awesome use of Integer.MIN_VALUE and Integer.MAX_VALUE

- kr.neerav March 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very good code.

I have one input regarding programming style, whenever you have code like:

if ( condition ) {
    return true;
} else {
    return false;
}

You can simply replace it by:

return condition;

- manishi.singh April 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

C++ version:

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 March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

So many tree problems? That is ridiculous.

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

Looks like some one got assignments on Tree and is posting here.

- AJ March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The invariant for any single BST tree node is only these two conditions:
a) node.left.data <= node.data <= node.right.data
b) and recursively: isBST(node.left) and isBST(node.right) must be true.

A simple java solution is:

public boolean isBST(Node node) {
    // Base cases
    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;

    // recurse. If either or both of left and right subtree is null, 
    //    it will handled by base-case above
    return isBST(node.left) && isBST(node.right);
}

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

good answer

- Anonymous November 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean validBST(Node root)
   {
       if(root == null) return true;
      return  root.left.data < root.data && root.right.data>root.data && validBST(root.left) && validBST(root.right);
 }

Add the child null case too in this please

- Danish Shaikh (danishshaikh556@gmail.com) March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Danish, what if root.left or root.right == null? You are not checking for those conditions.

- Anonymous March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int check(struct tnode *root,int min,int max)
{
    if(root==NULL)
       return 1;
    if(root->val>=min && root->val<max)
       return check(root->left,min,root->val) && check(root->right,root->val,max);
    return 0;
}

- Nitin April 01, 2014 | 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