Pancake sort inteview using java

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
0
down vote

favorite












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







share|improve this question





















  • For the record: pancake sort boils down to being a highly inefficient selection sort. The time-complexity will be n^2 * n :(
    – Vogel612♦
    May 1 at 9:29










  • 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.
    – Anirudh Thatipelli
    May 1 at 9:33










  • 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?
    – Duarte Meneses
    May 1 at 11:46










  • I redefined the function slightly to suit my needs
    – Anirudh Thatipelli
    May 1 at 14:41






  • 1




    But then it does not seem like a real pancake sort, you can not flip a stack of pancakes underneath another stack of pancakes.
    – Koekje
    May 1 at 14:52

















up vote
0
down vote

favorite












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







share|improve this question





















  • For the record: pancake sort boils down to being a highly inefficient selection sort. The time-complexity will be n^2 * n :(
    – Vogel612♦
    May 1 at 9:29










  • 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.
    – Anirudh Thatipelli
    May 1 at 9:33










  • 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?
    – Duarte Meneses
    May 1 at 11:46










  • I redefined the function slightly to suit my needs
    – Anirudh Thatipelli
    May 1 at 14:41






  • 1




    But then it does not seem like a real pancake sort, you can not flip a stack of pancakes underneath another stack of pancakes.
    – Koekje
    May 1 at 14:52













up vote
0
down vote

favorite









up vote
0
down vote

favorite











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







share|improve this 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









share|improve this question












share|improve this question




share|improve this question








edited May 1 at 18:36









200_success

123k14142399




123k14142399









asked May 1 at 6:27









Anirudh Thatipelli

227211




227211











  • For the record: pancake sort boils down to being a highly inefficient selection sort. The time-complexity will be n^2 * n :(
    – Vogel612♦
    May 1 at 9:29










  • 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.
    – Anirudh Thatipelli
    May 1 at 9:33










  • 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?
    – Duarte Meneses
    May 1 at 11:46










  • I redefined the function slightly to suit my needs
    – Anirudh Thatipelli
    May 1 at 14:41






  • 1




    But then it does not seem like a real pancake sort, you can not flip a stack of pancakes underneath another stack of pancakes.
    – Koekje
    May 1 at 14:52

















  • For the record: pancake sort boils down to being a highly inefficient selection sort. The time-complexity will be n^2 * n :(
    – Vogel612♦
    May 1 at 9:29










  • 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.
    – Anirudh Thatipelli
    May 1 at 9:33










  • 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?
    – Duarte Meneses
    May 1 at 11:46










  • I redefined the function slightly to suit my needs
    – Anirudh Thatipelli
    May 1 at 14:41






  • 1




    But then it does not seem like a real pancake sort, you can not flip a stack of pancakes underneath another stack of pancakes.
    – Koekje
    May 1 at 14:52
















For the record: pancake sort boils down to being a highly inefficient selection sort. The time-complexity will be n^2 * n :(
– Vogel612♦
May 1 at 9:29




For the record: pancake sort boils down to being a highly inefficient selection sort. The time-complexity will be n^2 * n :(
– Vogel612♦
May 1 at 9:29












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.
– Anirudh Thatipelli
May 1 at 9:33




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.
– Anirudh Thatipelli
May 1 at 9:33












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?
– Duarte Meneses
May 1 at 11:46




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?
– Duarte Meneses
May 1 at 11:46












I redefined the function slightly to suit my needs
– Anirudh Thatipelli
May 1 at 14:41




I redefined the function slightly to suit my needs
– Anirudh Thatipelli
May 1 at 14:41




1




1




But then it does not seem like a real pancake sort, you can not flip a stack of pancakes underneath another stack of pancakes.
– Koekje
May 1 at 14:52





But then it does not seem like a real pancake sort, you can not flip a stack of pancakes underneath another stack of pancakes.
– Koekje
May 1 at 14:52











2 Answers
2






active

oldest

votes

















up vote
2
down vote



accepted










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







share|improve this answer





















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

















up vote
1
down vote













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






share|improve this answer























  • Please explain your code and improvements you made. code dumps aren't reviews and are off-topic.
    – t3chb0t
    May 1 at 18:45






  • 1




    @MartinR I updated my answer with an explanation.
    – Koekje
    May 1 at 19:31






  • 1




    Definitely better than my version!
    – Eric Stein
    May 1 at 23:25










Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);








 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f193325%2fpancake-sort-inteview-using-java%23new-answer', 'question_page');

);

Post as a guest






























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
2
down vote



accepted










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







share|improve this answer





















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














up vote
2
down vote



accepted










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







share|improve this answer





















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












up vote
2
down vote



accepted







up vote
2
down vote



accepted






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







share|improve this answer













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








share|improve this answer













share|improve this answer



share|improve this answer











answered May 1 at 16:27









Eric Stein

3,703512




3,703512











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
















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















Thanks, @Eric Stein for your valuable comments on the code. I will keep these points in mind.
– Anirudh Thatipelli
May 1 at 18:53




Thanks, @Eric Stein for your valuable comments on the code. I will keep these points in mind.
– Anirudh Thatipelli
May 1 at 18:53












up vote
1
down vote













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






share|improve this answer























  • Please explain your code and improvements you made. code dumps aren't reviews and are off-topic.
    – t3chb0t
    May 1 at 18:45






  • 1




    @MartinR I updated my answer with an explanation.
    – Koekje
    May 1 at 19:31






  • 1




    Definitely better than my version!
    – Eric Stein
    May 1 at 23:25














up vote
1
down vote













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






share|improve this answer























  • Please explain your code and improvements you made. code dumps aren't reviews and are off-topic.
    – t3chb0t
    May 1 at 18:45






  • 1




    @MartinR I updated my answer with an explanation.
    – Koekje
    May 1 at 19:31






  • 1




    Definitely better than my version!
    – Eric Stein
    May 1 at 23:25












up vote
1
down vote










up vote
1
down vote









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






share|improve this answer















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







share|improve this answer















share|improve this answer



share|improve this answer








edited May 1 at 19:30


























answered May 1 at 18:28









Koekje

1,017211




1,017211











  • Please explain your code and improvements you made. code dumps aren't reviews and are off-topic.
    – t3chb0t
    May 1 at 18:45






  • 1




    @MartinR I updated my answer with an explanation.
    – Koekje
    May 1 at 19:31






  • 1




    Definitely better than my version!
    – Eric Stein
    May 1 at 23:25
















  • Please explain your code and improvements you made. code dumps aren't reviews and are off-topic.
    – t3chb0t
    May 1 at 18:45






  • 1




    @MartinR I updated my answer with an explanation.
    – Koekje
    May 1 at 19:31






  • 1




    Definitely better than my version!
    – Eric Stein
    May 1 at 23:25















Please explain your code and improvements you made. code dumps aren't reviews and are off-topic.
– t3chb0t
May 1 at 18:45




Please explain your code and improvements you made. code dumps aren't reviews and are off-topic.
– t3chb0t
May 1 at 18:45




1




1




@MartinR I updated my answer with an explanation.
– Koekje
May 1 at 19:31




@MartinR I updated my answer with an explanation.
– Koekje
May 1 at 19:31




1




1




Definitely better than my version!
– Eric Stein
May 1 at 23:25




Definitely better than my version!
– Eric Stein
May 1 at 23:25












 

draft saved


draft discarded


























 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f193325%2fpancake-sort-inteview-using-java%23new-answer', 'question_page');

);

Post as a guest













































































Popular posts from this blog

Chat program with C++ and SFML

Function to Return a JSON Like Objects Using VBA Collections and Arrays

Will my employers contract hold up in court?