Max stack
Design a stack that also supports peekMax() and popMax() (removing the top-most copy of the largest value), along with push, pop and top. Compare a two-stack design with a doubly linked list plus a sorted map or heap, and give each operation's cost.
MetaTechnical phone screenNo answer yet. Write the first one; the best answer gets endorsed.