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]

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.

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.