## Amazon Interview Question for SDE-2s

• 1
of 1 vote

Country: India
Interview Type: In-Person

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

Time Complexity O(N)
Space Complexity O(1)

Following is the code written in C++
Just include the header files and copy paste the code.
Let me know if there are bugs :P

``````int
find_min_array (int* a, int s, int e);

int
find_max_array (int* a, int s, int e);

void
find_min_subarray_sort(int* a, int sidx, int eidx);

int main ()
{
int *a;
cout<<"enter the number of elements to fill in the array\n";
int n;
cin>>n;

a=new int[n];

cout<<"Fill the array with "<<n<<" elements\n";

for (int i =0;i<n;i++)
cin>>a[i];

// Now find min subarray in O(N) time
find_min_subarray_sort (a,0,n-1);
return 0;
}

void
find_min_subarray_sort(int* a, int sidx, int eidx)
{
int s = sidx;
int e = eidx;

int first;
int last;
int i;

for(i=s;i<e;i++)
{
if(a[i]>a[i+1])
break;
}
first = i;

if (first == eidx)
{
return;
}

for(i=e;i>s;i--)
{	if(a[i] < a[i-1])
break;
}
last = i;

int min = find_min_array (a, first+1, last);
// Where to fit this min from 0 to first? We can do a Binary search here, but that will not change the complexity. Doing linear search for now
for(i=0;i<=first;i++)
{
if(min<a[i])
break;
}
cout<<"Min Subarray is the following (Indices start from 0): "<<endl;
cout<<"Start Index: "<<i<<endl;

int max = find_max_array (a, first, last-1);
// Where to fit this max from last to n-1?We can do a Binary search here, but that will not change the complexity. Doing linear search for now
for(i=eidx;i>last;i--)
{
if(max>a[i])
break;
}
cout<<"End Index: "<<i<<endl;
}

int
find_min_array (int* a, int s, int e)
{
int min=a[s];

for(int i=s+1;i<=e;i++)
{
if(a[i]<min)
min = a[i];
}
return min;
}

int
find_max_array (int* a, int s, int e)
{
int max=a[s];

for(int i=s+1;i<=e;i++)
{
if(a[i]>max)
max = a[i];
}
return max;
}``````

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

Great solution, works like charm!

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

1. Traverse from left and get the endIndex from where numbers break increment sequence. This is our LEFT part of the array
2. Find MIN element in the right part of the array.
3. Cut LEFT part so it would have all elements <= MIN(binary search). This is SORTED_LEFT
4. Do same from right(without touching SORTED_LEFT as all smallest elements are there) and you'll have SORTED_RIGHT
5. What is left is unsorted subarray

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

can you explain for this arr={-5,0,4,3,2,1,7,8,-3,9,-1} ??
step 3 i can't get it.

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

arr={-5,0,4,3,2,1,7,8,-3,9,-1}

1. Going from left - the first violator is 3, then LEFT is {-5, 0, 4}
2. MIN in the right part is -3
3. Cut LEFT will be {-5} since only -5 < MIN
4. Going from right - the first violator is 9, then RIGHT is {-5,0,4,3,2,1,7,8,-3}
5. MAX in left part is 9
6. Cut LEFT will be {} - empty array, since there are no elements > 9
7. From step 3 and 6 we have that min subarray is {0,4,3,2,1,7,8,-3,9,-1}

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

I think this condition, "(without touching SORTED_LEFT as all smallest elements are there)"
Could cause the following changed:
RIGHT is {-5,0,4,3,2,1,7,8,-3}
RIGHT is {0,4,3,2,1,7,8,-3}
Since SORTED_LEFT is -5 at this time, but actually this comment "(without touching SORTED_LEFT as all smallest elements are there)"
It is important because you get performance gains in not having to search those indices when looking for MAX in RIGHT.

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

The simplest way (complexity of n) that I can think of is to first find the breakpoint by traversing from the let side of the array towards the right.

Call the pointer pointing to this index 'L' (denoting current left of the minimum sub array).

Assign 'R' to the next index (i.e., L+1).

Now, for every element from R to the end of the array, compare it with the element at L. If it is lower than L , set R as this index and keep decreasing L until arr[R] > arr[L]. When you've exhausted the checks for all elements in the array with arr[L], the minimum sub array is given by L...R.

