I was having an intervew at Twitter several months ago and I was asked to develop a data structure that have

add(key, value)

remove(key, value)

getLast()

Looks easy, but we need to make all operations in O(1)

I immediately suggested to use HashMap and LinkedList, so removing will be easy. But removing from LinkedList would've cost us O(n), right?

I was very confused. What was the right answer?