Implement an LRU cache

Design and implement an in-memory cache that evicts entries using the Least Recently Used (LRU) policy.

The cache should store key–value pairs and support the following operations:

• LRUCache(int capacity) : Initialize the cache with a positive integer capacity representing the maximum number of key–value pairs it can hold.
• int get(int key) :
  • If the key exists in the cache, return its value and mark this key as most recently used .
  • If the key does not exist, return -1 .
• void put(int key, int value) :
  • Insert or update the value of the given key.
  • When inserting a new key causes the number of items to exceed capacity , you must evict exactly one key–value pair: the one that has been least recently used (i.e., the one whose get or put was accessed furthest in the past).
  • Updating an existing key should also mark it as most recently used .

Requirements:

• All get and put operations must run in O(1) average time.
• You may assume:
  • Keys and values are integers.
  • capacity >= 1 .

Describe the data structures you would use and then implement the LRU cache in a language of your choice.