Amazon Interview Question for SDE1s


Country: United States
Interview Type: Phone Interview




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

Depth first search passing max and min values for a sub tree

//in C++
/*One issue is if root->value is MAX/MIN_INT but we can always create a special function for root and check in there...though a root at either extream is going to make for a badly balanced tree
*/
bool isBinTree(node* node, int min=MIN_INT, int max=MAX_INT)
{
	if(node==NULL)
		return true;	//node tree is a valid tree

	if(node->value>=max || node->value <= min)
		return false;	//no duplicates allowed and must be in range

	

	return 	isBinTree(node->left, min, this->value) && 
		  	isBinTree(node->right,this->value,max);
}

- Anonymous September 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I suppose one could just attempt an in-order traversal as well, memoizing the previous node's key (k-1). If we encounter the situation that k-1 > k, then this cannot be a bst.

edit: Something like this, do the throw to terminate the test when the tree is not conforming

function traverse(node, cb) {
        if (!node) {
                return
        }
        traverse(node.left, cb)
        cb(node)
        traverse(node.right, cb)
}

function callback(node) {
        if (k_minus_one && node.key <= k_minus_one) {
                throw new Error("Not a BST")
        }
        k_minus_one = node.key
}

var k_minus_one


function isBinarySearchTree(root) {
        try {
                traverse(root, callback)
                return true
        } catch (e) {
                return false
        }
}

edit...reverse my comparator

- srterpe September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Depth first search passing max and min values for a sub tree

//in C++
/*One issue is if root->value is MAX/MIN_INT but we can always create a special function for root and check in there...though a root at either extreme is going to make for a badly balanced tree
*/
bool isBinTree(node* node, int min=MIN_INT, int max=MAX_INT)
{
	if(node==NULL)
		return true;	//node tree is a valid tree

	if(node->value>=max || node->value <= min)
		return false;	//no duplicates allowed and must be in range

	

	return 	isBinTree(node->left, min, this->value) && 
		  	isBinTree(node->right,this->value,max);
}

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

#include <iostream>

namespace amazon {

  template <class T>
  struct binary_node
  {
    using value_type = T;
    value_type value;

    binary_node<T>* left;
    binary_node<T>* right;
  };

  template <class T>
  bool check_for_binary_search_tree(const binary_node<T>* root)
  {
    if (root->left && (root->left->value > root->value))
      return false;
    if (root->right && (root->right->value < root->value))
      return false;

    bool left_check = true, right_check = true;
    if (root->left) left_check = check_for_binary_search_tree(root->left);
    if (root->right) right_check = check_for_binary_search_tree(root->right);

    return left_check && right_check;
  }

} // namespace amazon

int main()
{
  using type = int;
  using node = amazon::binary_node<type>;

  node* root = new node
  {
    8,
    new node
    {
      3,
      new node
      {
        1,
        nullptr,
        nullptr
      },
      new node
      {
        6,
        new node
        {
          4,
          nullptr,
          nullptr
        },
        new node
        {
          7,
          nullptr,
          nullptr
        }
      },
    },
    new node
    {
      10,
      nullptr,
      new node
      {
        14,
        new node
        {
          13,
          nullptr,
          nullptr
        },
        new node
        {
          15,
          nullptr,
          nullptr
        }
      }
    }
  };

  std::cout << "Result: " << amazon::check_for_binary_search_tree(root) << std::endl;

  return 0;
}

- Bikinev September 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isBST(Node *root, int *prev)
		{
			if(root == NULL)
				return true;
			if(!isBST(root->left,prev))
				return false;
			if(prev >= root->data)
				return false;
			else
				prev = root->data;
			return isBST(root->right,prev);
		}

	int main()
	{
		int prev = INT_MIN
		cout<<isBST(root, &prev);
	}

- Greg September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You should check the binary tree property on the current node first, e.g. if a node has a value 5 and the left child of this node has the value 10, you want to return false immediately, there is no point in checking all of the subtree of 10 (which could be a BST coincidentally and also huge).

