LRU Page Replacement

Problem Statement Design and implement a data structure for a Least Recently Used (LRU) cache. It should support the following operations: 1. get(key) : Retrieve the value of the key if the key exists in the cache, otherwise return 1. 2. put(key, value) : Update the value of the key if it exists. If the key does not exist, insert the key value pair into the cache. If the cache reaches its capacity, it should invalidate and remove the least recently used item before inserting the new item. The functions get and put must each run in O(1) average time complexity. Input Specification The first line contains an integer C, representing the capacity of the cache. The second line contains an integer Q, representing the number of operations to be performed. The next Q lines contain the operations, which can be of two types: GET x: Retrieve the value associated with key x. PUT x y: Insert or update the key x with value y. Output Specification For every GET operation, print the retrieved value on a new line. If the key is not found, print 1. Constraints 1 ≤ C ≤ 1000 1 ≤ Q ≤ 10^5 0 ≤ Key, Value ≤ 10^5 Sample Test Cases Sample Input 1 Sample Output 1 Explanation: Cache capacity is 2. PUT 1 1: Cache is {1=1} PUT 2 2: Cache is {1=1, 2=2} GET 1: Returns 1. Cache is {2=2, 1=1} (1 is now most recently used) PUT 3 3: Capacity full. Evicts LRU (key 2). Cache is {1=1, 3=3} GET 2: Returns 1 (not found) PUT 4 4: Capacity full. Evicts LRU (key 1). Cache is {3=3, 4=4} GET 1: Returns 1 (not found) Sample Input 2 Sample Output 2 Explanation: PUT 1 10: Cache is {1=10} PUT 1 20: Update key 1. Cache is {1=20} GET 1: Returns 20 GET 2: Returns 1 (not found) Difficulty Level Medium