Implement an LRU (Least Recently Used) cache with two operations: get(key) and put(key, value). get should return the value for key if it exists, otherwise -1. put should insert or update the key-value pair; if the cache exceeds its capacity, evict the least recently used entry. Both operations must run in O(1) average time.
Example 1:
Input: capacity = 2, operations = [put(1, 1), put(2, 2), get(1), put(3, 3), get(2), get(3)]
Output: [1, -1, 3]
Explanation: key 2 is evicted after inserting key 3.
Example 2:
Input: capacity = 1, operations = [put(1, 10), get(1), put(2, 20), get(1), get(2)]
Output: [10, -1, 20]
Explanation: inserting key 2 evicts key 1.
1 <= capacity <= 10^40 <= key, value <= 10^910^5 total get and put operationsget and put must run in O(1) average time
