Amazon Interview Question Software Engineer / Developers


Country: India
Interview Type: Written Test


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

since the array is strictly increasing first then strictly decreasing, therefore for the increasing part of the array if, i+1=j then definitely
a[i]<a[j] and for decreasing part a[j]<a[i],

we can use modified binary search to search the array.

consider the array
int[] arr = new int[] {1,3,5,7,19,221,132,56,8,6,4,2,1,-3,-17};

here we need to find k such that, for three consecutive elements i, k, j, a[i]<a[k] and a[k] > a[j]

step 1 :

so, first we need to find the ending of increasing part of the array, lets the end index of increasing part as k.

use a modified binary search to find k

int findK(int[] arr, int low, int high)
	{
		if(arr.length<=2)
			return -1;
		
		
		
		int mid=(low+high)/2;
		
		if(low==mid|| mid+1==high )
			return -1;
		
		if(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1])
			return mid;
		
		int n1= findK(arr, low, mid);
		int n2= findK(arr, mid, high);
		
		if(n1!=-1)
			return n1;
		if(n2!=-1)
			return n2;
					
		return -1;
		
	}

step 2 :

Now search the increasing part of array using binary search

BinarySearch(int[] arr, low, k)

step 3:

and decreasing part using binarysearch

BinarySearch(int[] arr, k+1, high)



sum all the above steps in a single wrapper function

int searchIncresingDecreasingArray(int[] arr, int N)
{
	
	int k = findK(arr, 0, arr.length);
	
	//now search only increasing array using binarysearch
	
	int res = binarySearch(arr, 0, k, N,true);
	
	if(res!=-1)
		return res;
	else 
		return binarySearch(arr, k+1, arr.length, N,false);
	
	

}

- rajeshp on May 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is pretty much what i thought.

- krishna on May 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@rajeshp i think this is not binary search. binary search in which we would be able to prune half part every time on function calling. see worst case it will go O(n) time.

chk if i am not wrong. even if we do this search we are increasing overhead on memory every time calling recursion.

- time on May 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, time is saying right.... your algo is more like quick sort with O(log n) complexity in average case but O(n) in worst cast

But still better than Linear Search: O(n)

- ravigupta on May 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the first step, we are rejecting one part which is sorted, So Its complexity is O(log n).
if a[i]>a[k]>a[j] => a[k,n] is sorted in decreasing order, So discard this part and search in a[1,k]
else if a[i]<a[k]<a[j] => a[1,k] is sorted in increasing order, So discard this part and search in a[k,n]
else a[i]<a[k]>a[j] => a[k] is result and we are done

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

Yes, in the worst case, it's still O(n). So instead of getting middle=(low+high)/2, middle=rand(high) might be a better choice to select the pivot

- Ted on May 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This can be solved like binary search, you can watch complete solution given in this wonderful video
youtu.be/Cwh_-O1dsDQ

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

in case of 3 elements like 231 k will be 3 but your algo return -1 because low is 0 high is 2 (2+0)/2=1 and 1+1==high (mid+1==high return -1)i don't understand whats problem in this or where i doing some mistake?

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

Code for finding the max value in O(logn) assuming the increasing and decreasing part don't have duplicates.

int find_max(int *array, int size)
{
        int low_bound, mid, low, high;
        low_bound = low = 0;
        high = size - 1;

        while (low <= high) {
                mid = (low + high) / 2;
                if (mid == low_bound) {
                        /* Only one element */
                        if (mid == high)
                                return mid;
                        else
                         /* 2 elements in increasing order */
                                return mid + 1;
                }
                if (array[mid - 1] < array[mid] && array[mid] < array[mid + 1])
                        low = mid + 1;
                else if (array[mid - 1] > array[mid] && array[mid] > array[mid + 1])
                        high = mid - 1;
                else /* max value found */
                        return mid;
        }
}

- arun.edarath on November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Find the maximum elements in array - O(logn)

