Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
will do a linear scan and return i as index for max number such that the following condition is satisfied.
a[i-1]<=a[i]>=a[i+1]
yes, on every middle element , we will check the above condition is true or not.
int BinarySearch(int a[], int l, int h){
int m=(l+h)/2;
if(m-1 >=l && m+1<=h){
if(a[m-1]<a[m]<a[m+1])
return a[m];
else if(a[m-1]>a[m]>a[m+1])
return BinarySearch(a,l,m);
else
return BinarySearch(a,m,h);
}
}
@Ashish
Your algorithm will fail in case of repeated integers.
For Example: 1 2 2 3 3 4 4 4 3 3 2 1 1
we can modify the binary search
int find(int a[],int n)
{
int low=0,up=n;
int mid;
while(low<=up)
{
mid=(up+low)/2;
if(a[mid]>a[mid-1]&&a[mid]>a[mid+1])
return a[mid];
else if(a[mid]>a[mid-1]&&a[mid]<a[mid+1])
low=mid+1;
else if(a[mid]<a[mid-1]&&a[mid]>a[mid+1])
up=mid-1;
}
}
Here is one good solution using modified binary search,
- Anonymous January 13, 2012puddleofriddles.blogspot.com/2011/12/given-array-of-unsigned-integers-which.html