[Leetcode] LRU Cache

Problem 

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:

• get(key),  get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
• set(key, value), set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate (delete) the least recently used item before inserting a new item.

The get and set operations should have O(1) running time. 

Algorithm

Hash table is a good choice for O(1) read and write. We still need a data structure to efficiently track the usage frequency of each data. We may use a priority queue. Although get the least recently used data from the priority queue has a O(1) time, deleting it needs O(log(n)) time. 

We can use a doubly linked list to