Now if element > max - Not found

Form two sorted array and do binary search.

Total time O(logn)+O(logx)+O(logn-x)~ OLog(n)

- nagen547 on May 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

This question is same as searching in a rotated sorted array

- Sriram on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

no,for rotated sorted array, the two parts are both increasing.

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

Anonymous is right.The logic isnt same for 1 3 5 8 9 7 6 2 0 and 15 16 19 20 25 1 3 5 7

- AN on June 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.iterate over array to find the max by comparing arr[i] and arr[i+1] where arr[i] >arr[i+1]
2.if key is greater than arr[i] then search in upper index of array
3.else search in lower index

- suvrokroy on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity: O(n) :(

- ravigupta on May 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You realise that if I am iterating to find the maximum element, I might as well iterate and find the element to be searched. There is no difference in complexity.

- Shivku.goku on July 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.iterate over array to find the max by comparing arr[i] and arr[i+1] where arr[i] >arr[i+1]
2.if key is greater than arr[i] then search in upper index of array
3.else search in lower index

- suvrokroy on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

find out the critical point and then recursively search in both part

- dilip kasana on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what are you trying to do here ? I did not get ?

- sumit on June 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

find out the critical point and apply binary search

- dilip kasana on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Best solution with complexity O(log n) .

- ancs on May 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Best solution with complexity O(log n) .

- ancs on May 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Finding out maximum element complexity: O(logn)
Doing two binary searches on different parts of the array: O(log(n1))+O(log(n2))
Total complexity: O(log(n*n1*n2))
You might say that n1=k*n; n2=k1*n;
so Complexity : O(logn(n))

- Shivku.goku on July 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can reduce the complexity to O(logn) by finding our the highest number also by using binary search...

- Shubham on May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

two points at a time first and the last
step 1:if(arr[start+i]==k || arr[end-i]==k)
found k;
else
recurse(arr,start+i,end-i)

O(lgn)

- Anonymous on May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

two points at a time first and the last
for i 0 to len/2
step 1:if(arr[start+i]==k || arr[end-i]==k)
found k;
else
recurse(arr,start+i,end-i)

O(lgn)

- raj on May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getMaxFromRotatedSortedList(int [] array){
int start = 0;
int end = array.length -1;
while(start<=end){
int mid = (start+end)/2;
if(array[mid]>array[mid+1]&&array[mid]>array[mid-1])
return mid ;
if(array[mid]<array[mid+1]){
start = mid+1;
}else {
end = mid -1;
}
}
return -1 ;
}


public static int orderbinarySearch(int[]array, int start, int end,int key,boolean order){
while(start<end){
int mid =(start+end)/2;
if(array[mid]==key)
return mid;
if(order){
if(key<array[mid])
end = mid;
else
start = mid +1;
}else{
if(key>array[mid])
end = mid;
else
start = mid +1;
}}
return -1;
}


public static void main(String [] args){
int [] newArray ={1,2,3,4,5,6,7,8,43,100,107,111,120,89,78,67,56,34,23,10};
int maxElementIndex = getMaxFromRotatedSortedList(newArray);
System.out.println("max element is"+getMaxFromRotatedSortedList(newArray));
int c = orderbinarySearch(newArray,0,maxElementIndex,23,true);
boolean found = false;
if(c==-1){
c = orderbinarySearch(newArray,maxElementIndex,newArray.length-1,23,false);
if (c!=-1) found = true ;
}else{
found = true;
}
if(found){
System.out.println("the index of the key is"+c);
}else {
System.out.println("key is not present ");
}
}

- Anonymous on May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getMaxFromRotatedSortedList(int [] array){
int start = 0;
int end = array.length -1;
while(start<=end){
int mid = (start+end)/2;
if(array[mid]>array[mid+1]&&array[mid]>array[mid-1])
return mid ;
if(array[mid]<array[mid+1]){
start = mid+1;
}else {
end = mid -1;
}
}
return -1 ;
}


public static int orderbinarySearch(int[]array, int start, int end,int key,boolean order){
while(start<end){
int mid =(start+end)/2;
if(array[mid]==key)
return mid;
if(order){
if(key<array[mid])
end = mid;
else
start = mid +1;
}else{
if(key>array[mid])
end = mid;
else
start = mid +1;
}}
return -1;
}


public static void main(String [] args){
int [] newArray ={1,2,3,4,5,6,7,8,43,100,107,111,120,89,78,67,56,34,23,10};
int maxElementIndex = getMaxFromRotatedSortedList(newArray);
System.out.println("max element is"+getMaxFromRotatedSortedList(newArray));
int c = orderbinarySearch(newArray,0,maxElementIndex,23,true);
boolean found = false;
if(c==-1){
c = orderbinarySearch(newArray,maxElementIndex,newArray.length-1,23,false);
if (c!=-1) found = true ;
}else{
found = true;
}
if(found){
System.out.println("the index of the key is"+c);
}else {
System.out.println("key is not present ");
}
}

- vibhanshu jha on May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the problem complexity is o(log n)
the problem is divided into 2 parts.
1)finding maximum point
2)applying binary search on each side of maximum index.
to find maximum point:
divide the array into 3 parts using n/3 and 2n/3 as indexes.
if(a[n/3]<a[2n/3])
then maximum present in the a[n/3] to a[n];
else
the maximum present in a[1] to a[2n/3]
repeat the process
the complexity for this is o(log n) because the array size is decrimented each time by 1/3rd.
now apply binary search on both sides of maximum element...

