Amazon Interview Question Software Engineer / Developers


Country: India
Interview Type: Phone Interview


Comment hidden because of low score. Click to expand.
7
of 15 vote

boolean checkOneChild(int[] preorder)
{
for(int i=0; i<preorder.length-2; i++)
{
int a = preorder[i]-preorder[i+1];
int b = preorder[i]-preorder[preorder.length-1];
if(a*b<0)
return false;
if(a*b==0)
{
if(a+b<0)
return false;
}
}
}

- LoocalVinci on July 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1

- words&lyrics on July 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u please explain the logic with some example ?

- chad on July 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

-1.

Why does the BST have to contain ints?

Silly solution.

- Anonymous on July 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Logic is Simple. Vinci is checking, if the child node and the leaf node(last node) lies on the same side (Left or Right) of the Sub Tree. Means if the a*b is <0 means
1. Child is smaller then parent(i) and Last Node is greater then parent(i)
2. Child is Greater then parent(i) and Last Node is smaller then parent(i)

- piyush on August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if all the internal modes in BST have only one child then its preorder has a special property i.e. every element is min or max of all the succeeding elements.
let there be n elements in preorder.
check(int p[])
{
int min,max,i;
if(p[n-1]<p[n-2])
{
min=p[n-1];
max=p[n-2];
}
else
{
min=p[n-2];
max=p[n-1];
}
for(i=n-3;i>=0;i--)
{
if(p[i]>max)
max=p[i];
else if(p[i]<min)
min=p[i];
else
return 0;
}
return 1;
}

- Ashish on August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Vinci's approach is good, but the code sucks.

- Anonymous on August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ashish's approach seems good too. Reminds me of check if a given binary tree is a BST problem.

- Anonymous on August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

cud sum1 tell me the wat is the utility of chkin
if(a.b==0) and also y (a+b<0) is chkd??

- codinglearner on August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is a problem with a+b<0. Consider the below tree.

5
       /  \
      1   5

The preorder traversal is: 5,1,5
a=5-1=4
b=5-5=0
a*b==0 But a+b>0, the function returns TRUE. But, it should return FALSE.

- Aashish on August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Lol -100

- Geek on August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@shondik
bt in the normal bst we dont have the duplicates how cum the example taken valid then??

- codinglearner on August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@codinglearner, then why the condition if(a*b==0) raised here?

- Aashish on August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@shondik
dats wat i cudnt figure out...:(
n confused

- codinglearner on August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

According to Wiki also :
"The right subtree of a node contains only nodes with keys greater than or equal to the node's key."

- Psycho on August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code doesn't work for any of these inputs:
{{
{12,8,5,2,7,10,11,9,15,14,18}

{12,8,5,2,7,10,9,15,14,18}

{12,8,5,2,7,10,9}
}}

- Second Attempt on August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
6
of 6 vote

bool checkSingleChild(int[] preOrder, int n) {
        int min, max, i;
        min = max = preOrder[n-1];
        
        for ( i = n-2; i>=0; i-- ) {
        int term = preOrder[i];

        if ( term > max )  max = term;
        else if ( term < min )  min = term;
        else return false;
        }

        return true;
    }

- Debo on August 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose your tree contains 
5
  \
   5

In your case it will return false !!

- Psycho on August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

It's a BST and there should not be a duplicate.

- hari@hbiz.in on August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

A small correction will do

if ( term >= max )  
               max = term;

         else if ( term <= min )  
                min = term;

        else 
                return false;

- hari@hbiz.in on August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@hari@hbiz.in

According to wiki and any general idea :

In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:[1]
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

- Anonymous on August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The logic is simple. For a node, all successors are either less our greater than that node. Implementation may differ from person to person.

- victor on August 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

and I wonder still other people replying to this question. I think It was asked as an appetizer question.

- Geek on August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Theres also a NlogN solution for this problem.

Since its a BST and not a regular binary tree, we can reconstruct the binary tree from the pre-order traversal.

Algo::
a) First Element of the array is root.
b) Scan the array till we encounter an element greater than the root. This element marks the beginning of the right subtree.
c) Now, we have the elements of both the left and right tree. So, we recursively apply the above algorithm.

This algorithm will take NLogN time.

Once the BST is constructed, we can do a tree traversal and determine the internal nodes with one/two children in linear time

- DeathEater on August 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

- Administrator on July 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if the tree is

5
2 6
3
4
then the pre order is 5 2 3 4 6 , but ur algo returns true for this even though 5 has 2 children!

- suitsrk on August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@suitsrk: !(3 < 4 && 3 < 6) => 1 and returns 0..

- cobra on August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<limits.h>
int main()
{
  int count=0,*p;
  scanf("%d",&count);
  int i=0;
  p=(int *)malloc(sizeof(int)*count);
  for(i=0;i<count;i++)
  {
    scanf("%d",&p[i]);
  }
  int max=INT_MAX,min=INT_MIN;
  for(i=0;i<count;i++)
  {
     if(p[i]>max || p[i]<min)
	  break;
     if(p[i+1]>p[i])
	 {
	    min=p[i];
	 }
	 else
	 {
	   max=p[i];
	 }
  }
  if(i==count)
   printf("true");
  else
   printf("false");
}

- Anonymous on August 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution will not work for this input :

5
       /  \
     1   5

- Psycho on August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

This is almost same as what @LoocalVinci's logic is.

int checkEachNodeOneChild (int* arr, int size) {
  int i, a, b ;
  for ( i = 0 ; i < size-2 ; i ++ ) {
    a = arr[i] - arr[size-1] ;
    b = arr[i] - arr[i+1] ;
    if ( a*b < 0 )
      return 0 ;
    if ( a*b == 0 ) {
      if ( a == 0 ) {
        // This means root has all its child in right subtree
        if ( b > 0 )
           return 0 ;
      }
    }
  }
  return 1 ;
}

- Psycho on August 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

rebuilt the bst.
This is oN algorithm!

- jim on August 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

check the array from end. each element should be greater than max or less than min for the rest of the array.

- san on August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Guys

I normally don't comment on these questions, but I feel everyone has it wrong here. In a Pre-Order traversal where all non-leaf nodes have two children, what property can on extract? The thing to look for is that if a node value decreases, then there must be an increase somewhere. In other words, if a parent node has a left child (a decrease in value), then there must also be an increase value (a right child) in order for that parent to have two children. In short, if you count the number of times a node increases, and the number of times a node decreases, then in a tree with each non-leaf node that has two children, it should balance out perfectly.

Here is the algorithm

bool checkOneChild(vector<int> preOrderList) {
	if (preOrderList.size() == 1) return true; //Only root node is present, so return true;
	int increaseDecreaseCounter = 0; //long name, I know
	int prev = preOrderList[0];	

	for (int i=1; i < preOrderList.size(); i++) {
		if (preOrderList[i] >= prev)
			increaseDecreaseCounter++;
		else
			increaseDecreaseCounter--;
		
		prev = preOrderList[i];
	}

	return (increaseDecreaseCounter == 0);
}

- barry.steyn on May 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think u are wrong with the understanding,
"check if each non-leaf node has only one child"
consider this one,

5
   \ 
    5

your code will return false!

- Psycho on July 14, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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