CareerCup

Here is one good solution using modified binary search,

puddleofriddles.blogspot.com/2011/12/given-array-of-unsigned-integers-which.html

will do a linear scan and return i as index for max number such that the following condition is satisfied.

a[i-1]<=a[i]>=a[i+1]

@VArora.mnnit: how was the interview? Did you get the offer?

we can modify the binary search

int find(int a[],int n)
{
 int low=0,up=n;
 int mid;
 while(low<=up)
 {
   mid=(up+low)/2;
   if(a[mid]>a[mid-1]&&a[mid]>a[mid+1])
      return a[mid];
   else if(a[mid]>a[mid-1]&&a[mid]<a[mid+1])
   low=mid+1;
   else if(a[mid]<a[mid-1]&&a[mid]>a[mid+1])
   up=mid-1;

 }
 
}

public static  int MaxValue(int[] arr, int L, int H)
        {
            if (L == H)
                return arr[L];

            int M = (L + H) / 2;
            if (M + 1 < arr.Length)
            {
                if (arr[M] > arr[M + 1])
                {
                  return MaxValue(arr, L, M);
                }
                else
                {
                  return  MaxValue(arr, M + 1, H);
                }
            }
            else
            {
               return MaxValue(arr, L, M);
            }

        }

can be solved in log n using modified binary search..

we can have repetitions in the array since it is increasing and decreasing not monotonically increasing and decreasing

Is the array increasing till half of the array or it could be till n-1? How it is? From the question it is not clear..

any segment (increasing or decreasing or both ) can be null

This problem can be solved with ternary search.
let l = 0, r = n-1;
delta = (r - l) / 3;
e1 = l + delta, e2 = e1 + delta;
if (a[e1] < a[e2]) l = e1;
else r = e2;