September 19th, 2013, 12:43 AM
Optimal Algorithm (Puzzle 2)
At a restaurant there is a chef and his job is to cook pancakes. The problem is that he is not a good cook and as a result all the pancakes he creates are of different sizes. Now when the waiter is delivering these to the customers, he rearranges them in such a way so that the smallest one ends up at the top and the largest one at the bottom (smallest to biggest). He uses a spatula to do that. Currently the only thing that he can do to achieve that, is to grab several pancakes from the top and then flip them over so that the top pancake arrives at the bottom of the stack. The waiter can do this as many times as he wants.
The problem is to come up with an algorithm that will solve this problem i.e. after doing all that flipping, the pancakes should be sorted (smallest at the top of the stack and largest at the bottom of the stack).
I am not sure if there is a O (n^2) algorithm for this.
Tags for this Thread
Click Here to Expand Forum to Full Width