## Adobe Interview Question for MTSs

Country: India
Interview Type: In-Person

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

PIVOT IS THE ELEMENT WHICH IS LESSER THEN IN LEFT ELEMENT AND RIGHT ELEMENT AS WELL.. so we need to use that...and recurse..where as problem will be divided in three parts when we have one element left then it is the pivot and when we are left with 2 elements then minimum of that...and when of more then three then we need to check the above stated condition and accordingly move to left or right part

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

use binary search O(logn)

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

I don't think normal Binary search will work in this case either you have to modify it or you cannot use binary search(simple one).

Can you explain your methodology ??

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

I confess I had to go look up what a rotated array was, but I'm not sure what you mean by the pivot. Is it the "first" element in the sort? If so, it seems like all you'd need to do is iterate through each element in the array, comparing it to the previous element (or the last element in the array when checking the first element) until you found the one element that had a lower sort value than its predecessor.

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

Wait, scratch that. Compare the first element with an element halfway down the length of the array. That'll tell you which half of the array the pivot is in. Pick an element halfway through that subsection and compare that against the first two elements. Continue dividing down until the pivot is located.

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

First look says it will not work.

Explain a more with some example.

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

Pivot is first element of array

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

Well in a sorted array any element can be a pivot. But when we rotate an array then the pivot becomes the element which breaks the sorting. This element can be found out by finding the element for which all the elements on the right and left are sorted.

For eg a sorted array would be 1,3,4,5,11,16,18,20. When we rotate it the new array might be 18,20,1,3,4,5,11,16.
Here 20 or 1 can be called as pivot as they break the sorting. The arrays to their left and right are sorted trivially or otherwise.

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

``````void main() {

int a,n,i;
scanf("%d",&n);
for (i = 0; i<n; i++)
scanf("%d",&a[i]);
int last = a[n-1];//last element
for(i = 0; a[i]>=last;i++);

printf("\n%d %d",i,a[i]);``````

}

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

The following code will work only when all the elements are unique (It works otherwise too but it'll break in certain conditions). The following code also assumes that the sorted array has been rotated i.e. there exists a pivot.

``````#include <iostream>
using namespace std;

int getPivot( int* arr, int N ) {
if ( NULL == arr ) {
return -1;
}

int low = 0;
int high = N - 1;
int mid;
int last = arr[N - 1];

while ( low <= high ) {
mid = ( low + high ) / 2;
cout << "Mid: " << mid << endl;
if ( arr[mid] < last ) {
high = mid - 1;
} else {
if ( mid < N - 1 && arr[mid] > arr[mid + 1] ) {
return mid;
}
low = mid + 1;
}
}

return mid;
}

void display( int *arr, int N ) {
if ( NULL == arr ) {
return;
}

for ( int i = 0; i < N; i++ ) {
cout << arr[i] << ' ';
}
cout << endl;
}

void rotateByOne( int *arr, int N ) {
if ( arr == NULL ) {
return;
}

int last = arr[N - 1];
for ( int i = N-1; i > 0; i-- ) {
arr[i] = arr[i - 1];
}

arr = last;
}

int main() {
int arr[] = { 1, 2, 3, 4, 5, 6, 7  };
int N = 7;

int pivot;
for ( int i = 0; i <= N; i++ ) {
cout << "=====================================" << endl;
display( arr, N );
pivot = getPivot( arr, N );
cout << "Pivot: " << pivot << endl;
rotateByOne( arr, N );
}

return 0;
}``````

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

pivot element will always be smaller then its left and right elemnets.so if middle element is smaller then the 1st element of the subarray, traverse left, else if midle element is greater then the first, traverse right.also when only one element left, thats the pivot

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

public static void FindPivotInrotatedSortedArray(int[] a)
{
if (a.Length == 0)
return;
if (a.Length == 1)
{
Console.WriteLine("Pivot is: {0}", a);
return;
}
for (int i = 0; i < a.Length; i++)
{
if (i == 0)
{
if (a[i] < a[i + 1] && a[i] < a[a.Length - 1])
{
Console.WriteLine("Pivot is: {0}", a[i]);
break;
}
}
else if (i == a.Length - 1)
{
if (a[i] < a && a[i] < a[i - 1])
{
Console.WriteLine("Pivot is: {0}", a[i]);
break;
}
}
else
{
if (a[i] < a[i + 1] && a[i] < a[i - 1])
{
Console.WriteLine("Pivot is: {0}", a[i]);
break;
}
}
}
return;

}

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.

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