Basically, you're expanding your minimum unsorted sub array conservatively (in an inverse way, greedily).

Now, for the complexity, the worst case occurs when L is at n-2 (assuming 0-indexed arrays) and R is at n-1 and you have to shift the L pointer all the way to index 0. In fact, the number of shifts of L towards the left and R towards the right after finding the breakpoint cannot be more than 'n'.

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

This is assuming an increasing order sorted array is supposed to be the output.

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

``````static void printShortestSub(int[] arr) {

int[] copy = Arrays.copyOf(arr, arr.length);
Arrays.sort(copy);

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

if(arr[i]!=copy[i])
System.out.print(arr[i]+" ");
}
}``````

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

Sorting will take atleast O(N LogN) Time in the worst case.
Copying will take atleast O(N) Space.

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

Ok.. I've put another solution at the bottom ....

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

``````static void printSmallest(int[] arr) {

int len = arr.length;
int stIndex = -1;
int endIndex = -1;
int max = Integer.MIN_VALUE;

for(int i=0;i<len-1;i++) {
/*
if(arr[i]>max){
stIndex = i;
j
}
*/

if(arr[i]>arr[i+1]) {
stIndex = i;
break;
}

}

for(int i=len-1;i>0;i--) {

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

endIndex = i;
break;
}
}
int min = minIndex(Arrays.copyOfRange(arr, stIndex, endIndex+1));
max = maxIndex(Arrays.copyOfRange(arr, stIndex , endIndex+1));

for(int i=0;i<stIndex;i++) {

if(arr[i]>min)
stIndex = i;
}

for(int i=len-1;i>=endIndex+1;i--) {

if(arr[i]<min)
endIndex = i;
}

for(int i=stIndex;i<=endIndex;i++)
System.out.print(arr[i]+" ");
}

static int minIndex(int[] arr) {

int min = Integer.MAX_VALUE;
for(int ele : arr) {

if(ele<min)
min = ele;
}

return min;
}

static int maxIndex(int[] arr) {

int max = Integer.MIN_VALUE;
for(int ele : arr) {

if(ele>max)
max = ele;
}

return max;
}``````

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

doesn't seem correct to me.
try input as the following array --> {1,1,1,1,1};

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

try {1,2,9,4,4,4};
correct output should be 9 4 4 4

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

The solution is simple: Scan the list from left and stop where the the number is no longer higher than the subsequent number. This stop point is our first (start) index. Similarly, start from the end of the list, moving left towards the first index, and stop where the previous number is no less than the current number. This stop point is our second(end) index.

The code:

``````void findMinArrToSort(int arr[], int size, int* start, int* end){
int i=0,j=0,k=0;
int foundEnd = 0;
for(i=0;i<size;i++){
if(arr[i+1]>=arr[i])
continue;
break;
}
*start = i;
for(j=size-1;j>i;j--){
if(arr[j]> arr[j-1])
continue;
break;
}
*end = j;
cout<<"Start Index="<<*start<<endl;
cout<<"End Index="<<*end<<endl;
}

int main()
{
int i=0,j=0;
int arr[]={-6,-1,0,4,3,2,1,7,8,6,5,9,1,10,12};
int size = sizeof(arr)/4;
printArr(arr,size);
findMinArrToSort(arr,size,&i,&j);
return 0;
}``````

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

try {1,1,-2,3,4,5};
output should be:
Start Index=0
End Index=2
but I think yours will give start index as 1

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

Once we found the lower and upper indexes , we need to iterate within the subarray to adjust the lower/upper indexes too. Please find the code below.

thanks

``````public void setData(int[] data)
{
array = data;
}

