## Interview Question

• 0
of 0 votes

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

- 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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

We need a strictly monotonically increasing from left, not non decreasing. So using your solution we can get duplicates and it will not be a monotonically increasing.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

max heap is another O(nlogn) solution

Comment hidden because of low score. Click to expand.
0
of 0 votes

Max heap also works, but it will use O(n) space, unfortunately.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

So it's still O(nlogn) for the problem, right?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.shashi.careercup;

public class Pointy {

public boolean isPointy(int array[])
{
boolean isdecreasing=false;
int current=array;
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));
}
}

Comment hidden because of low score. Click to expand.
0
of 0 votes

shashikumarvrce.blogspot.com

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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)

Comment hidden because of low score. Click to expand.
0
of 0 votes

Try:[ 4 2 1 7 3 5 6 ]

Comment hidden because of low score. Click to expand.
0
of 0 votes

``````//chek for leftside as increasing
while(low<mid)
{
if((low-1)>=0 && array[low-1]>array[low])
{
low=low-1;
}
if((low+1)<=mid && array[low]<array[low+1])

{
low++;
}

else
{
int tmp=array[low];
array[low]=array[low+1];
array[low+1]=tmp;
}

}``````

Hope this will solve the problem.

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More