|
There is an array of size 'n' in which first 'a' elements ....
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
There is an array of size 'n' in which first 'a' elements ....
Question:
There is an array of size 'n' in which first 'a' elements are sorted in either ascending/descending order . The remaining elements 'n-a' elements are again sorted in ascending/descending. Find the index of the point of inflexion.If both parts are sorted in the same way return -1.
maybe an answer1:
int findInflex(int a[], int n)
{
int lo = 0;
int hi = n-1;
bool firstHalfIncreasing = (a[1] - a[0])>0 ? true: false ;
bool secondHalfIncreasing = (a[n-1] - a[n-2]) > 0? true: false;
while(1)
{
int mid = (lo + hi)/2;
if( (a[mid-1] - a[mid]) * (a[mid] - a[mid+1]) < 0)
return mid;
else
{
if(lo == hi) //we are stuck
return -1;
if(firstHalfIncreasing && !secondHalfIncreasing && (a[mid] - a[mid-1] )>0 ||
!firstHalfIncreasing && secondHalfIncreasing && (a[mid] - a[mid-1]) <0 ) //this is first half
lo = mid;
else
hi = mid;
}
}
}
(Continued on next question...)
Other Interview Questions
| 