## 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);

}

```
public class PartitionArray {
public static void main(String[] args) {
int[] numbers = new int[] { 5, -1, 3, 8, 6 };
System.out.println(getPartitionIndex(numbers));
}
private static int getPartitionIndex(int[] numbers) {
int currentMax = numbers[0];
boolean decreased = false;
int index = 0;
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] > currentMax & !decreased) {
currentMax = numbers[i];
} else if (numbers[i] < currentMax) {
decreased = true;
index = i;
}
}
return index;
}
}
```

```
def partition(a):
if a[0] > a[-1]:
return -1
lpos, rpos = 0, len(a) - 1
lmax, rmin = a[0], a[-1]
moved = True
while rpos - lpos > 1 and moved:
moved = False
if a[lpos+1] < rmin:
lmax, lpos, moved = max(lmax, a[lpos+1]), lpos+1, True
if lmax < a[rpos-1]:
rmin, rpos, moved = min(rmin, a[rpos-1]), rpos-1, True
return lpos if moved else -1
```

private void execute() {

int[] input = new int[]{0, 9, 1, 2, 3};

if (input.length == 0) {

return;

}

int minHigh = input[0], maxLow = input[input.length - 1], i = 0, j = input.length - 1;

for (; i < j; ) {

int high = Math.max(minHigh, input[i]);

int low = Math.min(maxLow, input[j]);

if (high < low) {

i++;

maxLow = low;

minHigh = high;

} else {

if (low <= high) {

i--;

j--;

maxLow = low;

}

}

}

if (i == j)

System.out.println(i);

}

```
private void execute() {
int[] input = new int[]{0, 9, 1, 2, 3};
if (input.length == 0) {
return;
}
int minHigh = input[0], maxLow = input[input.length - 1], i = 0, j = input.length - 1;
for (; i < j; ) {
int high = Math.max(minHigh, input[i]);
int low = Math.min(maxLow, input[j]);
if (high < low) {
i++;
maxLow = low;
minHigh = high;
} else {
if (low <= high) {
i--;
j--;
maxLow = low;
}
}
}
if (i == j)
System.out.println(i);
}
```

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]