- Anonymous on May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo to find the point of inflection, once you get it do binary search in individual parts of the array, time complexity is O(log(n))

def find_pos(arr,n,s,e):
    m=(s+e)/2
    if not (m-1>=0 and m+1<n): return -1
    if arr[m-1]<arr[m] and arr[m]>arr[m+1]: return m
    if arr[m-1]>arr[m] and arr[m]>arr[m+1]:
        return find_pos(arr,n,s,m)
    if arr[m-1]<arr[m] and arr[m]<arr[m+1]:
        return find_pos(arr,n,m+1,e)

- light on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo to find the point of inflection, once you get it do binary search in individual parts of the array, time complexity is O(log(n))

def find_pos(arr,n,s,e):
    m=(s+e)/2
    if not (m-1>=0 and m+1<n): return -1
    if arr[m-1]<arr[m] and arr[m]>arr[m+1]: return m
    if arr[m-1]>arr[m] and arr[m]>arr[m+1]:
        return find_pos(arr,n,s,m)
    if arr[m-1]<arr[m] and arr[m]<arr[m+1]:
        return find_pos(arr,n,m+1,e)

- light on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can be done in order of logn

first find point of inflection using a method similar to binary search
then call binary search on the left list differently and call binary search on the right list differently

- harmeet on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can be done in order of logn

first find point of inflection using a method similar to binary search
then call binary search on the left list differently and call binary search on the right list differently

- harmeet on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is a Bitonic Sequence.
Let Mid = (start + end)/2, divides the array in two halves.
In this case two cases could happen:
1. The Array is Exactly Increasing/Decreasing in first half and Exactly Decreasing/Increasing in the second half.
2. The Array is Decreasing/Increasing in one half and it is again Bitonic in the other half.

So basically we perform Binary search in the Monotonic sequence and perform Sequential search in the Bitonic sequence.

Best Case Order : O(log n/2)) + O(log (log n/2)) i.e., Binary search in both halves (Case 1)
Worst Case : O(log n/2) + O(n/2) (Case 2: Which again can be checked recursively and search can be minimized)

Now Major part is to check if the Half is Strictly Increasing or decreasing :

