LRU Cache

Design a data structure that implements a Least Recently Used (LRU) cache with a fixed capacity.

The cache stores key-value pairs and must support two operations, both of which should run in constant time on average:

• get(key) — return the value associated with key, or -1 if the key is not present. Accessing a key this way counts as using it, so it becomes the most recently used entry.
• put(key, value) — insert or update the value for key. This also counts as using the key. If inserting a new key would push the cache past its capacity, evict the least recently used entry first before adding the new one.

You must implement a class named LRUCache with:

• LRUCache(int capacity) — initializes the cache with a positive maximum capacity.
• int get(int key) — described above.
• void put(int key, int value) — described above.

Rules to keep in mind:

• Both get and put must run in O(1) time.
• Updating the value of an existing key via put also refreshes its recency — it should not be treated as a new insertion for eviction purposes.
• When eviction is required, exactly one entry — the one that has gone the longest without being read or written — is removed.

Examples

Example 1:

Input:

LRUCache cache = new LRUCache(2);
cache.put(1, 10);
cache.put(2, 20);
cache.get(1);      // returns 10
cache.put(3, 30);  // evicts key 2
cache.get(2);      // returns -1
cache.put(4, 40);  // evicts key 1
cache.get(1);      // returns -1
cache.get(3);      // returns 30
cache.get(4);      // returns 40

Output: [null, null, null, 10, null, -1, null, -1, 30, 40]

Explanation:

• After the two put calls, the cache holds keys 1 and 2, with 2 being more recently used.
• Calling get(1) returns 10 and makes 1 the most recently used, leaving 2 as the least recently used.
• put(3, 30) needs to add a new key while the cache is full, so it evicts key 2.
• get(2) then correctly returns -1 since that key was just evicted.
• put(4, 40) again forces an eviction; at this point key 1 is the least recently used (key 3 was just inserted), so key 1 is evicted.
• The remaining get calls confirm the final state: key 1 is gone, keys 3 and 4 remain with their original values.

Example 2:

Input:

LRUCache cache = new LRUCache(1);
cache.put(7, 100);
cache.get(7);      // returns 100
cache.put(8, 200); // evicts key 7 since capacity is 1
cache.get(7);      // returns -1
cache.get(8);      // returns 200

Output: [null, null, 100, null, -1, 200]

Explanation:

• With a capacity of 1, inserting any second key immediately evicts whatever key was already stored, regardless of how recently it was used.

Constraints

• 1 <= capacity <= 3000
• 0 <= key, value <= 10^5
• At most 2 * 10^5 total calls will be made to get and put combined.
• Keys passed to put may already exist in the cache, in which case the value should simply be overwritten and the entry marked as most recently used.