## Microsoft Interview Question

**Country:**United States

```
public class Main {
public static void main(String[] args) {
Integer[] numbers = new Integer[]{5, -1, 3, 8, 6,-1,2,8,9,15};
int lastMaxElement = 0;
int currentMaxElement = 0;
int lastIndex = 0;
for (int i = 0; i < numbers.length; i++) {
int value = numbers[i];
if (value <= lastMaxElement) {
lastMaxElement = currentMaxElement;
lastIndex = i;
} else {
if(value > currentMaxElement) {
currentMaxElement = value;
}
}
}
System.out.println(lastIndex);
}
```

}

void partition(int[] input) {

if (input.length == 0) System.out.println("Input is empty";

List<Integer> low = new ArrayList<Integer>();

List<Integer> high = new ArrayList<Integer>();

int mid = input[input.length/2];

for (int i = 0; i<input.length; i++) {

if (input[i]>mid) {

high.add(input[i]);

} else {

low.add(input[i]);

}

}

for (Integer value:low) {

}

System.out.println(""

}

void partition(int[] input) {

if (input.length == 0) {

System.out.println("Input array is empty");

}

List<Integer> low = new ArrayList<Integer>();

List<Integer> high = new ArrayList<Integer>();

//Take the median value as key to partition

int mid = input[input.length/2];

for (int i = 0; i<input.length; i++ ) {

if (input[i]>mid) high.add(input[i]);

else low.add(input[i]);

}

System.out.println("Low partition: " + low);

System.out.println("Low partition: " + high);

}

It is unclear which index we're looking for here.

- Alex July 16, 2020For example: [1,2,3] can be divided into [1], [2,3] or into [1,2], [3]. Both being correct.

So let's presume we want to find all indexes.

We are limited in run time to O(n), so we can't do anything elaborate like sort it, or use trees.

So it sounds like a simple array traversal is needed.

But we're not limited in space - so let's use that!

We'll build 2 additional arrays:

MaxToThisPoint and MinFromThisPoint

The first one will hold the max value we encountered up to this point/index, and the second one the min value from (but not including) this point onward (which will be generated traveling in reverse).

So for our example: [5, -1, 3, 8,6]

The 2 arrays will look like this:

MaxToThisPoint: [5,5,5,8,8]

MinFromThisPoint: [-1,-1,3,6,6]

Our cut-off point will be such index that value in MaxToThisPoint is smaller than the adjacent (index+1) value in MinFromThisPoint.

In our example thats between index 2 & 3: [5, -1, 3] and [8,6]

If we take an example with multiple cut-off points: [5, -1, 3, 6, 8]

The 2 arrays will look like this:

MaxToThisPoint: [5,5,5,6,8]

MinFromThisPoint: [-1,-1,3,6,8]

So for this example, we have 2 places that match our equation:

MaxToThisPoint[2] < MinFromThisPoint[3]

MaxToThisPoint[3] < MinFromThisPoint[4]

So our 2 cut-off points are between indexes 2 & 3 and indexes 3 & 4.

So the resulting arrays are: [5, -1, 3] , [6, 8] and [5, -1, 3, 6], [ 8]