mystique
BAN USER
Employee at None
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
The previous code doesn't compile. Sorry about that. Here goes it again:
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;
}
}
}
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
How about doing a binary search? Let's assume the input is n. If n is a multiple of 5, then it can be written that n = 5*x. We set low = 1, high = n, and try to find x using a binary search. Note that since w can't use / operator, we need to use right shift for computing mid = (low + high) >> 1.
- mystique January 21, 2014