Amazon Interview Question
SDE-2sCountry: 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);
}
}