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


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