In today's post we look at a few more coding questions:
How do we convert a binary tree to a heap ?
There is a shortcut answer for this.
Remember that both can be serialized into arrays.
So we simply sort the array
Then we can deserialize them into the respective data structures.
In the case of the heap, the left and right nodes are at 2i and 2i+1
For the binary trees, the deserialization depends on whether the elements are listed in pre-order, inorder and postorder traversal.
Also, when we sort the array, remember that we can used different comparators.
We discuss the pancake problem next.
The pancake problem has a stack of n pancakes each with a different diameter. When you flip the pancakes, you can flip more than one by inserting your pancake flipper at any level into the stack and reversing it. The question is how many flips will it take to sort all the pancakes by size with the bottom pancake being the largest. We are looking for something that will work for in most cases of different orders of pancakes.
The first thing to observe here is that this is way different from sorting. In sorting we can exchange elements in a collection. This is not the same for this pancake stack where we must lift all the pancakes above the point where we insert the pancake flipper.
Consider three cases for the largest pancake.
If the largest pancake is already at the bottom, we don't need to do anything.
If the largest pancake is at the top, we flip the entire stack so the largest one lands at the bottom.
If the largest pancake is in the middle, we split the stack at that point. Put the pancake at the top of one stack and then invert it.
Because the pancakes at the bottom are unaffected by the flips above, we proceed from bottom to top in this way.
Since it takes two flips for the bottom pancake, we can assume that this takes the same number of flips for each pancake resulting in 2n-2 flips in worst case.
The pancakes problem has an interesting history. Bill Gates published a paper that was the most efficient for almost 30 years [Courtesy programming interviews exposed book]
How do we convert a binary tree to a heap ?
There is a shortcut answer for this.
Remember that both can be serialized into arrays.
So we simply sort the array
Then we can deserialize them into the respective data structures.
In the case of the heap, the left and right nodes are at 2i and 2i+1
For the binary trees, the deserialization depends on whether the elements are listed in pre-order, inorder and postorder traversal.
Also, when we sort the array, remember that we can used different comparators.
We discuss the pancake problem next.
The pancake problem has a stack of n pancakes each with a different diameter. When you flip the pancakes, you can flip more than one by inserting your pancake flipper at any level into the stack and reversing it. The question is how many flips will it take to sort all the pancakes by size with the bottom pancake being the largest. We are looking for something that will work for in most cases of different orders of pancakes.
The first thing to observe here is that this is way different from sorting. In sorting we can exchange elements in a collection. This is not the same for this pancake stack where we must lift all the pancakes above the point where we insert the pancake flipper.
Consider three cases for the largest pancake.
If the largest pancake is already at the bottom, we don't need to do anything.
If the largest pancake is at the top, we flip the entire stack so the largest one lands at the bottom.
If the largest pancake is in the middle, we split the stack at that point. Put the pancake at the top of one stack and then invert it.
Because the pancakes at the bottom are unaffected by the flips above, we proceed from bottom to top in this way.
Since it takes two flips for the bottom pancake, we can assume that this takes the same number of flips for each pancake resulting in 2n-2 flips in worst case.
The pancakes problem has an interesting history. Bill Gates published a paper that was the most efficient for almost 30 years [Courtesy programming interviews exposed book]
No comments:
Post a Comment