Implement an LRU cache

Problem: LRU Cache

Design and implement a data structure that supports an LRU (Least Recently Used) cache with a fixed capacity.

Requirements

Implement a cache with the following operations:

• get(key) -> value
  • If key exists in the cache, return its value and mark the entry as most recently used .
  • If key does not exist, return -1 .
• put(key, value) -> void
  • Insert or update the (key, value) pair.
  • If inserting causes the number of keys to exceed capacity , evict the least recently used entry.
  • Updating an existing key should also mark it as most recently used .

Performance Constraints

• Target time complexity: O(1) average for both get and put .
• Space complexity: O(capacity) .

Example

Assume capacity = 2:

• put(1, 10)
• put(2, 20)
• get(1) -> 10 (now key 1 is most recently used)
• put(3, 30) (evicts key 2 as least recently used)
• get(2) -> -1

Notes

You may choose any programming language, but clearly describe the data structures you use and how you ensure O(1) operations.