146. LRU Cache
Think about the requirements, both get and put need O(1), which inevitably involves hash operations and remind us that the basic data structure must be a hash table.
Both how do we cope with eviction? When evicting an element, we must quickly find the oldest element. When querying an element, we should update its timestamp, making it the newest. These two requirements remind us that the elements must be (partially) ordered. Can we use heaps? No. Therefore, we must maintain the order of elements in constant time. Since all new elements must be the newest one, we can model these elements as a list, whose head is the oldest element and whose tail is the newest. Making arbitrary element in the middle of the list the newest can be achieved in constant time using linked list via a node transfer. But how do we locate the element? Hash.
In one word, we maintain a history. New elements will be appended to the end. Evictions will go to the head of the history. Querying will locate the history entry via hash and transfer the entry to the end of history.
