Amazon Interview Question Software Engineer / Developers

• 0

Q2. F2F Round-1, Amazon(Bangalore)

Given an array of integers having the property that first that array is strictly increasing then it is strictly decreasing, You have to search for a given number.

Constraint: Minimize the complexity

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);

}``````

Comment hidden because of low score. Click to expand.
0

This is pretty much what i thought.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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;
}
}``````

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

Find the maximum elements in array - O(logn)

Form two sorted array and do binary search.

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

Comment hidden because of low score. Click to expand.
0
of 2 vote

This question is same as searching in a rotated sorted array

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

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

Complexity: O(n) :(

Comment hidden because of low score. Click to expand.
0

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.

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 2 vote

find out the critical point and apply binary search

Comment hidden because of low score. Click to expand.
0

Best solution with complexity O(log n) .

Comment hidden because of low score. Click to expand.
0

Best solution with complexity O(log n) .

Comment hidden because of low score. Click to expand.
0

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))

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...

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)

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)

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 ");
}
}

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 ");
}
}

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...

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)``````

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)``````

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

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

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

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

Find the maximum elements in array - O(logn)

Form two sorted array and do binary search.

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

Comment hidden because of low score. Click to expand.
0
of 2 vote

it can be done in O(logn)

Comment hidden because of low score. Click to expand.
0
of 2 vote

it can be done in O(log n)

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();
}

}``````

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).

Comment hidden because of low score. Click to expand.
0

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?

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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

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);

}

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@Anonymous right dear

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];
}

Name:

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

Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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.