- Anonymous September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 6 vote

Simple Recursive method

isBST(Node *root)
{
	bool l = r = true;
	if( (root == NULL) || (root->left == NULL && root->right == NULL) )
		return true;

	if(root->left != NULL)
	{
		if(root->data > root->left->data)
			l = isBST(root->left);
		else
			l = false;
	}
	
	if(root->right != NULL)
	{
		if(root->data < root->right->data)
			r = isBST(root->right);
		else
			r = false;
	}
	return (l && r);
}

- Rahul September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Better... +1 from me...

- rajmalraj567 September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

does not work for:
3
/ \
2 5
/\
1 4

- Anonymous September 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is working fine for your given test-case.....
In this case function will return false.... Which is correct...

- Rahul September 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesn't work. In a binary search tree all the nodes in the left sub tree should be lesser than root, and all the nodes in the right sub tree are greater than root.

For the test case
3
2 5
1 4

The function is called using isBST(3)
which in turn calls
isBST(2) and isBST(5)(this is true)
now isBST(2) calls
isBST(1) and isBST(4) which is also true

so this method actually returns true.

See, at any point in each level of recursive call you don't have any information about the ancestors of that node. Hence there is no way you can say whether the tree is BST using this method.

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

Something on the lines of srterpe suggested. Use the inorder traversal (since the inorder traversal of a BST gives sorted numbers in ascending oprder) and compare the root with its left or right child for predecessor or successor respectively.

int isBST(struct node * root)
{
	if(root)
	{
		if(root->left)
		{
			if(root->data > root->left->data)
			{
				isBST(root->left);
				isBST(root->right);
			}
			else
				return false;
		}
		else if(root->right)
		{
			if(root->data < root->right->data)
			{
				isBST(root->left);
				isBST(root->right);
			}
			else
				return false;
		}
	}
	return true;
}

void main()
{.
.
if(isBST(root))
		printf("\nIt is a BST!");
	else
		printf("\nIt is not a BST!");
.
.
}

