Implement an LRU Cache

Problem: LRU Cache (LeetCode 146)

Design and implement a Least Recently Used (LRU) Cache that supports the following operations in average O(1) time.

Requirements

Implement a class LRUCache with:

• LRUCache(int capacity) : Initialize the cache with a positive capacity.
• int get(int key) : Return the value of the key if it exists; otherwise return -1 .
  • Accessing a key counts as using it, so it becomes most recently used .
• void put(int key, int value) : Insert or update the value of the key.
  • If the key exists, update its value and mark it as most recently used .
  • If inserting causes the cache to exceed capacity, evict the least recently used key.

Notes / Constraints

• Keys and values are integers.
• Aim for O(1) average time per get and put .
• You may use any language, standard library containers, and write unit tests.

Example

If capacity = 2:

1. put(1, 1) -> cache = {1=1}
2. put(2, 2) -> cache = {1=1, 2=2}
3. get(1) -> returns 1 , cache order becomes [2 (LRU), 1 (MRU)]
4. put(3, 3) -> evicts key 2 , cache = {1=1, 3=3}
5. get(2) -> returns -1