Ebay Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

You need to use the definition of BST, i.e., the left node is smaller and the right node is bigger than the parent node, and traverse the tree to check if that condition satisfies.

public boolean isBSTMain(Node root) {
	return (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}

private boolean isBST(Node node, int min, int max) {
	if (node == null)  return true;
	
	if (node.data < min || node.data > max) return false;

	// left should be in range min...node.data
	boolean leftOk = isBST(node.left, min, node.data);
	if (!leftOk) return false;

	// right should be in range node.data..max
	return isBST(node.right, node.data, max);
}

This solution is O(n)

- oOZz June 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Correct me if I'm wrong, I think this would not work for the below case. The correct approach to this problem is the one posted by vgeek.

---------------------------5
-------------3				10
--------------------------11

PS: Forgive me for the poor tree structure.
Basically 5 is root of the with 3 as left child (3 has 11 as right child) and 10 as right child.

- arun_lisieux June 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@arun_lisieux it works buddy, but don't take my word for it, here is a unit test, go ahead and test it yourself.

@Test
public void testIsBST() {
	Node root = new Node(5);
	root.left = new Node(3);
	root.right = new Node(10);
	root.left.right = new Node(11);
		
	boolean bst = isBST(root);
	assertEquals(false, bst);
}

- oOZz June 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How to display double value double d = 999999999999999.99 in String format with the same value.

- madhu June 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@arun

that is an invalid BST as the value 11 should be the right child of 10, not of 3 - it would never be inserted in that position

- emalaj23 June 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it should be

boolean leftOk = isBST(node.left, min, node.data-1);
if (!leftOk) return false;

// right should be in range node.data..max
return isBST(node.right, node.data+1, max);
}

- Champ June 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

