LRU Cache

Problem: Implement an LRU Cache Design and implement a Least Recently Used (LRU) cache supporting: get(key): return the value if the key exists; otherwise return -1. put(key, value): update the value if the key exists; otherwise insert the key-value pair. When the cache reaches its capacity, inserting a new key must evict the least recently used key. Requirements Both get and put must run in O(1) (amortized) time. I/O format (for testing here) stdin: Line 1: integer capacity Line 2: integer q, number of operations Next q lines: one operation per line: get key put key value stdout: Print one line per get result. Constraints 1 <= capacity <= 1e5 1 <= q <= 2e5 key, value are 32-bit integers Example Input: 2 8 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 Output: 1 -1 -1 3 Example Input 2 8 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 Output 1 -1 -1 3