LRU Cache

Design a Least Recently Used (LRU) cache. Implement LRUCache(capacity) and: - get(key): Return value if key exists, else -1. Marks key as recently used. - put(key, value): Insert/update key. If over capacity, evict the least recently used key. Both operations must run in O(1) average time. DE Shaw Tier 1 — LC 146. Optimal: HashMap + Doubly Linked List. Map gives O(1) lookup. DLL gives O(1) move-to-front and evict-from-back. Talk-track: 'This is essentially the same eviction policy Redis uses for allkeys-lru. The DLL head is MRU, tail is LRU. On get/put, splice the node to the head. On capacity breach, remove from tail.'