Pancake sort inteview using java

Question

Given an array of integers arr:

Write a function flip(arr, k) that reverses the order of the first k elements in the array arr.
Write a function pancakeSort(arr) that sorts and returns the input array.

You are allowed to use only the function flip you wrote in the first step in order to make changes in the array.

Example:

input: arr = [1, 5, 4, 3, 2]

output: [1, 2, 3, 4, 5] # to clarify, this is pancakeSort's output

My approach:

import java.io.*;
import java.util.*;
class Solution {
 static int[] pancakeSort(int[] arr) {
 // your code goes here
 int max = -1000,maxpos = 0 ;
 //3 1 2 4 6 5 --> 6 4 2 1 3 5
 for(int i = 0; i < arr.length; i++ )
 {
 max = -1000;
 for( int c = i; c < arr.length; c++ )
 {
 if( max <= arr[c] )
 { 
 max = arr[c];
 maxpos = c;
 }
 }
 arr = flip(arr,i,maxpos+1);
 }
 arr = flip(arr,0,arr.length);
 return arr; 
 }
 // 3 1 2 4 6 -> 6 4 2 1 3 5
 // k = 5 ->
 static int[] flip(int [] arr,int start , int k)
 {
 int temp;
 for(int i = start, j = k - 1; i < j; i++, j-- )
 {
 temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
 return arr;
 }
 // 
 //1 5 4 3 -> 3 4 5 1
//54321
 1 5 4 3 2 --> flip(arr, maxpos) -> 5 1 4 3 2 --> flip(arr,arr.length ) -> 2 3 4 1 5
 public static void main(String[] args) {
 }
}

I have the following questions about my code:

1. Can I further improve my space and time complexity?

2. Is there any other alternative, smarter way to attempt this question?

3. Any grave coding convention that I have violated in my code?

Reference

• Vogel612: For the record: pancake sort boils down to being a highly inefficient selection sort. The time-complexity will be n^2 * n :(
• Anirudh Thatipelli: That is so inefficient. I got it as a mock interview question. So, I want to know whether there exists a more efficient way to solve the question.
• Duarte Meneses: In the problem description it's written that you can only use flip(arr, k) but you implemented flip(arr,start,k). Could you clarify this?
• Anirudh Thatipelli: I redefined the function slightly to suit my needs
• Koekje: But then it does not seem like a real pancake sort, you can not flip a stack of pancakes underneath another stack of pancakes.

Answer 1

Flip

• Use better variable names. i and j are harder to read than something like front and back.

• It's preferable to define the temp value inside the loop and save a line of code.

• The method should be private.

• Depending on what the interviewer wants, it's much nicer to make a new array than to destructively modify the existing one. I'll assume you asked and they specified to modify the existing array. That being the case, you don't need to return the modified array.

Pancake Sort

• You're not doing a pancake sort. It's nonsensical for you to describe a problem and then ask us to review code that breaks your own stated invariants to solve the problem.

• -1000 is arbitrary. Use Integer.MIN_VALUE and your code will work for all negative numbers.

• Don't use abbreviations or shorten variable names. The extra letters don't cost anything. max and maxPos are not sufficiently descriptive. Don't use c as an array index. Either use j or a descriptive name.

• In the comments, you observe that pancake sort is inefficient. Yes, it is. The point was to pick a sort that most people haven't thought about so everybody starts on an even playing field for the interview question. The inefficiency is tied to the algorithmic limitation of only having flip() available. There are no significant performance gains to be had unless you break that limitation, at which point you're no longer doing a pancake sort.

Using an actual pancake sort and my other suggestions, your code might look something like:

class Solution {
 // return an int for convenient testing
 private static int[] pancakeSort(final int[] array) {
 boolean sorted = false;
 while (!sorted) {
 sorted = true;
 for (int i = 0; i < (array.length - 1); i++) {
 if (array[i] > array[i + 1]) {
 flip(array, i + 1);
 flip(array, i + 2);
 flip(array, i + 1);
 sorted = false;
 break;
 }
 }
 }
 return array;
 }
 private static void flip(final int[] array, final int elementsToFlip) {
 for (int front = 0, back = elementsToFlip - 1; front < back; front++, back--) {
 final int temp = array[front];
 array[front] = array[back];
 array[back] = temp;
 }
 }
 public static void main(final String[] args) {
 System.out.println(Arrays.toString(pancakeSort(new int[] { 1 })));
 System.out.println(Arrays.toString(pancakeSort(new int[] { 1, 2 })));
 System.out.println(Arrays.toString(pancakeSort(new int[] { 2, 1 })));
 System.out.println(Arrays.toString(pancakeSort(new int[] { 1, 2, 3 })));
 System.out.println(Arrays.toString(pancakeSort(new int[] { 2, 1, 3 })));
 System.out.println(Arrays.toString(pancakeSort(new int[] { 3, 1, 2 })));
 System.out.println(Arrays.toString(pancakeSort(new int[] { 3, 2, 1 })));
 System.out.println(Arrays.toString(pancakeSort(new int[] { 3, 2, 1, 8, 4, 6, 5, 10, 7, 9 })));
 }
}

• Anirudh Thatipelli: Thanks, @Eric Stein for your valuable comments on the code. I will keep these points in mind.

Answer 2

Eric has given some good points, though I would implement it differently, something like:

public static void pancakeSort(final int[] array) {
 for (int remainingToSort = array.length; remainingToSort >= 2; remainingToSort--) {
 int maxValue = array[0];
 int maxIndex = 0;
 for (int i = 1; i < remainingToSort; i++) {
 if (array[i] > maxValue) {
 maxValue = array[i];
 maxIndex = i;
 }
 }
 if (maxIndex != remainingToSort - 1) {
 // flip max to the top of the stack
 flip(array, maxIndex + 1);
 // flip max to the bottom of the remaining stack to sort
 flip(array, remainingToSort);
 }
 }
}

The reason for this is that now we only flip while it is necessary, because if the bottom of the remaining stack already contains the largest pancake, we do not need to flip. Meanwhile, we are also keeping the implementation clear: you first look for the largest pancake in the remaining to sort stack, move it to the top, and then to the bottom of the remaining stack. Using clear variable names makes it so other people can understand your implementation more easily (and even for yourself, if you would come back later).

• t3chb0t: Please explain your code and improvements you made. code dumps aren't reviews and are off-topic.
• Koekje: @MartinR I updated my answer with an explanation.
• Eric Stein: Definitely better than my version!