Amazon Interview Question for SDE-2s


Country: India




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

public static void sortUsingRevMethod(int[] arr){
		
		for(int i=arr.length-1;i>=0;i--){
			//find largest from 0 to i
			int largestIndex = findLargest(arr,i);
			if(largestIndex!=i){
				rev(arr,0,largestIndex);
				rev(arr,0,i);
			}
			
		}
	}

- Resh February 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is nothing but part of pancake sorting... hoe u will get the answer when u will get to know pancake sorting...

- sumit.polite February 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is nothing but part of pancake sorting... hoe u will get the answer when u will get to know pancake sorting...

- sumit.polite February 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

So clearly this is a reference to pancake sorting, so it can be solved trivialy with only 2n-3 reversals and even fewer with non-trivial algorithms, the problem with this approach is the work involved in searching for the max value of the array in order to figure out what index to flip at is still O(n^2). However that is not good for a sort algorithm. The task can be accomplished in O(n log n) by implementing block sort using only reverse operations.

See Wikipedia for a description of the block sort algorithm. The important information is it can be implemented as an inplace sort with O(n log n). The algorithm is complicated enough so writing code for it here would be a little ridiculous. Anyway all of the required operations to implement it can be expressed as functions using only the reverse function, so you should be able to maintain the O(n log n) time complexity. As an example here is a swap function.

void swap(int i1, int i2){
    int min = Math.min(i1, i2);
    int max = Math.max(i1, i2);
    reverse(max);
    reverse(max-(min+1));
    reverse(max);
    reverse(min+1);
    reverse(1);
    reverse(min+1);
    reverse(max);
    reverse(max-(min+1));
    reverse(max);
}

- wHack23 February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can use pancake sorting.

- lokesh.vashisata February 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swap(int *x,int *y){

*x=*x^*y;
*y=*x^*y;
*x=*x^*y;
}

void rev(int a[],int i){

int j=0;

while(j<i){
swap(&a[j],&a[i]);
j++;i--;
}

}

void sort2(int a[],int n){

int i=0,minIndex;
while(i<n){

minIndex=GetMinIndex(a+i,n-i);
//printf("%d ",minIndex);

rev(a+i,minIndex);
i++;
}
}

- sunytyagi February 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for curindex = last to 2
maxind = findmax(0,curindex)//get the max till curindex
if maxind == curindex
continue;// elemnt is at the proper position
else
reverse(maxind)//this brings the max element to index 0
reverse(curindex)//this brings the max element to curindex

- AT February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for curindex = last to 2
{
maxind = findmax(0,curindex)//get the max till curindex
if maxind == curindex
continue;// element is at the proper position
else
{
reverse(maxind)//this brings the max element to index 0
reverse(curindex)//this brings the max element to curindex
}
}

