Grokking 75: Top Coding Interview Questions
Vote

0% completed

​

Minimum Window Sort (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

import math

class Solution:
  def sort(self, arr):
    i = j = 0

    # find the first out order position element from [left to right] -->
    for count in range(len(arr)):
      if count - 1 >= 0 and arr[count] < arr[count - 1]:
        i = count - 1
        break

    # find the first out order position element from [right to left] <--
    end = i - 1 if i >= 0 else 0
    for count in range(len(arr) - 1, end, -1):  
      if count + 1 < len(arr) and arr[count] > arr[count + 1]:
        j = count + 1
        break

    # for example i and j are in the positions below
    # [-4, -2, 1, 3, 2, 9, 0, -3, 7, 10, 30]
    #             i            j      
    # find the min and max elements between i and j inclusive
    # min = -3, max = 9  == the range is out of order between [-
A

Anonymous

· 2 years ago

Compare 7 and -1, stop. high = 5.

The above line is wrong because as long as arr[hi] >= arr[hi-1] we decrement hi--;

7 >= -1 so hi should stop on -1 that is index 4 not at 7 with index 5

A

Anonymous

· 3 years ago

import math

class Solution:
  def sort(self, arr):
    sorted_arr = sorted(arr)
    if sorted_arr == arr or len(arr) == 1:
      return 0
    l, r = 0, len(arr) - 1
    while l <= r:
      if arr[l] == sorted_arr[l]:      
        l+= 1
      elif arr[r] == sorted_arr[r]:     
        r -= 1
      else:
        break
    return r-l+1
A

Anonymous

· 3 years ago

i have dry run it multiple times, iam getting 6 as the size of subarray window? i think visualization of algorithm is misleading , if you dry run the first input based on the visualization of algorithm you get 6 as the size of subarray!

i might be wrong, but i have dry run it twice, what you guys think???

i think the problem is here:     while (low > 0 && arr[low - 1] > subarrayMin) {       low -= 1;     }     // extend the subarray to include any number which is smaller than the maximum of     // the subarray     while (high < arr.length - 1 && arr[high + 1] < subarrayMax) {       high += 1;     }

While in visualization it compares arr[min] > subarray_min ? then low-- , to insert from beginning

the min and max i found in subarray 👇 min=3 max=10

the first inorder from beginning

Show 1 reply
A

Anonymous

· 3 years ago

Actual answer is 0. Submission is expecting 1.

A

Anonymous

· 3 years ago

[22, 34, 59, 60, 75, 76, 81] fails because it expects 1 during submission, but when I run it before submission it expects 0.

A

Anonymous

· 3 years ago

public static int sort(int[] arr) {

int min = Integer.MAX_VALUE;

    int max = Integer.MIN_VALUE;

    if (arr.length == 1) return 0; 

    for (int i = 0; i < arr.length; ++i) {

        if (i == 0) {

            if (arr[i] > arr[i + 1]) {

                min = Math.min(min, arr[i]);

                max = Math.max(max, arr[i]);

            }

        } else if (i == arr.length - 1) {

            if (arr[i] < arr[i - 1]) {

                min = Math.min(min, arr[i]);

                max = Math.max(max, arr[i]);

            }

        } else {

            if (arr[i] > arr[i + 1] || arr[i] < arr[i - 1]) {

                min = Math.min(min, arr[i]);

                max = Math.max(max, arr[i]);
A

Anonymous

· 3 years ago

Why is it medium? It is impossible to come up with a solution O(n) in a reasonable time...

A

Anonymous

· 4 years ago

def shortest_window_sort(arr): if len(arr) < 2: return 0

start,end= -1,-2 high_num = arr[0] for i in range(1,len(arr)): if arr[i] >= high_num: high_num = arr[i] else: start = i - 1 if start == -1 else start while start > 0 and arr[i] < arr[start - 1]: start -=1 end = i return end-start+1

this is my solution. This is also O(N) correct?

A

Anonymous

· 4 years ago

how do u get the intuition to do this?

Show 2 replies

Reading Progress

0%

Vote for new content