## Microsoft Interview Question

• 0

Country: United States

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

It is unclear which index we're looking for here.
For example: [1,2,3] can be divided into , [2,3] or into [1,2], . 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!

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 < MinFromThisPoint
MaxToThisPoint < MinFromThisPoint
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]

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

How are we computing MinFromThisPoint ?

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

How are we computing MinFromThisPoint array

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

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

}

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

``````void Split(int[] arr)
{
var lo = 0; var hi = arr.Length-1;
maxLo = arr; minHi = arr[hi];
while(lo < hi)
{
if(maxLo < minHi)
{
lo++; hi--;
}
else
{
if(maxLo > minHi) return lo-1;
return hi;
}
maxLo = Math.Max(maxLo, arr[i]);
minHi = Math.Min(minHi,arr[i]);
}
return -1;
}``````

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

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) {
} else {
}
}

for (Integer value:low) {
}

System.out.println(""
}

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

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++ ) {
}

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

}

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.