LRU Cache

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) Cache.

An LRU Cache evicts the least recently used item when the cache reaches its capacity. An item is considered "used" whenever it is accessed via get or updated/inserted via put.

Operations

Implement the LRUCache class with the following methods:

• LRUCache(capacity) — Initialize the cache with a positive integer capacity.
• get(key) — Return the value of the key if it exists in the cache, otherwise return -1. This operation marks the key as recently used.
• put(key, value) — Insert or update the key-value pair. If the key already exists, update its value and mark it as recently used. If the cache is at full capacity, evict the least recently used key before inserting the new key.

All operations must run in O(1) average time complexity.

Input / Output Format

You will receive a list of operations and their arguments:

• operations: a list of strings representing method calls (e.g., ["LRUCache", "put", "get", ...])
• arguments: a list of argument lists corresponding to each operation

Return a list of results for each operation. The constructor (LRUCache) returns null.

Examples

Example 1

Operations: ["LRUCache","put","put","get","put","get","put","get","get","get"]
Arguments: [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output: [null,null,null,1,null,-1,null,-1,3,4]

Explanation:

• LRUCache(2) — capacity = 2
• put(1,1) — cache: {1:1}
• put(2,2) — cache: {1:1, 2:2}
• get(1) → 1 — cache: {2:2, 1:1} (1 is now most recent)
• put(3,3) — capacity exceeded, evict key 2 (LRU) → cache: {1:1, 3:3}
• get(2) → -1 (key 2 was evicted)
• put(4,4) — evict key 1 (LRU) → cache: {3:3, 4:4}
• get(1) → -1, get(3) → 3, get(4) → 4

Approach Hints

• To achieve O(1) for both and , consider combining a (for O(1) lookup) with a (for O(1) insertion and deletion of any node).