public void findSubArray()
{
//inclusive indexes for subarray
int lowerIndex = 0;
int upperIndex = array.length - 1 ;

while(array[lowerIndex] < array[lowerIndex + 1 ])
{
lowerIndex ++ ;
}

while(array[upperIndex] > array[upperIndex - 1])
{
upperIndex --;
}

for(int j = lowerIndex ; j <= upperIndex && j < array.length ; j++)
{
int currentVal = array[j];
//this value should be greater than lowerIndex value and lesser than upperIndex value. If not , adjust the indexes

if(currentVal >= array[lowerIndex] && currentVal <= array[upperIndex])
{
continue;
}
else if( currentVal < array[lowerIndex])
{
//adjust lowerIndex to point to the correct index where value is smaller than currentVal
while(lowerIndex >=0 && currentVal < array[lowerIndex])
{
lowerIndex --;
}
//adjust it back to make it inclusive
lowerIndex ++ ;
}else if( currentVal > array[upperIndex])
{
//adjust upper to point to the correct index where value is greater than currentVal
while(upperIndex < array.length && currentVal > array[upperIndex])
{
upperIndex ++;
}
//adjust it back to make it inclusive
upperIndex -- ;
}
}

dumpArray(array , lowerIndex, upperIndex);

}

private void dumpArray(int [] array , int startIndex , int endIndex)
{
for(int i = startIndex  ; i <= endIndex ; i++)
{
System.out.println(array[i] + " , ");
}
}``````

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

``````int shortest_subarray(int *data, int size)
{
int index_min=0;
int index_max=size-1;

for (int i=1; i<size; i++ ) {
if ( data[i] >= data[index_min] ) {
if (index_min == i-1 ) { index_min++; } // still in order
} else {
index_min--;
if ( index_min < 0 ) break;
i--; // re-check it.
}
}

if ( index_min == size-1) { printf("Sorted.\n"); return 0;}

for ( int i=size-2; i>=0; i--) {
if ( data[i] <= data[index_max] ) {
if ( i+1 == index_max ) { index_max--; } // still in order
} else {
index_max++;
if ( index_max == size ) break;
i++; // recheck
}
}

printf( "Sub arrary: %d -> %d \n", index_min+1, index_max-1);
return 0;
}``````

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

I think, I have quickest algorithm with only one Loop,

``````{
private int[] findShortestArray(int[] array) {
int least = 0;
int highest = 0;
int cBegin = -1;
int cEnd = 0;
for(int i=1; i < array.length; i++) {
if(array[i-1] > array[i] || (array[least] >= array[i] && array[highest] <= array[i])) {
if(cBegin < 0) {
cBegin = i-1;
}
cEnd = i;
}
if(array[least] > array[i]) {
cBegin = least < cBegin ? least : cBegin;
least = i;
}
if(array[highest] < array[i]) {
highest = i;
}
}

return Arrays.copyOfRange(array, cBegin, cEnd+1);
}``````

}

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

#include<stdio.h>
#include<string.h>
int main()
{
int arr[]={3,1,2,-5,7,8,9};
int i,j,min,flag=0;
for(i=0;i< sizeof(arr)/4;i++)
{
if (arr[i+1]<arr[i])
continue;
else
{
for(j=i+1;j<sizeof(arr)/4 -1;j++)
if (arr[j+1] < arr[j])
{
flag=1;
break;
}
else
{
continue;
}
}
if(flag==0)
{
break;
}
i=j;
flag=0;

}
min=i;
printf(" {0,%d}",min);
return 0;
}

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

How about O(n) complexity and O(1) space as well:

``````public static int[] unsortedRange(int[] arr){
if(arr == null || arr.length < 2){
return null;
}
//setup tracking information
int start = -1;
int end = -1;
int ptr = 0;
int max = arr;
while(ptr < arr.length){
if(arr[ptr] < max){
if(start == -1){
start = ptr-1;
}
end = ptr;
}
else{
max = arr[ptr];
}
ptr++;
}
if(start > -1){
return new int[]{start, end};
}
return null;
}``````

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

static void FindSortestSubArray(int[] array, int start)
{
int previous_index = start;
int right_index = -1;
int left_index=-1;
int right_min =int.MaxValue;
for (int i = start + 1; i < array.Length; i++)
{
if (!(array[i] > array[previous_index]))
{
left_index = previous_index;
break;
}
previous_index = i;
}
if (left_index == array.Length - 1)
{
return;
}
else
{
int j;
for (j = left_index + 1; j < array.Length; j++)
{
if (array[j] > array[left_index])
{
right_index = j;
break;
}
if (right_min > array[j])
right_min = array[j];
}
if(right_index ==-1)
{
right_index = array.Length - 1;
}
for (int k = right_index + 1; k < array.Length; k++)
{
if (!(array[k] > array[j]))
{
right_index = k;
}
if (right_min > array[k])
right_min = array[k];
}
}
if (right_index == array.Length - 1)
{
// new
}

for (int l = start; l < left_index; l++)
{
if (!(right_min > array[l]))
{
left_index = l;
break;
}
}
Console.WriteLine(" start " + left_index + " end " + right_index);

}

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

