Implement an LRU Cache

Problem

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

• get(key) :
  • Return the value associated with key if it exists in the cache.
  • Otherwise return -1 .
  • This operation marks key as most recently used .
• put(key, value) :
  • Insert or update the (key, value) pair.
  • This operation marks key as most recently used .
  • If inserting causes the number of keys to exceed the cache capacity , evict the least recently used key.

Requirements

• Implement a class (or module) that is initialized with an integer capacity .
• Both operations should run in O(1) average time.

Notes / Edge Cases

• Updating an existing key should overwrite its value and update its recency.
• capacity is a positive integer.

Example

Given capacity = 2:

1. put(1, 1)
2. put(2, 2)
3. get(1) → returns 1 (key 1 becomes most recently used)
4. put(3, 3) → evicts key 2
5. get(2) → returns -1
6. put(4, 4) → evicts key 1
7. get(1) → returns -1
8. get(3) → returns 3
9. get(4) → returns 4