Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
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
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}
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.
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'.
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]+" ");
}
}
Sorting will take atleast O(N LogN) Time in the worst case.
Copying will take atleast O(N) Space.
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;
}
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;
}
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] + " , ");
}
}
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;
}
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);
}
}
#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;
}
How about O(n) complexity and O(1) space as well:
public static int[] unsortedRange(int[] arr){
//bad inputs
if(arr == null || arr.length < 2){
return null;
}
//setup tracking information
int start = -1;
int end = -1;
int ptr = 0;
int max = arr[0];
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;
}
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)
{
Console.WriteLine("List is already soretd");
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);
}
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
}
}
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]);
}
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.
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
- 1337yogesh September 19, 2014