Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




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

the question asks for a Valid Binary Tree, not a valid Binary Search Tree, so, the min max should not be a concern, rather whether the tree has two children per node at most.

- josearturodelosangeles October 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The question is "checking the tree is Binary Tree"
However the code is Binary Search Tree...
So I think the question might be typing error????

- young October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Binary tree will have atmost 2^h-1 nodes (full binary tree). Count the number of nodes and see if n <= 2h^-1 (n=number of nodes, h=height of the tree). If its satisfies this condition then the tree is said to be binary tree.

- smurugu October 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public boolean isBinaryTree(Node root) {
if (root == null) return true;
else if (root.children.length > 2) return false;
return isBinaryTree(root.children[0]) && isBinaryTree(root.children[1]);
}

- wut October 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BST {	
	
	private static Node prevNode = null;
	
	public boolean isBST(Node root){
		if (root != null){
			if (!isBST(root.left)){
				return false; 
			}
			if (prevNode != null && prevNode.data >= root.data){
				return false;
			}
			prevNode = root;
			return isBST(root.right);
		}
		return true;
	}

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

fdsafdsa

- Anonymous October 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean checkBST(Node root, int minValue, int maxValue)
{
if(root == null)
return true;
else if( root.data > minValue && root.data < maxValue && checkBST(root.left,minValue,root.data)
&& checkBST(root.right,root.data,maxValue))
return true;
else
return false;
}

static boolean checkBST(Node root) {
if(root == null)
return true;
/* 2nd approach : O(n2)
* else if(isLeftSubtreeLesser(root.left,root.data) && isRightSubtreeGreater(root.right,root.data) && checkBST(root.left) && checkBST(root.right))
return true;*/
// 1st Approach : O(n)
else if(checkBST(root,Integer.MIN_VALUE, Integer.MAX_VALUE))
return true;
else
return false;
}

- rakesh.swarankar November 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you could iterate the tree in an in-order fashion, you need to check if your values are ordered :)

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

/**
* Binary Search Tree ,value of left child must be less than value of parent, value of right child must be greater
* than value of parent
* Then we can use inorder traversal, if BST , after in order, all value of node must be sorted
* if previous value is greater current value is invalid
*/
public boolean isValidBSTCaller(TreeNode root) {
int prev = Integer.MIN_VALUE;
return isValidBST(root, prev);
}

public boolean isValidBST(TreeNode root, int prev) {
if (root==null) return true;
return (isValidBST(root.left,prev)) && (root.data>= prev) && isValidBST(root.right,prev=root.data);
}

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

public boolean isValidBSTCaller(TreeNode root) {
int prev = Integer.MIN_VALUE;
return isValidBST(root, prev);
}
// BST, left key <= parent key, right key >= parent key, inorder list sorted key data
// once prev key > current key, invalid
public boolean isValidBST(TreeNode root, int prev) {
if (root==null) return true;
return (isValidBST(root.left,prev)) && (root.data>= prev) && isValidBST(root.right,prev=root.data);
}

- John Zhang December 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

struct node* check(struct node* root)
{
	struct node* true=NULL;
	struct node* false;
	int key=root->data;
	if(root==NULL)
     return true;
     if(key > root->right->data || key <= root->left->data)
        return false;
    if(key<root->right)
	return check(root->right);
	if(key>root->left)
	return check(root->feft); 
	}
	
	boolean getBinary()
 	{
		struct node* a;
		a=check(head);
		if(a)
		return true;
		else 
		return false;
	}

- sahooj October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

struct node* check(struct node* root)
{
	struct node* true=NULL;
	struct node* false;
	int key=root->data;
	if(root==NULL)
     return true;
     if(key > root->right->data || key <= root->left->data)
        return false;
    if(key<root->right)
	return check(root->right);
	if(key>root->left)
	return check(root->feft); 
	}
	
	boolean getBinary()
 	{
		struct node* a;
		a=check(head);
		if(a)
		return true;
		else 
		return false;
	}

- Sahooj105 October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

static boolean checkBST(Node root, int minValue, int maxValue)
	{
		if(root == null)
			return true;
		else if( root.data > minValue && root.data < maxValue && checkBST(root.left,minValue,root.data) 
				&& checkBST(root.right,root.data,maxValue))
			return true;
		else
			return false;
	}

	static boolean checkBST(Node root) {
	    if(root == null)
	        return true;
	    /* 2nd approach : O(n2)
	     * else if(isLeftSubtreeLesser(root.left,root.data) && isRightSubtreeGreater(root.right,root.data) && checkBST(root.left) && checkBST(root.right))
	                return true;*/
	    // 1st Approach : O(n)
	    else if(checkBST(root,Integer.MIN_VALUE, Integer.MAX_VALUE))
	    	return true;
	    else 
	        return false;     
	    }

- rakesh.swarankar November 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Using min-max approach:

public static boolean isValidBST(TreeNode root) {
		if (root == null) {
			return true;
		}
		return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
	}
	
	// int min, int max version
	public static boolean isValidBST(TreeNode root, long min, long max) {
		if (root == null) {
			return true;
		}
		if (root.val <= min || root.val >= max) {
			return false;
		}
		return isValidBST(root.left, min, root.val) && 
				isValidBST(root.right, root.val, max);
	}

- guilhebl October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

struct node* check(struct node* root)
{
	struct node* true=NULL;
	struct node* false;
	int key=root->data;
	if(root==NULL)
     return true;
     if(key > root->right->data || key <= root->left->data)
        return false;
    if(key<root->right)
	return check(root->right);
	if(key>root->left)
	return check(root->feft); 
	}
	
	boolean getBinary()
 	{
		struct node* a;
		a=check(head);
		if(a)
		return true;
		else 
		return false;
	}

- Anonymous October 02, 2016 | 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