isFirstHalfIncreasing = A[start]< A[mid-1] && A[mid-1][mid]
isFirstHalfDecreasing = A[start] > A[mid-1] && A[mid-1] > A[mid]
isSecondHalfIncreasing = A[mid] < A[mid+1] && A[mid+1] < A[end]
isSecondHalfDecreasing = A[mid] > A[mid+1] && A[mid+1] > A[end]


Algorithm is:

Boolean Sequential_Search(A,start,end,element) {

if(start == end ) return A[start]==element;
mid = (start+end)/2;
if(A[mid == element]) return true;
return ( isFirstHalfIncreasing OR isFirstHalfDecreasing
? Binary_Search(A,start,mid-1,element)
|| Sequential_Search(A,start,mid-1,element) )
OR (isSecondHalfDecreasing || isSecongHalfIncreasing
? Binary_Search(A,mid+1,end,element)
|| Sequential_Search(A,mid+1,end,element))

} //End of Sequential Search..

Boolean Binary_Search(A,start,end,element) {
if(start == end ) return A[start]==element;
mid = (start+end)/2;
if(A[mid == element]) return true;
return Binary_Search(A,start,mid-1,element) || Binary_Search(A,mid+1,end,element)

} // End of Binary Search..




Please Correct me if I am wrong. Also please if some one could caluclate the average case, that would be great

- Wolverine on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the maximum elements in array - O(logn)

Now if element > max - Not found

Form two sorted array and do binary search.

Total time O(logn)+O(logx)+O(logn-x)~ OLog(n)

- nagen547 on May 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

it can be done in O(logn)

- loveCoding on June 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

it can be done in O(log n)

- loveCoding on June 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ArrayExample1 {

	int[] arr=new int[]{1,2,3,4,5,77,88,90,-56,-45,-23};
	
	public void showElements(){
		int no=0;
		for(int i=0, j=1;j<arr.length;i++,j++){
			if(arr[i]<=arr[j]){
				continue;
			}else{
				no=arr[i];
				break;
			}
		}
		System.out.println("No: "  + no);
	}
	
	public static void main(String[] a){
		ArrayExample1 a1=new ArrayExample1();
		a1.showElements();
	}

}

- Jeevan on June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Store the complete array in hashtable..with numbers. By using Contains value check if the given number exists..
Storing elements in hashtable takes o(n).and..hashtable lookup is o(1).

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

This is the kind of problem where O(n) isn't good enough though...plus why store numbers in a hashtable when you can just compare them with the target number directly?

- Sunny on December 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My idea is same as everyone else:
(1) Find the position of the maximum with modified binary search. Call this the "climax".
(2) Perform binary search from beginning to climax
(3) Perform binary search from climax to end

Each is O(logn) so altogether still O(logn). Note that I am also accommodating for the case when the climax is at the beginning or end of the array.

static int search(int[] arr, int n) {
	int climax = findMax(arr);
	int p = binarySearch(arr, n, 0, climax);
	if(p >= 0)
		return p;
	else return binarySearch(arr, n, climax, arr.length-1);
}

static int findMax(int[] arr) {
	int start = 0;
	int end = arr.length-1;
	while(start <= end) {
		int middle = (start+end)/2;
		boolean gtLeft = (middle == 0 || arr[middle] > arr[middle-1]);
		boolean gtRight = (middle == arr.length-1 || arr[middle] > arr[middle+1]);
		if(gtLeft && gtRight)
			return middle;
		if(gtLeft && !gtRight) {
			// ascending
			start = middle+1;
		} else {
			// descending
			end = middle-1;
		}
	}
	// shouldn't happen
	return -1;
}

static int binarySearch(int[] arr, int n, int start, int end) {
	boolean ascending = (start == 0);
	while(start<=end) {
		int middle = (start+end)/2;
		if(arr[middle] == n)
			return middle;
		if(ascending) {
			if(arr[middle] < n)
				start = middle+1;
			else end = middle-1;
		} else {
			if(arr[middle] < n)
				end = middle-1;
			else start = middle+1;
		}
	}
	return -1;
}

