Amazon Interview Question for Software Engineer / Developers


Team: Kindle
Country: India
Interview Type: In-Person




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

this code will work for both case if n is present in BST and if n is not a part of BST
int nextBigNum( struct node * root, int n)
{
int nextBig =INT_MIN;

struct node * temp =root;

while(root!=NULL)
{
if(root->data > n)
{
nextBig=root->data;
root=root->left;
}
else
{
root=root->right;
}
}

return nextBig;
}

- Duke87 November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great Duke87! It's perfect! and in O(h) once!!

- mag November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wondering how did you come up with this algorithm.

- Richard November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

aren't you being funny rick...if searching for something in a binary search tree is taking more than O(h) time then you are definitely doing something wrong.

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

Artist, what I meant was that, it is straightforward to first search the given element and then seek for its successor. The method given above is definitely much better, and I have no clue how did Duke87 come up with it. That's why I ask.

- Richard November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hmm...look at my comment below on CodePredator's solution. Searching for the number and finding the next successor was out of question as you don't know whether the number is present in the tree or not...

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

Wow!!!I didnt get it first time I saw it!!!

- CodePredator November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Duke87,
Your algorithm is conceptually correct, but for the sake of completeness you might like to consider addressing the below case which currently will return wrong answer.

Consider a tree with single node whose value is INT_MIN. In this case we expect a null value or something similar to be returned to indicate that the tree does not have any solution but your solution will return INT_MIN which is the value of the root node and is incorrect answer.

- buckCherry November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if tree is created in this order 13 6 9 10 11
if number is 9 we get answer 11 and not 10

- AK November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

AK:
Building a BST by adding 13, followed by 6, followed by 9,..finally by adding 11, we'll have a tree whose root =13. Root=13 will have only left child=6. 6 will have 9 as right child, 9 in turn will have 10 as right child and finally 10 will have 11 as right child.

With this BST, if you apply 'Duke87''s algorithm, then the value of nextBig
after 1st iteration is : 13 (since 13 > 9 )
after 2nd iteration is : 13 (i.e. unchanged since 6 < 9 )
after 3rd iteration is : 13 (i.e. unchanged since 9 > 9 is false)
after 4th iteration is : 10 (since 10 > 9 )

Thus final answer is 10 (not 11).
Let us know how did you get 11.

- buckCherry November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To : buckCherry's reply on November 06, 2012

Well I believe it should always be part of question on what should function return if no “next big number” found. If not mentioned by interviewer then interviewee should really ask.

If function returns an integer value then there is no question of null. It purely depends on what client code expects and how intelligent client code is. If client is intelligent enough to determine that returned value is equal or less than input number then client code can understand that there isn’t exist next big number in the tree. This is one of the scenario and solution I could think of. But again it depends on what client code really expects, in short what is the exact requirement.

And yes, in terms of finding the next big number code works fine.

- maverick November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@maverick:
Not sure what you intend to tell towards my post. Anyway let me first quote this excerpts from my post "..we expect a null value or something similar to be returned to indicate that the tree does not have any solution..".
So clearly null was just an option and I think you've missed out the "something similar" part of my post. Let me know if you still have any confusion!!

- buckCherry November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes I understood and agreed what you meant to say. I just wanted to clarify because you reply is very specific to this solution code which returns int.

I was just trying to find out what could be that “something similar” and tried to explain on that a bit.

It’s great to have concrete answer of question raised on a concrete solution ,not just conceptual answer.

- maverick November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Try to solv this prblm by considering it as binary tree....not BST

- mathan November 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mathan: the answer to your problem is trivial...you'll have to go through all the nodes, checking if the value at a given node is less than the previously found max and more than the given number, then update the max.

- Anonymous November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
node *left;
int data;
node *right;
};

node *insert(node *root, int data);

void findnextbigger(node *root, int data);

int main()
{
node *root = NULL;
int n1 =0;
int n,i;
int input[20];
printf("\n enter size of array=");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&input[i]);

printf("\n Enter the node data for which next bigger data to find:");
scanf("%d",&n1);

for(i=0;i<n;i++)
{
root = insert(root, input[i]);
}

