Implement an LRU Cache with Constant-Time Operations

Implement an LRU cache with a positive capacity. get(key) returns the stored value and makes that entry most recently used, or returns -1 if absent. put(key,value) inserts or updates an entry and makes it most recently used; if capacity is exceeded, evict the least recently used entry. Both operations must take O(1) average time. ### Constraints and Clarifications The report identifies problem146. The [official LRU Cache reference](https://leetcode.com/problems/lru-cache/description/) supplies practice bounds of capacity 1–3000, keys 0–10000, values 0–100000, and at most 200000 operations. These are reference-context constraints, not separately recalled interview bounds. A missing get does not change recency. For a serialized operation-list interface, emit null for construction and put, and the integer result for get. ### Example With capacity 2: put(1,10), put(2,20), get(1), put(3,30), get(2) produces get results 10 and -1. Accessing key1 made key2 the eviction candidate. ### What a Strong Answer Covers Combine key lookup with constant-time recency updates, maintain consistent map/list membership, and handle updates without adding duplicate nodes or unnecessarily evicting another entry. ### Follow-up Questions - Why is a singly linked list insufficient for removing an arbitrary accessed node in constant time without more information? - What additional coordination would concurrent callers require?