Pregunta de entrevista de Amazon

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.

Respuesta de la entrevista

Anónimo

19 de jun de 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.