Design cache with least-recently-used eviction

You are asked to design an in-memory key–value cache that supports a least-recently-used (LRU) eviction policy.

The cache must support the following operations:

• get(key) -> value :
  • If key exists in the cache, return its associated value and mark this entry as most recently used .
  • If key does not exist, return -1 (or an equivalent sentinel value indicating a miss).
• put(key, value) -> void :
  • Insert or update the value associated with key .
  • If the key already exists, update its value and mark it as most recently used .
  • If inserting the new key would cause the number of items in the cache to exceed a fixed capacity (given when the cache is created), you must evict the least recently used entry first.

Requirements:

• The cache is initialized with an integer capacity > 0 .
• Both get and put operations must run in amortized O(1) time .
• Clearly describe the data structures you will use to achieve O(1) time for both operations.

Example behavior (for illustration only):

Initialize cache with capacity = 2
put(1, 1)          # cache = {1=1}
put(2, 2)          # cache = {1=1, 2=2} (2 is most recently used)
get(1) -> 1        # returns 1, cache order: 2 (LRU), 1 (MRU)
put(3, 3)          # capacity exceeded, evict 2 (LRU), cache = {1=1, 3=3}
get(2) -> -1       # 2 was evicted
put(4, 4)          # capacity exceeded, evict 1 (LRU), cache = {3=3, 4=4}
get(1) -> -1       # 1 was evicted
get(3) -> 3        # returns 3
get(4) -> 4        # returns 4