Problem

In a Meta-style system such as Facebook Feed, recently accessed items are often kept in a fixed-size cache. Design and implement an LRU (Least Recently Used) cache that supports get and put in O(1) average time.

You must implement a cache with a fixed positive capacity:

1. get(key) returns the value associated with key if it exists, otherwise returns -1.
2. put(key, value) inserts or updates the key-value pair.
3. When inserting a new key would exceed capacity, evict the least recently used key.
4. Any successful get or put on an existing key makes that key the most recently used.

Formal Specification

Implement a class LRUCache with:

• LRUCache(capacity: int)
• get(key: int) -> int
• put(key: int, value: int) -> None

Use integer keys and values.

Examples

Example 1:

• Input: capacity = 2, operations = [put(1,1), put(2,2), get(1), put(3,3), get(2)]
• Output: [null, null, 1, null, -1]
• Explanation: 1 becomes recently used after get(1), so key 2 is evicted when key 3 is inserted.

Example 2:

• Input: capacity = 1, operations = [put(1,10), put(2,20), get(1), get(2)]
• Output: [null, null, -1, 20]
• Explanation: The cache can store only one key, so inserting 2 evicts 1.

Constraints

• 1 <= capacity <= 3000
• 0 <= key, value <= 10^9
• At most 2 * 10^5 calls to get and put
• get and put should run in O(1) average time