Pancake sort interview with Python 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 &lt; 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 &gt; 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] &gt; 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]
flip

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

&gt;&gt;&gt; a = 3
&gt;&gt;&gt; b = 5
&gt;&gt;&gt; a, b = b, a
&gt;&gt;&gt; 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.