Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
@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.
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)
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
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
This can be solved like binary search, you can watch complete solution given in this wonderful video
youtu.be/Cwh_-O1dsDQ
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?
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;
}
}
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 ");
}
}
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 ");
}
}
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...
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)
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)
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
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();
}
}
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).
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;
}
#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);
}
#include<bits/stdc++.h>
using namespace std;
int bin(int a[],int low,int high)
{
int mid=(low+high)/2;
if(a[mid]>a[mid-1]&&a[mid]>a[mid+1])
{
return mid;
}
if(a[mid]>a[mid-1]&&a[mid]<a[mid+1])
{
bin(a,mid+1,high);
}
else
{
if(a[mid]<a[mid-1]&&a[mid]>a[mid+1])
{
bin(a,low,mid);
}
}
}
int bin1(int a[],int low,int high,int x)
{
int mid=(low+high)/2;
if(low<=high)
{
if(a[mid]==x)
return mid;
if(a[mid]>x)
return bin1(a,low,mid-1,x);
return bin1(a,mid+1,high,x);
}
return -1;
}
int bin2(int a[],int low,int high,int x)
{
int mid=(low+high)/2;
if(low<=high)
{
if(a[mid]==x)
return mid;
if(a[mid]<x)
return bin2(a,low,mid-1,x);
return bin2(a,mid+1,high,x);
}
return -1;
}
int main()
{
int i,j,k,m,n=15,x,min1;
int a[]={1,3,5,7,19,221,132,56,8,6,4,2,1,-3,-17};
cin>>x;
int max1=bin(a,0,14);
//cout<<max1<<endl;
k=max1;
if(a[0]>a[n-1])
{
min1=n-1;
}
else
{
min1=0;
}
//cout<<min1;
int res=bin1(a,0,max1,x);
if(res!=-1)
{
cout<<res<<endl;
}
else
{
int res1=bin2(a,k+1,n-1,x);
cout<<res1<<endl;
}
}
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
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];
}
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
why not simply use linear search instead of the yours algo that would also be O(n) and much simpler....
#include<bits/stdc++.h>
using namespace std;
int bin(int a[],int low,int high)
{
int mid=(low+high)/2;
if(a[mid]>a[mid-1]&&a[mid]>a[mid+1])
{
return mid;
}
if(a[mid]>a[mid-1]&&a[mid]<a[mid+1])
{
bin(a,mid+1,high);
}
else
{
if(a[mid]<a[mid-1]&&a[mid]>a[mid+1])
{
bin(a,low,mid);
}
}
}
int bin1(int a[],int low,int high,int x)
{
int mid=(low+high)/2;
if(low<=high)
{
if(a[mid]==x)
return mid;
if(a[mid]>x)
return bin1(a,low,mid-1,x);
return bin1(a,mid+1,high,x);
}
return -1;
}
int bin2(int a[],int low,int high,int x)
{
int mid=(low+high)/2;
if(low<=high)
{
if(a[mid]==x)
return mid;
if(a[mid]<x)
return bin2(a,low,mid-1,x);
return bin2(a,mid+1,high,x);
}
return -1;
}
int main()
{
int i,j,k,m,n=15,x,min1;
int a[]={1,3,5,7,19,221,132,56,8,6,4,2,1,-3,-17};
cin>>x;
int max1=bin(a,0,14);
//cout<<max1<<endl;
k=max1;
if(a[0]>a[n-1])
{
min1=n-1;
}
else
{
min1=0;
}
//cout<<min1;
int res=bin1(a,0,max1,x);
if(res!=-1)
{
cout<<res<<endl;
}
else
{
int res1=bin2(a,k+1,n-1,x);
cout<<res1<<endl;
}
}
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
- rajeshp May 12, 2012int 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); }