Implement an LRU Cache

Design and implement a Least Recently Used (LRU) cache. An LRU cache is a fixed-size cache that evicts the least recently used items first when it reaches its capacity and a new item needs to be inserted. This is a common data structure pattern used in many applications to optimize performance by keeping frequently accessed data readily available.

Problem Description

You need to implement a LRUCache class with the following operations:

1. initialize(capacity): Initializes the cache with a given capacity. This is the maximum number of key-value pairs the cache can hold.
2. get(key): Returns the value associated with the given key. If the key is not found in the cache, return -1. If the key is found, it should be marked as the most recently used.
3. put(key, value): Inserts or updates the value for the given key.
   • If the key already exists, update its value and mark it as the most recently used.
   • If the key does not exist, insert the new key-value pair.
   • If the cache is at its capacity and a new key-value pair needs to be inserted, evict the least recently used item before inserting the new one.

The operations get and put must have an average time complexity of O(1).

Examples

Example 1:

Input:
capacity = 2
operations = [
  ("put", 1, 1),
  ("put", 2, 2),
  ("get", 1),
  ("put", 3, 3),  // evicts key 2
  ("get", 2),
  ("put", 4, 4),  // evicts key 1
  ("get", 1),
  ("get", 3),
  ("get", 4)
]

Output:
[1, -1, -1, 3, 4]

Explanation:
- put(1, 1): Cache is {1: 1}
- put(2, 2): Cache is {1: 1, 2: 2}
- get(1): Returns 1. Cache is now {2: 2, 1: 1} (1 is most recently used)
- put(3, 3): Cache is at capacity. Evict the least recently used (2). Cache is now {1: 1, 3: 3}
- get(2): Returns -1 (key 2 was evicted)
- put(4, 4): Cache is at capacity. Evict the least recently used (1). Cache is now {3: 3, 4: 4}
- get(1): Returns -1 (key 1 was evicted)
- get(3): Returns 3. Cache is now {4: 4, 3: 3} (3 is most recently used)
- get(4): Returns 4. Cache is now {3: 3, 4: 4} (4 is most recently used)

Example 2:

Input:
capacity = 1
operations = [
  ("put", 2, 1),
  ("get", 2),
  ("put", 3, 2),
  ("get", 2),
  ("get", 3)
]

Output:
[1, -1, 2]

Explanation:
- put(2, 1): Cache is {2: 1}
- get(2): Returns 1. Cache is {2: 1}
- put(3, 2): Cache is at capacity. Evict key 2. Cache is {3: 2}
- get(2): Returns -1 (key 2 was evicted)
- get(3): Returns 2. Cache is {3: 2}

Constraints

• 1 <= capacity <= 10^4
• 0 <= key <= 10^4
• 0 <= value <= 10^4
• The number of operations will not exceed 10^5.
• The key and value will always be non-negative integers.
• get and put operations must have an average time complexity of O(1).

Notes

• Consider how to efficiently track the order of usage for elements.
• A combination of a hash map (for O(1) key lookup) and a doubly linked list (for O(1) insertion/deletion and maintaining order) is a common and effective approach.
• Ensure that when an element is accessed (get) or updated (put), it becomes the most recently used.
• When the cache is full and a new element is added, the least recently used element must be removed.