Implement a class LRUCache that simulates a Least Recently Used (LRU) cache with the following operations:
- LRUCache(int max_size): Initializes the cache with a positive integer max_size.
- get(int query_key): Returns the value associated with query_key if it exists in the cache; otherwise, returns -1.
- put(int update_key, int update_value): Inserts or updates the key-value pair (update_key, update_value) in the cache. If the cache exceeds max_size, evicts the least recently used key.
Both get and put must operate in O(1) average time complexity.
Example 1
Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get"] [[3], [5, 10], [6, 20], [5], [7, 30], [6], [8, 40], [7]]
Output: [None, None, None, 10, None, 20, None, 30]
Explanation: Cache starts with max_size 3. After puts: {5=10, 6=20, 7=30}. get(5) returns 10, get(6) returns 20, get(7) returns 30. put(8,40) evicts least recently used (5), so cache is {6=20, 7=30, 8=40}.
Example 2
Input: ["LRUCache", "put", "get", "put", "get", "put", "get"] [[2], [1, 100], [1], [2, 200], [2], [3, 300], [1]]
Output: [None, None, 100, None, 200, None, -1]
Explanation: Cache starts with max_size 2. After puts: {1=100, 2=200}. get(1) returns 100, get(2) returns 200. put(3,300) evicts least recently used (1), so get(1) returns -1.
Constraints
Case 1
Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get"] [[2], [10, 1], [20, 2], [10], [30, 3], [20], [40, 4], [10], [30]]
Expected: [None, None, None, 1, None, -1, None, -1, 3]
Case 2
Input: ["LRUCache", "put", "get", "put", "get", "put", "get", "get"] [[3], [100, 5], [100], [200, 10], [200], [300, 15], [100], [300]]
Expected: [None, None, 5, None, 10, None, 5, 15]