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):