LRU Cache (Design with Doubly Linked List + Hash Map)

Problem: Implement an LRU Cache Design and implement an LRU (Least Recently Used) cache that supports the following operations with average time complexity O(1). Implement class LRUCache: LRUCache(int capacity): Initialize the cache with a positive integer capacity. int get(int key): If key exists in the cache, return its value and mark it as most recently used; otherwise return -1. void put(int key, int value): If key already exists, update its value and mark it as most recently used; otherwise insert the key-value pair. If the cache size exceeds capacity, evict the least recently used entry. Constraints 1 <= capacity <= 10^5 0 <= key, value <= 10^5 Total number of get and put operations <= 2 * 10^5 Use a hash map + doubly linked list to achieve O(1) operations. Example Input: capacity = 2 put(1, 1) put(2, 2) get(1) put(3, 3) get(2) put(4, 4) get(1) get(3) get(4) Output: 1 -1 -1 3 4 Example Input 2 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4 Output 1 -1 -1 3 4