Implement an LRU Cache

To implement an LRU Cache with O(1) get and put operations, I will combine a Hash Map with a Doubly Linked List. The Hash Map will store keys mapping directly to the corresponding nodes in the linked list, allowing instant access. The Doubly Linked List will maintain the usage order, where the most recently used item sits at the head and the least recently used item sits at the tail. For the 'get' operation, if the key exists in the map, I retrieve the node, move it to the front of the list to mark it as recently used, and return its value. If the key is missing, I return -1. For 'put', if the key already exists, I update the value and move the node to the front. If the key is new, I create a new node and insert it at the head. If the cache exceeds its capacity after insertion, I remove the node at the tail, which represents the least recently used item, and delete its entry from the map. This approach ensures that every operation involves only constant-time pointer updates and hash lookups. This specific pattern is often seen in Google's infrastructure where low-latency access to frequently used data is critical, demonstrating my ability to balance memory efficiency with performance constraints effectively.