findnextbigger(root, n1);
return 0;
}

#define INT_MIN -999
void findnextbigger(node *root, int n1)
{
node *ptr = root;

node *tmp= NULL;

int nextbigdata = INT_MIN;

while(ptr !=NULL)
{
if(ptr->data == n1)
{
/*find inorder successor of n1*/
printf("\n find inorder successor of n1");
tmp = ptr->right;
if(tmp != NULL)
{
while(tmp->left != NULL) tmp = tmp->left;

printf("\nNext Bigger node value of %d is %d: ",n1,tmp->data);
break;
}
else
{
if(nextbigdata == INT_MIN)
{
/* last node */
printf("\n No Next Bigger value than %d", n1);

}
else
{
printf("\nNext Bigger node value of %d is %d: ",n1,nextbigdata);
}
break;
}
}
else if(n1 < ptr->data)
{

nextbigdata = ptr->data;
ptr = ptr->left;
}
else if(n1 > ptr->data)
{
ptr = ptr->right;
}
}


}


node *insert(node *root, int data)
{
if(root == NULL)
{
root = (node *)malloc(sizeof(node));
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}

if(root->data > data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);

return root;
}

- Pankaj Gupta November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you should add a condition that is
if (nextBig ==INT_MIN )
no number is present in the BST which is greater than given number.

Just for better understanding.

- Psycho November 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wrong code. consider following tree: Root(2)->right child(5)>right child(7) and you are given n=5, Your code won't return 7 which is incorrect.

- Anonymous1 March 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 6 vote

1. Search for the number ( TC: O(h) )
2. Find its in order successor ( TC: O(h) )
Total TC: O(h) but in two passes

- mag November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Guys, Duke87's algorithm is perfect and works in O(h), I would highly recommend that as optimal solution, please upvote!

- mag November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

int nextInBST(int num, Node root)
{
    if(root == NULL)
      return -999;
    int n;  
    n = nextIntBST(int num, Node root->left);
     if(n != -999)
      return n;
     
     if(root->info > num)
       return root->info;
    n = nextIntBST(int num, Node root->right);    
    return n;
}

- CodePredator November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice solution...

- pradegup November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int nextIntBST(int num, node* root)
{
    if(root == NULL)
      return -999;
    int n;  
    n = nextIntBST(num, root->left);
     if(n != -999)
      return n;
     
     if(root->data > num)
       return root->data;
    n = nextIntBST( num, root->right);    
    return n;
}

It is a nice solution, the idea is the first successor that is greater than the number in "In order traversal"

- tcl00 November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice but not the best. The worst case time taken for this algorithm will be O(n) (when there is no element bigger than the given number or the biggest number in the tree is the answer) which makes it a O(n) algorithm. Now if searching for anything in a binary search tree is taking more than O(h) time than you should really think twice. In the above algorithm you are blindly attacking the root->left which is not required if root->data was less than the given number. In that case you already know that the number you are searching for lies, if present, in the right sub tree of the root element

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

also rather than returning -999 you might want to return something that you will be sure of is not a solution (say for example n-1) what if the solution itself is -999?

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

I think solution given by Duke87 is better as it does not involve recursion.

- kanhaiya November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

We can do it in O(h) complexity by using the following method:
1. Search for the element 'n' in the BST, as you search add the elements in the path to a stack
2. If element is found and the element has a right subtree, the leftmost element in the right subtree will be the next biggest element.
3. If element is not found or the element is found but does not have right subtree, then pop elements from the stack until you find an element that is greater than 'n'. This will be the next biggest element.

Funda : by maintaining a stack we can traverse back and easily find the inorder successor with in O(h) time.

- CodePredator November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you are taking extra space ( a stack ) then you don't have to perform complex algorithm, just storing in order traversal in an array would do it!

- mag November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But the space needed in this method is also bounded by O(h). Storing in array would need O(n).

- CodePredator November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Great book: Elements-Programming-Interviews by Adnan-Aziz

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

Do an inorder traversal of the BST. In place of print test whether node->data-number is negative. If yes print that number.Complexity O(n)