how about using quickSort's partition logic to find correct indexes?

``````/**
* 1> Find
* 		index where discrepancy starts - dStartIndex
* 		index where discrepancy ends -	dEndIndex
*
* 2> From i=dStartEnd till dEndIndex (inclusive)
*  	find min element and its index
*  	find max element and its index
*
* 3> Find the true index where min element should be kept - using "partition" logic of quickSort - dRealStartIndex
* 4> Find the true index where max should be kept - dRealEndIndex
*
* 5> SubArray that needs to be sorted ranges from dRealStartIndex till dRealEndIndex (inclusive)
*
*/
public class MinSubArrayWithUnsortedValues {

public static void main(String[] args) {
//int a[] = {-1, 0, 4, 3, 2, 1, 7, 8, 9};				//[4,3,2,1]
//int a[] = {10, 15, 20, 30, 25, 40, 35, 45, 50, 60};	//[30, 25, 40, 35]
int a[] = {-1, 0, 4, 3, 2, 1, 7, 8, 9, -2};				//[-1,0,4,3,2,1,7,8,9,-2]
int dStartIndex=-1;
int dEndIndex=-1;
for(int i=0;i<a.length;i++){
if(i+1<a.length && a[i]>a[i+1]){
if(dStartIndex < 0){
dStartIndex=i;
} else {
dEndIndex = i+1;
}
}
}

int dMinValue = Integer.MAX_VALUE;
int dMinValueIndex=-1;
int dMaxValue = Integer.MIN_VALUE;
int dMaxValueIndex=-1;
for(int i=dStartIndex;i<=dEndIndex;i++){
if(dMinValue > a[i]){
dMinValue = a[i];
dMinValueIndex = i;
}
if(dMaxValue < a[i]){
dMaxValue = a[i];
dMaxValueIndex = i;
}
}

if(dMinValueIndex<0 || dMaxValueIndex<0)
return;

int dRealStartIndex = partition(a, dMinValueIndex);
int dRealEndIndex = partition(a, dMaxValueIndex);

for(int i=dRealStartIndex;i<=dRealEndIndex;i++){
System.out.print(a[i]+" ");
}
}

/**
* QuickSort partition without any real swapping
* @param arr
* @param randomIndex
* @return
*/
public static int partition(int []arr, int randomIndex){
int pivotValue = arr[randomIndex];
//swap(arr, randomIndex, arr.length-1);
int pivotRealIndex = 0;
for(int i=0;i<=arr.length-1;i++){	//quicksort condition - i<arr.length-1 - but we are not doing any swap so need to check till the end of the array
if(arr[i] < pivotValue && i!=randomIndex){	//shift less values on left hand side
//swap(arr, pivotRealIndex, i);	//pivotRealIndex <= i
pivotRealIndex++;
}
}
//swap(arr, pivotRealIndex, arr.length-1);
return pivotRealIndex;	//must return real start|end index
}
}``````

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

``````public void findSubArray(int a[]){
int leftIndex = 0;
int rightIndex = a.length-1;
int i;
for( i=1;i<a.length && a[i]> a[leftIndex];i++){
leftIndex = i;
}

int j=a.length-2;

for( ;j>=0 && a[j]< a[rightIndex];j--){
rightIndex = j;
}

System.out.println(leftIndex + " to "+ rightIndex);

for(int k=leftIndex;k<=rightIndex;k++)
System.out.println(a[k]);``````

}

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

I think O(n) is very obvious solution. It should only take O(logn) as the array is sorted. We first find the number which violates the condition of an increasing sequence using binary search, and then we find the number which violates decreasing sequence...

The code for it will be very messy but yeah efficient.

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.