LRU Cache with TTL or Weighted Size

Implement an LRU-style cache, then handle production follow-ups such as TTL expiration, per-item size, or evicting multiple entries to stay within capacity. Requirements Design and implement a cache class. The base API is usually some combination of: class Cache: def get(self, key): ... def put(self, key, value): ... Expected behavior: get returns the value if present and not expired; otherwise it returns a miss. put inserts or updates a key and marks it as most recently used. When capacity is exceeded, evict least-recently-used entries. If TTL is included, expired entries must not be returned. If item sizes vary, total cache size is a budget and one insertion may evict multiple old entries. Notes The standard answer is a hash map from key to doubly-linked-list node plus a list ordered by recency. get and put both move the node to the most-recent end. Eviction removes from the least-recent end until the capacity invariant is restored. For TTL, store an expiry timestamp per node. A simple interview implementation can lazily delete expired nodes on get and before eviction; a stronger version also keeps a min-heap or timing wheel for eager cleanup. For weighted size, track current_size, subtract evicted node sizes, and reject or special-case a single item larger than capacity. Concurrency follow-up: protect map and list mutations together. A read-write lock only helps if reads do not mutate recency; true LRU get mutates state, so it still needs write coordination or a relaxed approximate-LRU design. Preparation Implement LRUCache with a sentinel head and tail so remove / insert operations are constant time. Add a TTL variant and tests where expired keys are still physically present in the map. Add a weighted-capacity variant where inserting a large item evicts several old items. Be ready to explain why OrderedDict is fine in production but an interview may require the linked-list internals.