Microsoft Interview Question


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 [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]

- Alex July 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How are we computing MinFromThisPoint ?

- alex August 04, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How are we computing MinFromThisPoint array

- Alex August 04, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Pranav November 28, 2020 | Flag
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);
    }

}

- Valerii Tiurin July 15, 2020 | Flag Reply
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;
}

- Sid July 17, 2020 | Flag Reply
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) {
high.add(input[i]);
} else {
low.add(input[i]);
}
}

for (Integer value:low) {
}

System.out.println(""
}

- Anonymous July 18, 2020 | Flag Reply
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++ ) {
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);

}

- Anonymous July 18, 2020 | Flag Reply
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;
	}

}

- Barun February 09, 2021 | Flag Reply
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

- shauligal February 23, 2021 | Flag Reply
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);
}

- Yash Patel October 31, 2021 | Flag Reply
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);
    }

- yash October 31, 2021 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More