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

}
}``````

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

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

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

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

we can use pancake sorting.

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

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

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

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

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

}``````

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

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

}

}``````

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

}

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

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

}

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

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

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

}
}``````

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

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

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

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.

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

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

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

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

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.