Hi everyone,
I had this problem on my interview with Bloomberg. It is easily solved in O(N), but it is required to solve it in O(1) (all following functions).

Build your own data structure which does the following functions:

1. add(integer) -> add a new integer.
2. getAll() -> return all elements in same insertion order.
3. deleteLast() -> delete the last inserted element.
4. getMaximum() -> return the maximum value of all elements.
5. getMaximumNeighbourValues() -> return the maximum value of two consecutive elements.

Example:
[7, 3, 1, 10]: maxValue=10, maxNeighborsValue=11
deleteLast -> [7, 3, 1]: maxValue=7, maxNeighborsValue=10
add(2) -> [7, 3, 1, 2]: maxValue=7, maxNeighborsValue=10
add(8) -> [7, 3, 1, 2, 8]: maxValue=8, maxNeighborsValue=10

Solution:
I came up to solve to first four functions in O(1). I used an arrayList to store the elements (to keep its order while insertion), and I used a LinkedHashMap to store the element as a key, and its occurrences as a value (that way, I kept the order to see which element is deleted, and I kept if maximum value should be modified -> takes the second last element in the map). That way, all functions have complexity O(1).

But the fifth function is still unclear for me!