LRU Cache

Design a cache with a fixed capacity. When the cache is full, it removes the least recently used key. The least recently used key is the key that nobody read or wrote for the longest time.

Write the class LRUCache with these operations:

LRUCache(capacity) creates an empty cache that holds at most capacity keys. get(key) returns the value of key, or -1 if the key is not in the cache. put(key, value) adds the key or changes its value.

If put adds a new key to a full cache, the cache first removes the least recently used key. A get or a put on a key makes it the most recently used key. Each operation must run in O(1) average time.