Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
The above code fails if number elements in increasing order is not equal to the number of of elements in decreasing order. The problem is not explicitly saying that till the mid of the array elements are in increasing order and after that in decreasing order.
The correct way to find would be to traverse the array the till the point a[i]<a[i+1]. As that point arrives, a comparison should be made between a[j] and a[j+1] whichever is bigger is the answer
public class SearchMaxHiLoArray {
private int splitIndex(int start, int end){
return start + (end-start)/2;
}
public int max(int[] array){
return max(array, 0, array.length);
}
private int max(int[] array, int start, int end){
int split = splitIndex(start, end);
if(split==(array.length-1) || split==0) return array[split];
if(1 == (end-start)) return array[end];
if(array[split] < array[split+1]){
return max(array, split, end);
} else if(array[split] > array[split+1]){
return max(array, start, split);
}
return array[split];
}
}
#include<stdio.h>
#include<stdlib.h>
int max(int a[],int i,int j)
{
if(i<j)
{
int mid=(i+j)/2;
if(j-i ==1 ) /* only two element*/
return (a[i]>a[j] ? a[i]:a[j]);
if(mid-1 >= i && mid+1 <=j) /* at least 3 element*/
{
if(a[mid]>=a[mid-1] && a[mid+1] <= a[mid])
return a[mid];
else if(a[mid] >a[mid+1])
return max(a,i,mid);
else
return max(a,mid,j);
}
}
return -1;
}
int main()
{
int a[]={1,3,6,8,77,89,78,67,56,45,34,23,12,9,8,7,6,5,4,3,2,1};
printf("%d",max(a,0,21));
return 0;
}
#include <iostream>
using namespace std;
int max(int a[], int n)
{
int i, flag =0;
if(n == 1)
return a[0];
for(i=0; i<n-1; i++)
{
if(a[i] > a[i+1])
{
flag =1;
return a[i];
}
}
if(!flag)
return a[n-1];
}
int main()
{
int arr[] = {1,3,6,8,77,99,99,78,67,56,45,34,23,12,9,8,7,6,5,4,3,2,1};
int a[] = {1,3,6,8,77,89};
cout<<"Maximum Element in 1st Array is "<<max(arr, 23)<<endl;
cout<<"Maximum Element in 2nd Array is "<<max(a, 6);
getchar();
return 0;
}
/*
The logic behind this program is that -- Once you encounter an element that is greater than its next
element then you found the max element (as was given in the question that is in decresing order from there)
Please let me know if I misunderstood anything
*/
int max(int *a,int start,int end))
- Ali_BABA January 22, 2012{
int mid=(start+end)/2;
if(a[mid-1]<a[mid] && a[mid]<a[mid+1])//mid falls in increasing series
return(max(a,mid+1,end));//search in next half
elseif((a[mid-1]>a[mid] && a[mid]>a[mid+1])//mid falls in decreasing series
return(max(a,start,mid-1));//search in previoushalf
else return a[mid];
}