- Sunny on December 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hmm sorry I just realized that in my binarySearch, start = 0 doesn't guarantee that we are searching an ascending array, if the maximum element is at the beginning. But that's simple enough to fix by using an additional parameter instead.

- Sunny on December 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>
#include<stdlib.h>


int main()
{

int arr[] = {10,12,14,17,18,16,11,9,8};
int low = 0,
mid ,
high = lengthof(arr), // length of array
low1,
low2,
high1,
high2;

int k ;

int temp_low = low,
temp_high = high;

int find = 0;

printf("please enter the number to search \n");
scanf("%d",&k);

mid = (low + high)/2;

while( low < high)
{

mid = (low + high) /2;
if ((arr[mid -1] < arr[mid]) && (arr[mid] < arr[mid + 1]))
{
low = mid + 1;
}
else
{
if ((arr[mid -1] > arr[mid]) && (arr[mid] > arr[mid + 1]))
{

high = mid + 1;
}
else
{
if ((arr[mid -1 ] > arr[mid]) && (arr[mid] < arr[mid + 1]))
{
high1 = mid;
low1 = temp_low;

high2 = temp_high;//This is for descedning order
low2 = mid + 1;
break;
}
else
{
high2 = temp_high;
low2 = mid + 1;

high1 = mid;
low1 = temp_low;
break;
}

}

}

}

printf( "high1 = %d low1 = %d high2 = %d low2 = %d\n", high1,low1, high2, low2);

/* check the number in ascending part*/
while( (low1 <= high1) && (find == 0))
{

mid = (low1 + high1)/2;
if(arr[mid] == k)
{
find = 1;
break;
}
else if (arr[mid] > k)
{
high1 = mid - 1;
}
else if(arr[mid] < k)
{
low1 = mid + 1;
}
}


/* check the num in desc part*/
while ((low2 <= high2) && (find == 0))
{
mid = (low2 + high2) / 2;

if (arr[mid] == k)
{
find = 1;
break;
}
else if (arr[mid] > k)
{
low2 = mid + 1;
}
else if (arr[mid] < k)
{
high2 = mid - 1;
}
}


if (find != 0)
{
printf("find postion is : %d \n", mid);
}
else
{
printf("%d is not present in the array\n", k);
}

return(0);

}

- Damodar on May 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

How about this approach:

1. First find the highest element; If there are elements i,j such that a[i]>a[j], obviously 'i' marked the end of the first list. O(n);
2. Do a binary search on these elements. If it is found, return it. [O(logn)].
3. If it is not there, then search in the decreasing part; For this multiply the numbers 'i+1' till last element with -1 and also the key with -1; O(n)
4. Search using binary search for the key; O(log n);
5. If found, return else terminate with a message saying that the key is not found.
So, overall complexity is O(n) + O(log n ) + O(n) + O(log n ) ;
6. Final complexity, is O( n );

If you feel that I need to include anything here, do let me know.

thanks,
Pavan

- Pavan Dittakavi on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why not simply use linear search instead of the yours algo that would also be O(n) and much simpler....

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

@Anonymous right dear

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

public static int MaxElementPosition(int[] input, int search)
{
int start = 0, end = input.Length - 1;
int maxPosition = 0;
while (true)
{
int n = end - start + 1;

// only 2 elements
if (n <= 2)
{
if (input[end] > input[start])
{
maxPosition = end;
}
else
{
maxPosition = start;
}
break;
}

if (input[start + n / 3] <= input[start + 2 * n / 3])
{
start += n / 3;
end = start + n - 1;
}
else
{
end = start + 2 * n / 3 - 1;
}
}

return input[maxPosition];
}

- Working code with O(Log(n)) to find Max element Position on June 16, 2012 | Flag Reply


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