CareerCup

- Find an element i > 0, so that s[i] < s[i-1] (i.e. the first pair of adjacent elements of s where the second element is smaller than the previous one).
- Then sort the rest of the array ( s[i] to s[s.size() - 1] ) in descendant order.
- If you don't find that pair in the whole array, it means that s is already sorted in ascendant order. If "pointy" means that the array has to have a "descending part" at the end (k has to be less than s.size() - 1), you can just swap the last two elements of s (then k will be s.size()-2).

1 find the largest element
2 place it in the middle of the array.
3 sort nos before that no and after that no

Why? Just Sort the array in O(nlogn). An ascending array is still Pointy as the question described.

1.build a max heap from the elements.This can be done in O(n)
2.modify the original array by overriding elements from the middle toward both directions

you will get mononically decreasing series around the max seating in the middle

1. sort in O(n log n)
2. i=A[mid] and j=A[n-1]
3. while i<j swap A[i] with A[j]

It appears to be a modified binary search question. I am assuming the question is to find the maximum element.
Solution would be to perform binary search with a modified condition to check the element adjacent to the middle element. The base cases get a little tricky.

/*
	 * Given a bitonic array in which there is an increasing
	 * sequence of ints followed by a decreasing sequence. We 
	 * are to find the largest value in such an array. The solution
	 * has O(log n) Time Complexity & O(1) Space Complexity.
	 */
	public int getMaxValueInBitonicArray(int[] a)
	{
		if(a==null)
			return Integer.MIN_VALUE;//returns negative infinity
		
		int l=0;
		int r=a.length-1;
		int m;
		
		while(l<=r)
		{
			m=(r-l)/2+l;
			
			/*
			 * This condition is super tricky, all base cases must be covered.
			 */
			if((m==0 && a[m]>a[m+1]) || (m==a.length-1 && a[m-1]<a[m]) || (a[m]>a[m-1] && a[m]>a[m+1]))
			  return a[m];
			
			if(a[m]<a[m+1])
				l=m+1;
			else
				r=m-1;
		}
		
		return Integer.MIN_VALUE;
	}

def pointyfier(a):

        a.sort()
        length = len(a)
        point = a[length - 1]
   
        a[length//2], point = point, a[length//2]
   
        a[length//2 + 1:].sort(-1)

Can somebody give a solution in O(n)? Which means sorting is not allowed.

package com.shashi.careercup;

public class Pointy {

public boolean isPointy(int array[])
{
boolean isdecreasing=false;
int current=array[0];
boolean finalres=false;
int index=0;
for(int i=1;i<array.length;i++)
{
if(current<=array[i])
{
current=array[i];
}
else
{
index=i-1;
isdecreasing=true;
// System.out.print(index);
}
if(isdecreasing)
{
finalres=passing(index,array);

break;
}

}
return finalres;
}
public boolean passing(int index,int array1[])
{
boolean res=false;
//System.out.print("Array langth is"+array1.length);
for(int i=index+1,j=1;i<array1.length;i++,j++)
{

if(array1[index-j]!=array1[i])
{

break;
}
//if there is
if(i == array1.length-1)
res=true;
}
return res;
}

//main method
public static void main(String args[])
{
Pointy p=new Pointy();
int ar[]={1,2,3,2,1};
System.out.print(p.isPointy(ar));
}
}

1) sort the array
2) rotate array to the right one or more times

The idea is to find the smallest element and place it in begining. Then the next smallest element at the end of array. Repeat these steps for all elements in input.

void monotonicSort(int[] ip)
        {
            int l = 0, r, len = ip.Length;
            r = len-1;

            for (int i = 0; i < len; i++)
            {
                int min = ip[l];
                int index = l;
                for (int j = l; j <= r; j++)
                {
                    if (ip[j] < ip[index])
                    {
                        index = j;
                    }
                }

                if (i % 2 == 0)
                {
                    Swap(ref ip[l], ref ip[index]);
                    l++;
                }
                else
                {
                    Swap(ref ip[r], ref ip[index]);
                    r--;
                }
            }
        }

        private static void Swap(ref int p1, ref int p2)
        {
            int temp = p1;
            p1 = p2;
            p2 = temp;
        }

public static void main(String args[])
	{
		int array[]={1,2,3,5,3,6,1};
		
		int low=0;
		int high=array.length-1;
		int mid=(low+high)/2;
		int maxpos=-1;
		int max=-1;
		for(int i=0;i<array.length;i++)
		{
			if(array[i]>max)
			{
				max=array[i];
				maxpos=i;
			}
		}
		
		if(array[mid]!=max)
		{
			int temp=array[mid];
			array[mid]=array[maxpos];
			array[maxpos]=temp;
		}
		if(array[mid]==max)
		{
			//chek for leftside as increasing
			while(low<mid)
			{
				if((low+1)<=mid && array[low]<array[low+1])
					
				{	
					low++;
				}
				else
				{
					int tmp=array[low];
					array[low]=array[low+1];
					array[low+1]=tmp;
				}
				
			}
			while((mid)<high)
			{
				if((mid+1)<=high && array[mid]>array[mid+1])
				{
					mid++;
				}
				else if(mid+1<=high)
				{
					int tmp=array[mid];
					array[mid]=array[mid+1];
					array[mid+1]=tmp;
				}
			}
			//check for rightside as decreasing
		}
			
		
		for(int i:array)
		{
			System.out.print(i+" ");
		}
		
	}

Time Complexity: O(n)