LRU, LFU, then a pluggable eviction policy

Implement LRUCache(capacity) (capacity >= 1) with O(1) operations:

• get(key) -> int: the stored value, or -1 if the key is missing. A hit makes the key the most recently used.
• put(key, value) -> None: insert or overwrite, and make the key the most recently used. If a new key would push the size above capacity, first evict the least recently used key.

c = LRUCache(2)
c.put(1, 10); c.put(2, 20)
c.get(1)        # 10
c.put(3, 30)    # evicts 2
c.get(2)        # -1

Use a dict plus a doubly linked list (or OrderedDict if you already know how to write the list). Later levels build on this, so keep the "which key is next to evict" bookkeeping separate from the key-to-value storage.