Skip to main content
Code Review

Return to Question

added 56 characters in body; edited title
Source Link
Jamal
Jamal
  • 35.2k
  • 13
  • 134
  • 238

pancake Pancake sort interview with pythonPython

I got asked this question during my interview. You You can find information about this question here: https://en.wikipedia.org/wiki/Pancake_sortinghere.

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

theThe following property of the flipping function - if we call flip(arr, k)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)flip(arr, k), and then shift it to the last place by calling flip(arr, arr.length - 1)flip(arr, arr.length - 1). We can exploit this method further, by iterating ii from arr.lengtharr.length - 1 to 1, finding the maximal element in the current i’thith 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 i’thith place in the array.

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]

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]

pancake sort interview with python

I got asked this question during my interview. You can find information about this question here: 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 i’th 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 i’th place in the array.

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]

Pancake sort interview with Python

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

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.

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]
Tweeted twitter.com/StackCodeReview/status/987996249038229504
Formatting
Source Link
301_Moved_Permanently
301_Moved_Permanently
  • 29.4k
  • 3
  • 49
  • 98

Pancake Sort

Pancake Sort

Given an array of integers arr:

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:

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]

input:  arr = [1, 5, 4, 3, 2]

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

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

i also ran my code against the following test cases

I also ran my code against the following test cases:

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

i also ran my code against the following test cases

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

I also ran my code against the following test cases:

Source Link
NinjaG
NinjaG
  • 2.6k
  • 2
  • 30
  • 61

pancake sort interview with python

I got asked this question during my interview. You can find information about this question here: https://en.wikipedia.org/wiki/Pancake_sorting

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 i’th 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 i’th 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]