Amazon Interview Question

Implement a Stack. (of ints; push, pop, peek) Implement a method that returns the smallest integer in the stack. (min) Implement a method that returns the statistical mode of the stack. (mode) O(1) time for all.

Interview Answer

Anonymous

Jun 19, 2015

Basic Stack, used LinkedList Structure. (main stack) A stack that contains the minimum element at the top of the stack (min stack) Push - if the new element is smaller than or equal to the top of the min stack, push it onto the min stack. Pop - if the top of the stack is equal to the top of the min stack, pop the min stack. Min - get the data from the node on top of the min stack. A stack that contains the mode at the top of the stack and a Map that maps from the number to the count of that number in the main stack (mode stack, map) Push - increment the counter of the item in the map, if it's count is larger than the current mode's count, then push the number onto the mode stack. Pop - decrement the counter of the popped number in the map, pop the mode stack. Mode - get the data from the node on top of the mode stack. This is just a simplified overview of how I solved the problem, there's still more that could be done to make mode better, and there's a bunch of corner cases to watch out for when you code this up.