Amazon Interview Question
SDE-2sCountry: India
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);
}
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
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;
}
}
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);
}
}
}
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;
}
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;
}
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--));
}
}
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--));
}
}
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.
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;
}
- Resh February 20, 2015