LRU Cache

A cache keeps a limited number of items close at hand. When it is full and a new item arrives, a least recently used (LRU) cache throws out the item that has gone unused the longest.

Build an LRUCache class:

• LRUCache(capacity) makes an empty cache that holds at most capacity items.
• get(key) returns the value stored for key, or -1 if it is not in the cache. A successful get counts as a use of that key.
• put(key, value) stores value under key (replacing any old value) and counts as a use of that key. If the cache now holds more than capacity items, remove the least recently used one.

Examples

c = LRUCache(2)
c.put(1, 'one')
c.put(2, 'two')
c.get(1)            # returns 'one'    (now 2 is the least recently used)
c.put(3, 'three')   # too many items: 2 is removed
c.get(2)            # returns -1
c.get(3)            # returns 'three'

Constraints

• 1 <= capacity <= 1,000
• Up to 20,000 calls, and each get or put should take about the same time however full the cache is