IMG Interview Question
ConsultantsThis is tower of hanoi problem.
suppose we name the 3 vertical bar as name A , B , C. then the algo goes like this,
Honoi(n , source , dest , by)
{
if (n=1) then
writeln('Move the plate from ', source, ' to ', dest)
else begin
Hanoi(n-1, source, by, dest);
Hanoi(1, source, dest, by);
Hanoi(n-1, by, dest, source);
}
LOL.
Anytime you see a vertical pole, you start moving plates as in the tower of hanoi problem?
Tower of Hanoi will have to be modified slightly to give you the answer to this question. Read the question carefully. The ordering on the vertical bar is random. The expected result is that the largest pizza should be at the bottom. You don't care about the rest. My assumption is that the "large bar" is probably a stack because you cant get to any pizza without removing the pizzas above it. So you can do this is O(n) time using a temporary array of size n-1.
"modified slightly"? LOL.
Tower of hanoi has a restriction that you cannot place a larger disk on top of a smaller disk. That isn't the case here. Frankly, and sorry to be saying this, but... anyone who thinks this is the tower of hanoi problem, is either stupid or ignorant.
Anyway, the question is itself unclear.
Engineering approach ..
find if the largest pizza is at the bottom. If yes then no need to sort else lift the largest pizaa and other pizzas on top of it and place it aside. Now lift the left over pizzas and place it on top of the pizzas that you have just kept aside. Now place all the pizzas on the bar.
It is as good as changing the pointers & making the largest value the last node in a linked list.
Management approach....
If you want to act like a smart A**.... leave only the last pizza on the bar and carry the others home or sell them off. The pizza that is left on the bar may be the largest or may be smallest now the comparison is no more possible.
This is as good as eliminating the competition by taking over a company breaking it into chunks & selling it so that the competition is eliminated and you make profit out of this take over.
Think of sorting a double ended queue.
- Lord Darth Plagueis June 19, 2009I do not know - exactly how you do it - sort a double ended queue - using only push_back() and push_front() and pop_back() and pop_front() - but then that is the abstraction you are dealing with here.
Search BING to find more - could not resist naming BING