Pergunta de entrevista da empresa Amazon
design a ADT to implement push(), pop() method as stack, and also has a getMinElement(). Require that getMinElement() is constant time but push()/pop() do not have to be constant time at first. Then for improvement, these three methods are all required to be constant time
Respostas da entrevista
For the first half, a minheap is enough. For the second half, use two stacks, the second stack store the min value.
Having a push and pop done in constant time strongly implies a linked list structure. The getMinElement seems like a red herring to get you thinking minheap. In reality if it's just a linked list you can easily keep a pointer to the node that currently has the lowest value element (or the prior node if getMinElement implies removal from the linked list).
second part isn't theoretically possible .. sounds like the question was mis quoted.
Say you have a trillion numbers. You can't push a random number to that list of numbers in constant time and still be able to always get the minValue .. at a minimum you need to do logN insert into a minheap.
well, ok, I suppose you might be able to do something if you knew the range of numers before hand. that's not exactly ADT though.
even then, it would be o(range of numbers) .. that's not exactly constant time given that integers can get rather large. Often larger than the actually length of the stack you're popping/pushing from.
also a minheap isn't enough for the first part. minheap doesn't retain fifo you need for stack.