static bool is_found = 0;
void closest_num( node* root, int number )
{
    if( root == NULL)
         return;
     closest_num(root->left, number);
      if( !is_found &&root->data > num ){
         cout << root->data;
          is_found = 1;
      }
      closest_num(root->right, number);
}

- aj__ November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int search_num( node *root, int num)
{
    if(NULL == root)
       return 0;
    if(num == root->data)
       return 1;
    if(num > root->data && root->right)
    {
         // recursive call with right node
         return(search_num(root->right, num))
    }
    else if(num < root->data && root->left)
    {
         // recursive call with left node
         return(search_num(root->left, num))
     }
      
     return 0
}

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

search number recursively,
when found
check if it has right child .
if yes , this is the number
if no right child
return
now the calls will start unwinding check number with data of root
if big this is the number.

- AK November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

AK:
Unless you write a pseudo code, it's very difficult to evaluate the correctness of your solution. In addition, see my response above, where I think you've mistaken got wrong answer for a tree with 13 6 9 10 11.

- buckCherry November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def inOrderSuccessorMain(root, node):
    if root == None or node==None or (root.left==None and root.right):
        return False
    return inOrderSuccessorHelper(root, node)
    

def inOrderSuccessorHelper(root, node):
    found = False

    if root == None:#node not found then return False
        return found

    elif node.data < root.data:#node less than root then search left subtree
        found = inOrderSuccessor(root.left, node).
        if found == None:#if found=None then root is the successor
            return root
            
    elif node.data > root.data:#node less than root then search right subtree
        found = inOrderSuccessor(root.right, node)#found can be False, None, or some node
        
    else:
        if root.right != None:# Find left most node of right subtree
            found = rightSubTree(root.right)
        else
            return None # return None if no right node exists

    return found

def rightSubTree(root):
    if root.left == None:
        return root
    else:
        return rightSubTree(root.left)

- G10 April 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse the BST in order and keep track of the previous value. Since BST inorder traversal results in ascending order, if the previous node visited is the required number, then the current node is the next big number. Below is the pseudo code.

Node* prevNode;
Search(Node* node,int n)
{
if(node== NULL)
return;
Search(node->left,n);
if(prevNode->data == n)
Print(node->data);
prevNode= node;
Search(node->right,n)

- fecklessCoder May 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

findNextBiggernumber(tree *root,int num,int &next)
{
if(!root) return -9999 ;
if(root->data>n&&root->data<next)
{
next=root->data ;
findnextbiggernumber(root->left,num,next) ;
}
else
findnextbiggernumber(root->right,num,next) ;
return next ;
}

- abhishek July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse the tree inOrder, & set prev (when node with data 'num' found).
If prev is already found, then return curr (i.e.- root) in recursion.

Handles all cases. Returns NULL if succ/num node doesn't exist

struct node * inOrderSuccessor(struct node * root, int num){
	struct node * prev = NULL;
	return find(root, prev, num);
}

struct node * find(struct node * root, struct node *& prev, int num){
	static bool found = false;
	static struct node * succ = NULL;
	if(root){
		find(root->left, prev, num);

		if(prev && !found){
			found = true;
			succ = root;
		}
		else if(root->data == num){
			prev = root;
		}

		if(!found)
			find(root->right, prev, num);
	}
	return succ;
}

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

int greater(Bt t, int n) {
		int big = t.value;

		while (t.value != n) {
			if (n < t.value) {
				big = t.value;
				t = t.left;
			} else {
				t = t.right;
			}
		}

		if (t.right == null) {
			if (t.value > big)
				return -1;
			else
				return big;
		} else
			return t.right.value;
	}

}

- Adi September 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Break the problem into two steps: a) find its number b) find its successor.

To find a number in a BST, you look at the root value. If you have match, you're done. If your desired value is less than root, search the left subtree; otherwise, search the right subtree.

To find the successor of a BST's root note, find the minimum value of the right subtree.

To find the minimum value of a tree, determine if the root node has a left subtree. If it does, recursively return the minimum value of the left subtree. Otherwise, return the root's value.

- Steve November 04, 2012 | 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