OA: LRU cache with TTL and weighted size

Build Cache(capacity), where capacity >= 1:

• get(key) returns the stored value, or None on a miss. A hit makes the key the most recently used.
• put(key, value) inserts or overwrites the key and makes it the most recently used. If the cache now holds more than capacity keys, it drops the least recently used one.

Both must be O(1). A dict plus a doubly linked list with sentinel nodes is the classic answer. OrderedDict is allowed, but write the list yourself if you want the interview practice. Keys are hashable and values are anything except None.

c = Cache(2)
c.put("a", 1); c.put("b", 2)
c.get("a")        # 1  ("b" is now least recent)
c.put("c", 3)     # drops "b"
c.get("b")        # None