LRU Map
Design a data structure that supports storing key-value pairs and evicting the least recently used entry when capacity is exceeded.
Implement the basic operations for an LRU map so that lookups and updates can be performed efficiently.
This problem is a classic LRU cache design question. The standard solution combines a hash map for O(1) access with a doubly linked list to maintain usage order. On every get or put, the accessed item is moved to the front, and when the capacity is exceeded, the least recently used item at the tail is evicted. The key challenge is keeping all operations efficient while correctly tracking recency.
END
