## Interview Question

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
3
of 7 vote

Step 1:
Scan the array from index 0 -> (N - 1) and keep track of the maximum value seen up to each index. Let's call it (max_value_seen) and it is initialized to the smallest value. At index i, if A[i] >= max_value_seen, then do two things:
1- max_value_seen = A[i]
2- potential_q[i] = true.
Where "potential_q" is an array of length N of booleans initialized to all false. When you say potential_q[i] = true, it means that index "i" is a potential candidate for "q" since it satisfies the first constaint, i.e., for all k < i, A[i] >= A[k].

Step 2:
Scan the array in reverse order and do the opposite, i.e., keep track of min value. Let say the min value is stored in "min_value_seen". At index j, do the following

``````if (A[i] <= min_value_seen) {
min_value_seen = A[i];
if (potential_q[i] == true)
return i;
}``````

If A[i] < min_value_seen, then for any j > i, A[j] \ge A[i]. Then if A[i] is a potential Q from previous section, we know that A[i] \ge A[k] for all k < i. As a result, Q = i is a solution.

Full code:

``````public class FindSubIndex {
public FindSubIndex(int[] A) {
this.A = A;

}
public int GetQ() {
boolean[] pot_q = new boolean[A.length];
pot_q[0] = true;
int max_value_seen = min_val;
for (int i = 0; i < A.length; i++) {
if (A[i] > max_value_seen) {
pot_q[i] = true;
max_value_seen = A[i];
}
}
// if for some i, pot_q[i] = false, then Q cannot be i.
int min_value_seen = max_val;
if (pot_q[pot_q.length - 1])
return A.length - 1;
for (int i = 0; i < A.length; i++) {
int rev_index = A.length - i - 1;
if (A[rev_index] < min_value_seen) {
min_value_seen = A[rev_index];
if (pot_q[rev_index])
return rev_index;
}
}
return -1;
}
private int[]       A;
private int min_val = -(int) Math.pow(2, 32);
private int max_val = (int) Math.pow(2, 32);
}

class Program {
public static void Main(String arg[]) {
int[] A = new int[]{....}.
int Q = (new FindSubIndex(A)).GetQ();
System.out.print(Q);
}``````

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

perfect solution!

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

Stop upvoting yourself Ehsan (aka tikatel.main).

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

``````def findPivot(input):
pivot = -1
max = None
for i in xrange(len(input)):
if i == 0:
pivot = 0
elif input[i] < input[pivot] and pivot != -1:
pivot = -1
elif input[i] > max and pivot == -1:
pivot = i

if max == None:
max = input[i]
elif input[i] > max:
max = input[i]

return pivot

Memory O(2)
Time O(n)``````

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

Wow nice. Short, sweet and very elegant. This is the best solution. It blows the memory requirement right out of the water.

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

Yes, Nice one!

In plain english (if I understood correctly): This finds the leftmost pivot if a pivot exists.

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

But, with O(N) space usage, we can find _all_ pivots.

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

I have a solution here: (not converted to code yet, but it should be simple)

All you need to do is fill 2 arrays, both of which having length n (lenght of the input array). One recording the greatest value seen so far, and the other recording the smallest value after that position, which is easier if we start the scan from the very end of the array.

For example,
input: [ 2, 3, 1, 4, 5, 6, 5 ]
1st array: [ 2, 3, 3, 4, 5, 6, 6 ] // start the scan at the beginning and keep track of max
2nd array: [ 1, 1, 1, 4, 5, 5, 5 ] // start the scan at the end and keep track of min

After we have these 2 array, we look for matching elements, which is 4 & 5 at index 3 & 4 respectively. These two are the possible index for choosing a pivot.

If no matches can be found, return -1:

input: [ 3, 2, 1 ]
1st: [ 3, 3, 3]
2nd: [ 1, 1, 1]
=> no match

This solution is correct because of the fact that, everything on the LHS of the pivot point is smaller than or equal to the pivot value, that is to say, the maximum value on the LHS of the pivot point is equal to the pivot value. Vice versa for minimum value on the RHS.

Hope this helps.

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

This does not work,, try with 1 5 7 4 3,, This will give you 1 according your logic

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

``````#import <stdio.h>

int solution(int A[], int N)
{
int minind, maxind;
int max = -2147483647, min = 2147483647;

for (int i = 0; i < N; i++) {
if (A[i] > max) {
max = A[i];
maxind = i;
}
if (A[i] < min) {
min = A[i];
minind = i;
}
}

if (maxind < minind)
return -1;

max = -2147483647; min = 2147483647;

for (int i = 0; i <= minind; i++) {
if (A[i] > max)
max = A[i];
}

for (int i = minind+1; i < N; i++) {
if (A[i] < min)
min = A[i];
}

if (max > min)
return -1;

int q = minind;

for (int i = minind; i <= maxind; i++) {
if (A[i] < max)
q = i+1;
}

return q;
}

int main(int args, char **argv)
{
int A[] = {4,2,2,1,4,6,7,8,9};

printf("%d\n", solution(A, 9));
}``````

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

What are you doing? Explain in english?

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

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

Not sure why we need to deal with 'expected' time. Algorithm is deterministic O( N ) time and space.

``````int pivot(int n, int* A)
{
int pivot = -1;
int* smaller = new int[n];
int* greater = new int[n];

greater[0] = A[0];
for(int i=1; i < n; i++)
greater[i] = (A[i] > greater[i-1]? A[i]: greater[i-1]);

smaller[n-1] = A[n-1];
for(int i=n-2; i >= 0; i--)
smaller[i] = (A[i] < smaller[i+1]? A[i]: smaller[i+1]);

for(int i = 0; pivot == -1 && i < n; i++)
if(greater[i]<=A[i] && smaller[i]>=A[i])
pivot = i;

delete [] smaller;
delete [] greater;

return pivot;
}``````

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

expected = expected by the programming contest from which this problem was taken.

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.