Custom LRU Cache Implementation

Airtel Payments Bank services need fast eviction of inactive session data. Implement a fixed-capacity Least Recently Used cache that supports get and put operations in O(1) average time.

Use a hash map for direct key lookup and a custom doubly linked list to maintain usage order. The most recently used item must be at the front, and the least recently used item must be at the back.

Formal Specification

Implement lru_cache_operations(capacity, operations).

• capacity is a positive integer.
• operations is a list of operation arrays. Each operation is either ['get', key] or ['put', key, value].
• Keys and values are integers.
• Return a list containing the result of every get operation, in order.
• Return -1 for a cache miss.
• A successful get marks the key as most recently used.
• Updating an existing key with put also marks it as most recently used.
• When inserting into a full cache, evict the least recently used key.