LRU Cache (Design, Modified)

Problem: Design a data structure for a Least Recently Used (LRU) cache that supports get(key) and put(key, value) in O(1) average time, evicting the least recently used item when capacity is exceeded. (In this interview, the interviewer asked for a modified/extended variant beyond the basic LeetCode version.)

Constraints: Capacity is fixed and positive; keys/values are generic.

Example: capacity=2; put(1,1); put(2,2); get(1)->1; put(3,3) evicts key 2; get(2)->-1.

Approach: A brute-force approach with 3-4 hashmaps runs in linear time per operation. This can be optimized to O(log n) with an ordered structure, and finally to true O(1) using a combination of a HashMap (key -> node) and a doubly linked list that tracks recency order, moving the accessed node to the front on every get/put and evicting from the tail on overflow.