LRU Conflict Resolution

Implement an LRU cache. Please complete the class LRUCache: LRUCache(int capacity) Initialize the LRU cache with a positive integer capacity. int get(int key) Return the value of the key if it exists in the cache, otherwise return -1. void put(int key, int value) Update the value of the key if it exists, otherwise insert the key-value pair. When the cache reaches its capacity, it should invalidate the least recently used item before inserting new data. Average time complexity for both operations should be O(1). Example: Input ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[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 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); lRUCache.put(2, 2); lRUCache.get(1); // Returns 1 lRUCache.put(3, 3); // Invalidates key 2 lRUCache.get(2); // Returns -1 (not found) lRUCache.put(4, 4); // Invalidates key 1 lRUCache.get(1); // Returns -1 (not found) lRUCache.get(3); // Returns 3 lRUCache.get(4); // Returns 4 Example Input {"ops":["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"], "values":[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]}