bool isBST(Node root) {
    return isBSTNode(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

bool isBSTSubTree(Node node, int minValue, int maxValue) {
    return (node == null ||
            (node.value > minValue
             && node.value < node.maxValue
             && isBST(node.left, minValue, node.value)
             && isBST(node.right, node.value, maxValue)));
}

- coder June 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

if a binary tree is a bst, an inorder traversal should return a sorted array...O(n) in both space and time...let me think if i can find something better

- The Artist December 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Earlier I used to say if each element is greater/equal to it's left element and less/equal to it's right element this it's a BST. But in this approach the major flow is it does not take ancestors into considerations. This I learnt from this forum itself and found the below mentioned solution (not able to locate the original thread):
Solution: For a given node, all nodes in its left subtree should be less than or equal to this element and all nodes in its right subtree should be greater than or equal to this element. Here is the code for it:

IsBST(root, root->value, root->value);

boolean isBST(Node* root, Integer min, Integer max) {
    if (root != null) {
        return  (min <= root->value <= max) && IsBST(root->left, min, root->value) && IsBST(root->right, root->value, max);
    }

    return true;
}

- Mario December 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a good solution : O(n) time complexity and O(1) space if not consider the stack call, in stead of the InOrder solution which uses O(n) time and O(n) space.

Here is the java version:

public static boolean isBst(TreeNode root, int min , int max){
        if(root==null) return true; //modified
        if(root.d < min || root.d >max) return false;
        return isBst(root.left, min, root.d-1) && isBst(root.right, root.d+1, max);
    }

- Kamy December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one Mario, it is better than my solution and Kamy you are right if we ignore the call stack memory consumption in will be O(1) space algorithm but even if we consider the call stack memory the worse case memory will be 2*log(n) when recursing through a leaf node (for a balanced tree assuming the 2 int params of max and min) which makes it O(log n) space still better than inorder traversal for all n > 2, But even this can be reduced by senfing the pointers to the actual min node and max node rather than the data in it.

- The Artist December 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The first line in the code should be
if(root==null) return true;

and not

if(root!=null) return true;

- Mike January 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To pass the root->value in the top call as min,max parameters is WRONG. It should the lowest possible and the largest possible integer (tree's value type) values as it is done in the "coder"s comment on June 30, 2013.

- celicom September 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Use inorder traversal. Keep a static pointer that is previous that points to the previous node.Note inorder traversal will lead to you a sorted set of values.If at any time current value is less than the previous value then it is not a bst otherwise it is:

#include <stdio.h>
#include <stdlib.h>
typedef struct node node_t;
struct node
{
    int data;
    node_t *left;
    node_t *right;
};
node_t *newNode(int data)
{
    node_t *nn=(node_t *)malloc(sizeof(node_t));
    nn->data=data;
    nn->left=NULL;
    nn->right=NULL;
}
int isBst(node_t *root)
{
    static node_t *prev=NULL;
    if(root)
    {
        if(!isBst(root->left))
            return 0;
        if(prev!=NULL&&root->data<=prev->data)
            return 0;
        prev=root;
        return isBst(root->right);
    }
    return 1;
}
int main()
{
    node_t *root      = newNode(4);
    root->left        = newNode(2);
    root->right       = newNode(5);
    root->left->left  = newNode(1);
    root->left->right = newNode(3);

    if(isBst(root))
        printf("Is BST");
    else
        printf("Not a BST");
    return 0;
}

- vgeek June 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple recursive call to each of the nodes to check if the left subtree is less than equal to Current Node and right subtree is greater than equal to current node.

class BinaryTree {
	private class Node {
		int value;
		Node leftChild;
		Node rightChild;

		public Node(int val) {
			value = val;
			leftChild = null;
			rightChild = null;
		}
 	}
	
	Node root = null;

	private bool checkBST(Node currNode) {
		if(currNode == null) return true;
		else if(currNode.leftChild == null && currNode.rightChild == null) return true;
		else {
			if(currNode.leftChild != null && currNode.rightChild != null)
				return( 		currNode.value >= currNode.leftChild.value 
						&& 	currNode.value <= currNode.rightChild.value
						&& 	checkBST(currNode.leftChild)
						&&	checkBST(currNode.rightChild));
			if(currNode.leftChild != null && currNode.rightChild == null)
				return( 		currNode.value >= currNode.leftChild.value 
						&& 	checkBST(currNode.leftChild)
						&&	checkBST(currNode.rightChild));
			if(currNode.leftChild == null && currNode.rightChild != null)
				return( 		currNode.value <= currNode.rightChild .value 
						&& 	checkBST(currNode.leftChild)
						&&	checkBST(currNode.rightChild));
			return false;
				
		}
		return false;
	}

	public void isBST() {
		if(checkBST(root))
			System.out.println("The BT is BST");
		else
			System.out.println("The BT is not BST");
	}		
}

- Subhajit June 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this should not work in case of this bst but yours will work:
-----3------
--2---- 5
1-4

- vgeek June 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[20],i=0;
void check(struct treeNode *root)
{
struct treeNode *q=root;
if(q)
{
check(q->left);
a[i++]=q->data;
check(q->right);
}
else
return ;
}
int main()
{ check(root);
for(j=0;j<i-1;j++)
{
if(a[j]>a[j+1])
{
printf("not bst\n");
break;
}
}
if(j==i-1)
printf("bst\n");

- faisal June 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

learn a lot from your answers.
main idea is : left smaller and right bigger than parent.

- zhuyu.deng July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

please explain the use of min and max in the above code??

- abc December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

a BST has minimum element in the leftmost .. & maximum in the right most ...... just take these two and
just check min < element in the tree <max

- jkl December 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Initially make
min=leftMostElement;
max=rightMostElement;


That serve the purpose

- Tendulkar February 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public boolean isBST() {
		if (root == null) {
			return true;
		}
		//initialize min
		TreeNode ptr = root;
		while(ptr.left != null){
			ptr = ptr.left;
		}
		Integer min = ptr.element;
		
		//initialize max
		ptr = root;
		while(ptr.right != null){
			ptr = ptr.right;
		}
		Integer max = ptr.element;
		
		return isBST_helper(root, min, max);
	}

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

- Kevin March 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Python version:

def is_valid_bst(node):
	previous_value = None
	stack = []

	while stack or node:
		if node:
			stack.append(node)
			node = node.left
		else:
			node = stack.pop()
			if previous_value > node.value:
				return False
			else:
				previous_value = node.value
				node = node.right

	return True

- yokuyuki June 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Post order traverse should give us a sorted array.

- saumil June 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Inorder traversal is the one that gives the values in sorted order...

- yokuyuki June 14, 2013 | 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