LRU Cache

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

Implement a function that processes an array of operations and an array of arguments:

• "LRUCache" — Initialize the LRU cache with positive size capacity.
• "put" — Update the value of the key if it exists. Otherwise, add the key-value pair. If the number of keys exceeds the capacity, evict the least recently used key.
• "get" — Return the value of the key if it exists, otherwise return -1.

Both get and put must run in O(1) average time complexity.

Examples

Example 1:

Input: operations = ["LRUCache","put","put","get","put","get","put","get","get","get"], args = [[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: The cache capacity is 2. After putting keys 1 and 2, getting key 1 returns 1. Putting key 3 evicts key 2 (least recently used). Getting key 2 returns -1 (not found). Putting key 4 evicts key 1. Getting keys 1, 3, and 4 returns -1, 3, and 4 respectively.

Example 2:

Input: operations = ["LRUCache","put","get","put","get","get"], args = [[1],[1,10],[1],[2,20],[1],[2]]

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

Explanation: Cache capacity is 1. After putting key 1 and getting it (returns 10), putting key 2 evicts key 1. Getting key 1 returns -1, getting key 2 returns 20.

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5
• At most 2 * 10^5 calls will be made to get and put