Microsoft Interview Question

Country: United States

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

It is unclear which index we're looking for here.
For 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]

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

@Alex
MinFromThisPoint is calculated by traversing the given input array from left to right. Initially set MinFromThisPoint to the last element and start traversing from the last element and then keep updating the min when a smaller element is found.

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[0]; 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);

}

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

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

}``````

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

``````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``````

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

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

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

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

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

a

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

a

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.