I got asked this question during my interview. You can find information about this question here.
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
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
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:  Expected:  Actual:  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]