Yahoo Interview Question
Software Engineer / Developersstart with finding the max and min of the array and check if min is at beginning or max is at the end .if either of them occurs to be true then accordingly change the start and end of array.recurse it until the max and min within the array boundaries(start and end) dont happen to be at the either extremities.at that point sort the array in length start and end.
The below algo assumes the size of array is even. With few modifications to the below code, it can be supported when array of size is odd. N is the size of array.
public ret[] returnIndices(int[] a, int size) {
int n1=0, n2 = size - 1;
for(;n1<n2;n1++,n2--) {
if(a[n1] > a[n2]) break;
if(a[n1] < a[n1-1]) { n1--; break; }
if(a[n2] > a[n2+1]) { n2++; break; }
}
ret[0] = n1;
ret[1] = n2;
return ret;
}
I took the below example & it works fine : a = {1,2,6,4,5,7,8,9}
The below algo assumes the size of array is even. With few modifications to the below code, it can be supported when array of size is odd. N is the size of array.
public ret[] returnIndices(int[] a, int size) {
int n1=0, n2 = size - 1;
for(;n1<n2;n1++,n2--) {
if(a[n1] > a[n2]) break;
if(a[n1] < a[n1-1]) { n1--; break; }
if(a[n2] > a[n2+1]) { n2++; break; }
}
ret[0] = n1;
ret[1] = n2;
return ret;
}
It works fine for this array : a = {1,2,6,4,5,7,8,9}
do you mean find the two indices?
- Anonymous September 12, 2010