- AT February 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Training {

	public static void main(String[] a) {

			Training t = new Training();
			int[] arr = { 3,2,1,4,7,2,1,-6,14,-1 };

			for(int i = 0; i < arr.length; i++)
				System.out.print(arr[i] + "|");

			t.sort(arr);
			
			System.out.println("");
			for(int i = 0; i < arr.length; i++)
				System.out.print(arr[i] + "|");

	}
	
	public void sort(int[] arr){
	
		for(int mi = arr.length - 1; mi > 0; mi--) {

			int ci = 0;
			int cv = arr[0];
			
			for(int i = 0; i <= mi; i++) {
				if(arr[i] > cv) {
					cv = arr[i];
					ci = i;
				}
			}
			
			if(ci != mi) {
				rev(arr, ci);
				rev(arr, mi);
			}

		}
		
	}

	public void rev(int arr[], int f){
		int s = 0;

		if(arr.length == 0)
			return;

		while(s < f){
			swap(arr, s, f);
			s++;
			f--;
		}
	}

	public void swap(int arr[], int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

}

- waldou February 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry,

public void sort(int[] arr){
	
		for(int mi = arr.length - 1; mi > 0; mi--) {

			int ci = 0;
			for(int i = 0; i <= mi; i++) {
				if(arr[i] > arr[ci]) {
					ci = i;
				}
			}
			
			if(arr[ci] != arr[mi]) {
				rev(arr, ci);
				rev(arr, mi);
			}

		}
		
	}

- waldou February 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void Sort(int[] num){
    	if(num.length <= 0){
    		return;
    	}
    	
    	for(int i = 1; i < num.length; i++){
    		int start = -1;
    		int end = i;
    		for(int j = 0; j < i; j++){
    			if(num[j] >= num[i]){
    				start = j;
    				break;
    			}
    		}
    		
    		if(start < 0){
    			continue;
    		}
    		
    		rev(num, start, end);
    		if(start + 1 < end){
    			rev(num, start + 1, end);
    		}
    	}

}

- cqyanbo February 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private void flip( int s, int e) {
		int j = e,temp;
		for (int i = 0; i < Math.floor((s + e) / 2); i++) {
			temp = arr[i];
			arr[i]= arr[j];
			arr[j] = temp;
			j--;

		}
	}

	private int maxElementIndex( int s, int e) {
		int max = 0, i = 1;
		while (i <= e) {
			if (arr[i] > arr[max]) {
				max = i;
				i++;
			} else {
				i++;
				continue;
			}
			
		}

		return max;
	}

- nitinsaxena February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void rev(int a[],int j)
{
	int i=0,temp;
	while(i<j)
	{
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
		i++;
		j--;
	}
}
void sort(int a[6],int n)
{
	int i,n1=n,j;
for(i=0;i<n;i++)
{
	for(j=1;j<n1;j++)
	{
		if(a[0]<a[j]){
			rev(a,j);
		}
	}
	//printf("%d",j);
	rev(a,j-1);
	n1--;
}

}

- Abhishek February 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void pancakesort(int a[], int i) {
    for (; i > 1; i--) {
        int m_index = indexOfMax(a, i);
        rev(a, m_index);
        rev(a, i - 1);
    }
}

- foo February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void pancakesort(int a[], int i) {
    for (; i > 1; i--) {
        int m_index = indexOfMax(a, i);
        rev(a, m_index);
        rev(a, i - 1);
    }
}

- foo February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void sortUsingRevMethod(int[] arr){
		
		for(int i=arr.length-1;i>=0;i--){
			//find largest from 0 to i
			int largestIndex = findLargest(arr,i);
			if(largestIndex!=i){
				rev(arr,0,largestIndex);
				rev(arr,0,i);
			}
			
		}
	}

- Resh February 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] revSort(int...values) {
    int idxMax;
    boolean sorted = false;
    for(int flips=0; flips < values.length; flips++) {
        idxMax = 0;
        sorted = true;
        for(int idx=0; idx < values.length - flips; idx++) {
            if(values[idxMax] < values[idx]) {
                idxMax = idx;
            }
            else if(values[idxMax] > values[idx]) {
                sorted = false;
            }
        }
        if(sorted) {
            break;
        }
        while(idxMax < values.length-1-flips && values[idxMax] == values[values.length-1-flips]) {
            flips++;
        }
        if(idxMax == values.length-1-flips) {
            continue;
        }
        rev(values, idxMax);
        rev(values, values.length-1-flips);
    }
    return values;
}
static void rev(int[] values, int upper) {
    int lower=0;
    while(lower < upper) {
        swap(values, lower++, upper--);
    }
}
static void swap(int[] values, int idx1, int idx2) {
    int tmp = values[idx1];
    values[idx1] = values[idx2];
    values[idx2] = tmp;
}

- theclish August 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A quickSort based solution:
{
public void sortUsingReverseFunction(int array[]){
if(array == null)
return;
sortUsingReverseFunction(array, 0, array.length-1);
}

private void sortUsingReverseFunction(int array[], int start, int end){
if(start >= end)
return;
int i = start, j = end-1;
for(;i < j;){
if(array[i] >= array[end]){
reverse(array,i,j--);
}
else
i++;
}
reverse(array,array[i] < array[end]? ++i : i,end);
sortUsingReverseFunction(array, start, i-1);
sortUsingReverseFunction(array, i+1, end);
}

private void reverse(int array[], int start, int end){
if(array == null)
return;
for(;start < end; swap(array,start++,end--));
}
}

- Sandy May 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A quickSort based solution:
{
public void sortUsingReverseFunction(int array[]){
if(array == null)
return;
sortUsingReverseFunction(array, 0, array.length-1);
}

private void sortUsingReverseFunction(int array[], int start, int end){
if(start >= end)
return;
int i = start, j = end-1;
for(;i < j;){
if(array[i] >= array[end]){
reverse(array,i,j--);
}
else
i++;
}
reverse(array,array[i] < array[end]? ++i : i,end);
sortUsingReverseFunction(array, start, i-1);
sortUsingReverseFunction(array, i+1, end);
}

private void reverse(int array[], int start, int end){
if(array == null)
return;
for(;start < end; swap(array,start++,end--));
}
}

- sandy May 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The idea will be to use mergesort, breaking the array into smaller partitions until we hit 2 numbers and if they are out of place you will be using the rev method to reverse them.

- srikanth February 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry commented a little too fast did not see index 0 in there

- srikanth February 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

May not be the best of solutions, but one possible one:-

public void sort(int[] array) {
        int length = array.length;

        while(length > 0) {
            int maxIndex = getMaxIndex(array, length);
            rev(array, maxIndex+1);
            rev(array, length);
            length--;
        }
}

public int getMaxIndex(int[] array, int endPos) {
        int maxIndex = 0;
        for(int i = 1; i < endPos; i++) {
            if(array[maxIndex] < array[i]) {
                maxIndex = i;
            }
        }
        return maxIndex;
}

- srikanth February 07, 2015 | Flag


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