Problem

Implement an LRU (Least Recently Used) cache with capacity capacity. The cache supports get(key) and put(key, value) operations. get returns the value for key if present, otherwise -1. put inserts or updates a key; if the cache exceeds capacity, evict the least recently used key. Both operations must run in average O(1) time.

Examples

Example 1:

Input:
capacity = 2
operations = ["put", "put", "get", "put", "get", "get"]
arguments = [[1, 10], [2, 20], [1], [3, 30], [2], [3]]

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

Explanation:
After inserting keys 1 and 2, key 1 is accessed and becomes most recently used.
Inserting key 3 evicts key 2, so get(2) returns -1.

Example 2:

Input:
capacity = 1
operations = ["put", "get", "put", "get", "get"]
arguments = [[5, 50], [5], [6, 60], [5], [6]]

Output:
[null, 50, null, -1, 60]

Explanation:
With capacity 1, inserting key 6 evicts key 5.

Constraints

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