Pancake sort inteview using java
Clash 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:
Can I further improve my space and time complexity?
Is there any other alternative, smarter way to attempt this question?
Any grave coding convention that I have violated in my code?
Reference
java programming-challenge sorting interview-questions complexity
add a comment |Â
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:
Can I further improve my space and time complexity?
Is there any other alternative, smarter way to attempt this question?
Any grave coding convention that I have violated in my code?
Reference
java programming-challenge sorting interview-questions complexity
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 useflip(arr, k)
but you implementedflip(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
add a comment |Â
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:
Can I further improve my space and time complexity?
Is there any other alternative, smarter way to attempt this question?
Any grave coding convention that I have violated in my code?
Reference
java programming-challenge sorting interview-questions complexity
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:
Can I further improve my space and time complexity?
Is there any other alternative, smarter way to attempt this question?
Any grave coding convention that I have violated in my code?
Reference
java programming-challenge sorting interview-questions complexity
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 useflip(arr, k)
but you implementedflip(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
add a comment |Â
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 useflip(arr, k)
but you implementedflip(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
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
Flip
Use better variable names.
i
andj
are harder to read than something likefront
andback
.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
andmaxPos
are not sufficiently descriptive. Don't usec
as an array index. Either usej
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 )));
Thanks, @Eric Stein for your valuable comments on the code. I will keep these points in mind.
â Anirudh Thatipelli
May 1 at 18:53
add a comment |Â
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).
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
add a comment |Â
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
andj
are harder to read than something likefront
andback
.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
andmaxPos
are not sufficiently descriptive. Don't usec
as an array index. Either usej
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 )));
Thanks, @Eric Stein for your valuable comments on the code. I will keep these points in mind.
â Anirudh Thatipelli
May 1 at 18:53
add a comment |Â
up vote
2
down vote
accepted
Flip
Use better variable names.
i
andj
are harder to read than something likefront
andback
.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
andmaxPos
are not sufficiently descriptive. Don't usec
as an array index. Either usej
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 )));
Thanks, @Eric Stein for your valuable comments on the code. I will keep these points in mind.
â Anirudh Thatipelli
May 1 at 18:53
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Flip
Use better variable names.
i
andj
are harder to read than something likefront
andback
.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
andmaxPos
are not sufficiently descriptive. Don't usec
as an array index. Either usej
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 )));
Flip
Use better variable names.
i
andj
are harder to read than something likefront
andback
.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
andmaxPos
are not sufficiently descriptive. Don't usec
as an array index. Either usej
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 )));
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
add a comment |Â
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
add a comment |Â
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).
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
add a comment |Â
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).
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
add a comment |Â
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).
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).
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
add a comment |Â
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
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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 implementedflip(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