Implement an LRU Cache (HashMap + Doubly Linked List) and Debug an Existing Implementation

Problem: Implement and Debug an LRU Cache Implement a fixed-capacity LRU (Least Recently Used) cache supporting the following operations in amortized O(1) time: get(key): If key exists, return its value and mark the entry as most recently used; otherwise return -1. put(key, value): Insert or update key with value and mark it as most recently used. If the cache exceeds capacity, evict the least recently used entry. Requirements Use a HashMap + doubly linked list (or an equivalent structure) to guarantee O(1) get/put. Maintain recency order correctly: Most recently used node at the head Least recently used node at the tail put on an existing key must: Update the value Move the node to the head When full and inserting a new key: Remove the tail (LRU) node Remove it from the HashMap as well I/O for an executable version of this prompt Given a sequence of operations, print outputs of all get operations. Input (stdin): Line 1: two integers capacity and m (capacity and number of operations) Next m lines: an operation get key put key value Output (stdout): Print one line per get result. Constraints 1 <= capacity <= 1e5 1 <= m <= 2e5 key, value are 32-bit signed 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 Part 1 (Debugging) You are given an existing LRU cache implementation (intended to be HashMap + doubly linked list) that contains one or more bugs. Identify the bug(s), explain the impact, and fix the implementation so it matches the required behavior and complexity. 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