Implement LRU Cache with get and put Operations

apple Implement a LRU (Least Recently Used) cache. This cache needs to support get and put operations and should automatically remove items based on the least recently used policy when the cache reaches its maximum capacity. Please implement the class LRUCache: LRUCache(int capacity) Initializes the LRU cache with a positive integer capacity. int get(int key) Returns the value of the key if the key exists in the cache, otherwise returns -1. void put(int key, int value) If the key already exists, change its data value; if not, insert the key-value pair into the cache. If the insertion operation causes the cache capacity to exceed capacity, it should remove the least recently used item before inserting the new item. Test cases: cache = LRUCache(2) cache.put(1, 1) cache.put(2, 2) print(cache.get(1)) # returns 1 cache.put(3, 3) # evicts key 2 print(cache.get(2)) # returns -1 (not found) cache.put(4, 4) # evicts key 1 print(cache.get(1)) # returns -1 (not found) print(cache.get(3)) # returns 3 print(cache.get(4)) # returns 4 Constraints: 1 <= capacity <= 3000 0 <= key <= 10000 0 <= value <= 100000 The number of calls to get and put is at most 3 * 10^4. Example Input LRUCache(2) put(1, 1) put(2, 2) get(1) put(3, 3) get(2) put(4, 4) get(1) get(3) get(4)