CareerCup

so if you have 5 4 3 2 1 of size 5, that will also return -1?

How about a binary search?

bool findInflex(int a[], int n)
{
	int lo = 0;
	int hi = n-1;
	bool firstHalfIncreasing = (a[1] - a[0])>0 ?
	bool secondHalfIncreasing = (a[n-1] - a[n-2]) > 0?

	while(1)
	{
		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;
		}
	}
}

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;
		}
	}
}

The simplest way is tree.
Step1. Create a tree of sequence if it's a left/right skew tree then the list is either in ascending/descending order.
Step2. Then by height balancing tree algo (AVL/RBTree) we can find the index.

simple solution in time O(n) space O(1) - by comparing elements...
idea is, first 2 elements will always decide direction and then onwards comparison can be used to find change....

public static int findInflexion(int[] d) {
		int i=1;
		boolean fwd=true;
		
		if( d.length < 3 ) return -1;
		if(d[1]< d[0]) fwd=false;
		
		if(fwd) {
			for(int j=2;j<d.length;j++) {			
				if(d[j]>=d[j-1])
					i=j; // still increasing
				else {
					if(d[j+1]>=d[j])return -1;
					else return i;
				}
			}
		}
		else {
			for(int j=2;j<d.length;j++) {			
				if(d[j]<=d[j-1])
					i=j; // still increasing
				else {
					if(d[j+1]<=d[j])return -1;
					else return i;
				}
			}
		}
		return i;
	}

int a[] = new int[]{1,1,2,3,4,2,1,1,1};
		Boolean increasing = null;
		int last = a[0];
		for (int i = 1; i < a.length; i++) {
			if (increasing == null) {
				if (a[i] > last)
					increasing = true;
				else if (a[i] < last)
					increasing = false;
				last = a[i];
				continue;
			}
			if ((increasing && a[i] < last) || (!increasing && a[i] > last)) {
				System.out.println(i + " " + a[i]);
				return;
			}
			last = a[i];
		}
		System.out.println("-1");

Get the difference between two elements. Decreasing is - while increasing is +. Then check the changing point.
for example 94512678, we get 1459 8762. Then we have +++ ----, therefore, the inflexion point is 4.

chenming831 i could not get ur example. can u elaborate it a bit

int[] a = { 1, 1, 2, 3, 4, 2, 1, 1, 1 };
int FindArrayInflexionIndex(int[] a)
{

for (int i = 1; i < a.Length - 1; i++)
{
if ((a[i] > a[i + 1]) != (a[0] > a[1]))
return i;
}

return -1;
}

int FindInflectionPoint(int[] a)
{            
  if (a.Length > 1)
  {
    for (int i = 1; i < a.Length - 1; i++)
    {
      if ( ((a[i] - a[i - 1]) * (a[i + 1] - a[i])) < 0)
        return i;
    }
  }

  return -1;
}

I think you mean peak or trough. "Inflection point" means something completely different.

what is the inflexion point for 9 8 7 6 5 6 7 8 ?

For the above, as I understand inflexion point is at index 5.
static int findflip(int[] a)
{
bool? Firstinc = null;

for (int i = 0; i < a.Length - 1; i++)
{
if (a[i] < a[i + 1])
{
if (Firstinc == false) return i+1;
Firstinc = true;
}
else if (a[i] > a[i + 1])
{
if (Firstinc == true) return i+1;
Firstinc = false;
}
}
return -1;
}

int inflexion(int a[], int n)
{
if(n<3)
return -1;
int i, diff = 0, old_diff=0;
old_diff = a[1] - a[0];
for(i=1; i<n-1;i++)
{
diff = a[i+1] - a[i];
if(diff>0 && old_diff<0 || diff<0 && old_diff >0)
return i;
else
old_diff = diff;
}
return -1;
}

This is an easy one which can be done in O(n) time and O(1) space ...
Suppose the array a is 9 8 7 6 5 7 8 9
maintain a pointer j to the beginning of the array
keep incrementing j until j+2 reaches the end of the array .
when ever signs of a[j]-a[j+1] and a[j+1]-a[j+2] is different then j+1 is the point of inflexion .
so in this case 5 is the point of inflexion as
signs of 6-5 and 5-7 are different ....

int Findinflexion(int inp[], int len)
{
int check = 0;
inp[1] - inp[0] >= 0?check = 1:check = -1;

int prev = inp[0];
int index = -1;
for(int i=1;i<len;i++)
{
int tempcheck = 0;
inp[i]-prev > 0?tempcheck = 1:tempcheck = -1;

if(tempcheck != check)
{
index = i;
break;
}
prev = inp[i];
}

return index;
}