## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
int 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);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it assumed that the array should be increasing?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am wondering whether the subarray should be consecutive or not consecutive?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ {{{ #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); } }}} }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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.

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

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

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