- envy1426 September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BT<Key extends Comparable<Key>, Value> {
    private Node root;

    private class Node {
        Key   key;
        Value value;
        Node  left, right, parent;

        Node(Key k, Value v) {
            key = k;
            value = v;
        }
    }

    public Value get(Key k) {
        /* Add logic to retrive the value for a Key from the Tree */
    }

    public void put(Key k, Value v) {
        /* Add logic to insert an element to the Tree */
    }

    private static boolean lessThan(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    //== Check if BT using In-Order traversal ==================================
    private boolean checkBSTInorder(Node x, Key lastKey) {
        if (x == null) return true;
        checkBTInorder(x.left, lastKey);
        if (lastKey != null && lessThan(x.key, lastKey))
            return false;
        else {
            lastKey = x.key;
            checkBTInorder(x.right, lastKey);
        }
        return true;
    }

    public boolean checkBSTInorder() {
        if (root == null) return true; // empty tree - can be a BST.
        return checkBTInorder(root, null);
    }
    
    //== Check if BT - alternative technique ==================================
    private boolean checkBST(Node x) {
        if (x == null) {
            return true;
        } else {
            if (x.left != null && lessThan(x.key, x.left.key)) {
                return false;
            } else if (x.right != null && lessThan(x.right.key, x.key)) {
                return false;
            } else {
                return checkBT(x.left) && checkBT(x.right);
            }
        }
    }

    public boolean checkBST() {
        if (root == null) return true; // empty tree - can be a BST.
        return checkBT(root);
    }

    //== Test Client ===========================================================
    public static void main(String[] args) {
        String[] a = { "L", "A", "M", "B", "N", "C", "O", "D", "P", "E", "Q", "F", "R", "G", "S", "H", "T", "U", "I", "V", "J", "W", "K", "X", "Z", "Y"};
        BST<String, String> bt = new BST<>();
        for (String x : a) {
            bt.put(x, x); // Setting value same as key - but can be anything.
        }

        System.out.println("Is BST: " + bt.checkBST());
        System.out.println("Is BST (using In-order traversal technique): " + bt.checkBSTInorder());
    }
}

- sks September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean isBST(Node root) {
	if(root.left == null && root.right == null) return true;
	//in Java, if A is false, then A && B doesn't evaluate B, therefore short circuits
	if(root.right == null) return root.left.val < root.val && isBST(root.left);
	if(root.right == null) return root.val < root.right.val && isBST(root.right);
	return root.left.val < root.val && root.val < root.right.val && isBST(root.left) && isBST(root.right);
}

- Adam September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correction to that, the 3rd condition should be

if(root.left == null)

- Adam September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class IsTreeBST {
	
	
	public static void main(String[] args) {
		
		NodeIsTreeBST temp = new NodeIsTreeBST();
		temp = temp.NodeIsTreeBST(6);
		temp.left = temp.NodeIsTreeBST(5);
		temp.left.left = temp.NodeIsTreeBST(3);
		temp.left.left.right = temp.NodeIsTreeBST(20);
		temp.right = temp.NodeIsTreeBST(33);
		temp.right.left = temp.NodeIsTreeBST(20);
		temp.right.right = temp.NodeIsTreeBST(50);
		
		
		System.out.println(isBST(temp, Integer.MIN_VALUE, Integer.MAX_VALUE));
	}
	
	
	public static boolean isBST(NodeIsTreeBST node , int min , int max) {
		
		if(node == null)
			return true;
		
		if(node.data < min || node.data>max)
			return false;
		
		
		if(!isBST(node.left, min, node.data-1) || !isBST(node.right, node.data+1, max))
			return false;
		
		
		
		return true;
		
	}

}


class NodeIsTreeBST {
	
	int data;
	NodeIsTreeBST left;
	NodeIsTreeBST right;
	
	public NodeIsTreeBST NodeIsTreeBST(int data) {
		
		NodeIsTreeBST temp = new NodeIsTreeBST();
		temp.data = data;
		temp.left = null;
		temp.right = null;
		return temp;
		
		
	}
}

- shukad333 September 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//suppose treenode data is normal integer
bool JudgeBST(TreeNode *pTreeNode)
{
if(!pTreeNode) return true;

if(pTreeNode->leftchild && pTreeNode->rightchild){
return (pTreeNode->leftchild->data < pTreeNode->rightchild->data) &&
JudgeBST(pTreeNode->leftchild) && JudgeBST(pTreeNode->rightchild);
}else if(pTreeNode->leftchild){
return JudgeBST(pTreeNode->leftchild);
}else if(){
return JudgeBST(pTreeNode->rightchild);
}
return true;
}

- zhouyouisme September 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool is_bst(Node* n, Node* parent = null, bool left = true)
{
    if (n == null) { return true; }
    if (parent && left && n->value > parent->value) { return false; }
    if (parent && !left && n->value < parent->value) { return false; }
    return is_bst(n->left, n, true) && is_bst(n->right, n, false);
}

- Joe September 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursively, by passing the current MIN and MAX down.

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidNode(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean isValidNode(TreeNode node, int min, int max) {
        if (node == null)
            return true;
        if (node.val > max || node.val < min)
            return false;
        return isValidNode(node.left, min, node.val - 1) && isValidNode(node.right, node.val + 1, max);
    }
}

- Qiusheng September 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java Code :

public boolean isBinaryTree(BinaryNode node) {

		if (flag == true) {

			// Leaf Node
			if (node.left == null && node.right == null) {

				return flag;
			}

			else if (node.right != null && node.right.data >= node.data) {

				isBinaryTree(node.right);
			}
			else	{
				
				flag = false;
			}
			
			if ((node.left != null && node.left.data < node.data)) {

				isBinaryTree(node.left);
			}
			else	{
				
				flag = false;
			}
			
		}

		return flag;

	}

- Santhosh September 21, 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