LRU Cache

Design a data structure for a least recently used (LRU) cache with a fixed capacity.

Implement the class LRUCache:

• LRUCache(capacity) creates an empty cache that can hold at most capacity keys (capacity is positive).
• get(key) returns the value stored for key, or -1 if key is not in the cache. A successful get counts as a use of key.
• put(key, value) stores value under key, overwriting any existing value, and counts as a use of key. If adding a new key makes the cache hold more than capacity keys, first remove the least recently used key (the one whose last get or put is oldest). Updating an existing key never evicts anything.

Both get and put should run in O(1) average time.

In the examples, each line is a call and the output lists what each call returns (None for the constructor and put).