Amazon Interview Question for SDE-2s


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)
	{
		cout<<"array is already sorted\n"; 
		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;
}

- 1337yogesh September 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great solution, works like charm!

- merida September 19, 2014 | Flag
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

- geraskov September 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- Anonymous September 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Mark September 19, 2014 | Flag
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'.

- Neil September 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Neil September 19, 2014 | Flag
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]+" ");
		}
	}

- shukad333 September 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 1337yogesh September 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- shukad333 September 19, 2014 | Flag
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;
	}

- shukad333 September 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 1337yogesh September 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 1337yogesh September 19, 2014 | Flag
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;
}

- Ashish September 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 1337yogesh September 19, 2014 | Flag
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] + " , ");
    }
  }

- maheshbansal.cs September 19, 2014 | Flag Reply
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;
}

- Anonymous September 19, 2014 | Flag Reply
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); 
	}

}

- srammer September 20, 2014 | Flag Reply
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;
}

- Tauqir Azam September 21, 2014 | Flag Reply
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){
  //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;
}

- zortlord October 06, 2014 | Flag Reply
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)
{
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);

}

- shikhil October 19, 2014 | Flag Reply
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
	}
}

- kn October 19, 2014 | Flag Reply
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]);

}

- shiva November 02, 2014 | Flag Reply
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.

- deepanshu November 19, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More