## Amazon Interview Question

SDE-2s**Country:**United States

**Interview Type:**In-Person

```
#include <iostream>
#define SZ 10
using namespace std;
int findsubArray(int arr[], int& b, int &e)
{
int i, j, tb, te;
b = SZ-1;
e= -1;
//Assuming the sorting is ascending
//traverse as long as asending order is maintained
for(i=1, j=0; i<SZ; i++) {
if(arr[i] < arr[j]) {
//its a glitch in sorting order
//sub array sorting will be needed from the posizion where arr[i] fits
tb = j;
while(tb > -1 && arr[tb] > arr[i]) {
tb --;
}
tb++;
te = i;
if(tb < b) {
b = tb;
}
if(te > e) {
e = te;
}
cout<<"b = " << b << " e = " << e <<endl;
} else j = i;
}
return 0;
}
int main()
{
int sb, se;
int arr[10] = {0, 2, 5, 100, 3, 200, 1, 88, 300, 500};
findsubArray(arr, sb, se);
}
```

Would not following code work?

public class UnSortedSubArray {

public static void main(String[] args) {

int[] array = {1,13,2,4,17, 15, 19, 20,22};

Stack<Integer> integers = new Stack<>();

int start = -1;;

int end = -1;;

integers.push(array[0]);

for(int i = 1; i<array.length;i++)

{

if(integers.peek() > array[i]){

if(start == -1)

start = i-1;

end = i;

}

else

{

integers.push(array[i]);

}

}

System.out.println(start + " " + end);

}

}

```
pair<int, int> SortPatch(vector<int> const &a)
{
if (a.empty()) {
return pair<int, int>(-1, -1);
}
vector<int> min_to_right, max_to_left;
min_to_right.resize(a.size());
max_to_left.resize(a.size());
int max_val = numeric_limits<int>::min();
for (int i = 0; i < a.size(); ++i) {
max_val = max(max_val, a[i]);
max_to_left[i] = max_val;
}
int min_val = numeric_limits<int>::max();
for (int i = a.size() - 1; i >= 0; --i) {
min_val = min(min_val, a[i]);
min_to_right[i] = min_val;
}
int i = 0;
for (; i < a.size(); ++i) {
if (a[i] > min_to_right[i]) {
break;
}
}
int j = a.size() - 1;
for (; j >= 0; --j) {
if (a[j] < max_to_left[j]) {
break;
}
}
if (i >= j) {
return pair<int, int>(0, 0);
}
return pair<int, int>(i, j);
}
```

This is insertion sort.

> if elements are already sorted, it won't make any swap

```
private static void doInsertionSort(int[] arr) {
// Iterate through all cards : pick one each time
for (int i = 1; i < arr.length; i++) {
// say you have picked card called key
int key = arr[i];
int j = i-1;
while(j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
// move fwd one and place key card
arr[j+1] = key;
}
}
```

start of the unsorted array -> element for which line arr[j+1] = arr[j]; will start executing.

end of unsorted array -> element for which line arr[j+1] = arr[j]; will stop executing.

{start,....., end} will be min unsorted array.

There could be multiple such unsorted arrays. To find that, store all (start, end) and finally calculate one subarray with min length.

Time Complexity:- Since most of the elements are sorted, this will take between O(n) and O(n^2).

{

- Pinkesh September 06, 2017int input[n];

int min = input[n-1];

int max = input[0];

int sub_len = 0;

int e_idx = 0, s_idx = 0;

for(int i = 0; i < n-1; i++) {

if(input[n-i-1] < min) {

min = input[n-i-1];

} else {

s_idx = i;

}

if(input[i+1] > max) {

max = input[i+1];

} else {

e_idx = i;

}

}

if(e_idx > s_idx) {

sub_len = (e_idx - s_idx + 1);

}

}