Implement LRU Cache.

Your program is running slowly because it's accessing data from disk over and over again. To improve the performance, you want to build a simple key-value store to cache this data in memory, but you also want to limit the amount of memory used. You decide to build a caching system that only keeps the N most recently used items—also known as a least recently used (LRU) cache.

Write a class LRUCache(n) that accepts a size limit n. It should support a set(key, value) method for inserting or updating items and a get(key) method for retrieving items. Can you implement a solution where both of these methods run in O(1) time?

Python
class LRUCache(n):
  set(key, value)
  get(key)

Examples

To make room for new items, the least recently used item should be removed. An item is 'used' whenever it is set, retrieved, or updated.

Python
cache = LRUCache(2) # Limit of 2 items

cache.set('user1', 'Alex')
cache.set('user2', 'Brian')
cache.set('user3', 'Chris')

Here user1 is empty because it was the least recently used and thus removed to make room for user3:

Python
cache.get('user1') # => None
cache.get('user2') # => 'Brian'
cache.get('user3') # => 'Chris'