Pancake sort interview with Python

Question

I got asked this question during my interview. You can find information about this question here.

Pancake Sort

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]

Note: it’s called pancake sort because it resembles sorting pancakes on a plate with a spatula, where you can only use the spatula to flip some of the top pancakes in the plate. To read more about the problem, see the Pancake Sorting Wikipedia page. https://en.wikipedia.org/wiki/Pancake_sorting

My solution is to use flip function to implement my pancake_sort(arr).

The following property of the flipping function - if we call flip(arr, k), then the previous k-th element in the array is now the first element. Hence, if we find the maximal element, we can shift it to be the first element by one call to flip(arr, k), and then shift it to the last place by calling flip(arr, arr.length - 1). We can exploit this method further, by iterating i from arr.length - 1 to 1, finding the maximal element in the current ith prefix, flipping the maximal element once to move it to the first place in the array, and a second time to put it in the ith place in the array.

def flip(arr, i):
 # reverse arr[0...i]
 start = 0
 while start < i:
 temp = arr[start]
 arr[start] = arr[i]
 arr[i] = temp
 start += 1
 i -= 1
def pancake_sort(arr):
 # the main function that complete sorting
 # start from the array and one by one reduce the current size
 output = []
 curr_size = len(arr) - 1
 # find the index of the maxmium element inside the arr[0..curr_size -1]
 while curr_size > 0:
 mi = findMaxUpTo(arr, curr_size)
 if mi != curr_size:
 flip(arr, mi)
 # once I flip it
 # now move the maximum number to the end by reversing current array
 flip(arr, curr_size)
 curr_size -= 1
 return arr
def findMaxUpTo(arr, rightBound):
 best_index = 0
 max_val = None
 for i in range(rightBound + 1):
 if arr[i] > max_val:
 best_index = i
 max_val = arr[i]
 return best_index

I also ran my code against the following test cases:

Test Case #1
Input: [1]
Expected: [1]
Actual: [1] 
Test Case #2
Input: [1,2],Expected: [1,2],
Actual: [1, 2]
Test Case #3
Input: [1,3,1],
Expected: [1,1,3],Actual: [1, 1, 3]
Test Case #4
Input: [3,1,2,4,6,5],
Expected: [1,2,3,4,5,6],
Actual: [1, 2, 3, 4, 5, 6]
Test Case #5
Input: [10,9,8,7,6,5,4,3,2,1],
Expected: [1,2,3,4,5,6,7,8,9,10],
Actual: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Test Case #6
Input: [10,9,8,6,7,5,4,3,2,1,9,10,8,7,6,5,4,3,2,1,10,9,8,7,6,5,4,3,2,1],
Expected: [1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9,10,10,10],
Actual: [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10]

• Evpok: Side note: this is much easier to write with recursion, since flipping does not alter the bottom of the array.

Answer 1

flip

For starter, you can swap two variables in Python without using a temporary one:

>>> a = 3
>>> b = 5
>>> a, b = b, a
>>> print(a, b)
5 3

But above all, this function is better implemented using slices:

def flip(arr, i):
 arr[:i] = reversed(arr[:i])

Or

def flip(arr, i):
 arr[:i] = arr[i-1::-1]

findMaxUpTo

Same here, slices and builtin functions can go a long way into simplifying the code. A "max" function that doesn't use the max builtin feels wrong to me.

A naïve rewrite would be:

def findMaxUpTo(arr, i):
 val = max(arr[:i])
 return arr.index(val)

It is good for now. But a better rewrite would make use of enumerate and the key argument of max. Possibly involving operator.itemgetter in the process and itertools.takewhile to avoid copying the array.

pancake_sort

Not much to add here, except a note on your return value. Since you are mutating the array in-place, there is absolutely no reason to return a value. Once you call the function on an array, it will be sorted and all previous references to this array will now hold the sorted version. Returning a value can mislead the users that the original array remain untouched, which is false.

Similarly, you never make use of the output variable.

miscelaneous

Your naming style is inconsistent and some variable names don't convey much meaning, please fix it.

• JAD: Regarding your feedback on findMaxUpTo, I think the reason for this is that in the current implementation, you would only have to traverse the list once, since you keep a running maximum. This should be more efficient than your suggestion, which does it once in max and once in index. Then again, I'm not sure if efficiency really is the most important in this algorithm.
• 301_Moved_Permanently: @JAD yes that's why using max(enumerate(arr[:i]), key=operator.itemgetter(1)) or something is better as it traverse the list once.
• JollyJoker: Doesn't arr.index(val) give the wrong result when you have duplicates? You should find the last index that matches.
• 301_Moved_Permanently: @JollyJoker if you look closely at the original code, the > makes it find the index of the first maximum element. In any case, it doesn't matter much as all identical elements will be found sooner or later.
• JollyJoker: @MathiasEttinger Of course; the next iteration doesn't start from where the max was found, but would include any duplicates. My mistake.

Answer 2

@MathiasEttinger gave some good tips on using Python features to simplify the code, preserving the algorithm.

Your algorithm itself is good, achieving \$ O(n^2)\$ complexity on both comparisons and data movement, which I think is about as good as you can get within the arbitrary constraints. Nobody is likely to use a pancake sort for real work; an ordinary selection sort moves less data with the same number of comparisons, and heapsort does better on both metrics.

The one algorithmic improvement I can think of is to make the sort adaptive, that is, to take less time on sorted or partially sorted data than it does on random data. For this, you could keep track of the last time the new value was less than the saved maximum during your find-max search. This gives you the portion of the end of the array that's already sorted - which will be zero-length if you needed to do any flips on that pass. So, if you didn't need to flip, set the new end-pointer to the last decreasing element instead of just decrementing it.

• Billal BEGUERADJ: Good you mentioned the complexity because that is one of the most relevant parts when discussing an algorithm
• Maxim: Actually, you could think of real-world examples where this sort could be useful; i.e. when sorting pancakes stacked vertically with gravity using only your spatula ;)
• yo': @Maxim Python + Spatula = Robotics.SE :)