Design an LRU (Least Recently Used) Cache

Your task is to implement a data structure that simulates the behavior of a Least Recently Used (LRU) cache.

Class Definition

• LRUCache(int capacity): Initializes the cache with a positive integer representing its capacity.
• int get(int key): If the key exists, return the associated value; otherwise return -1.
• void put(int key, int value): Inserts or updates the key with the given value. If the cache exceeds its capacity, the least recently used key is removed first.

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

Example Execution

  LRUCache cache = new LRUCache(2);
  cache.put(10, 10); // cache is {10=10}
  cache.put(20, 20); // cache is {10=10, 20=20}
  cache.get(10);     // returns 10
  cache.put(30, 30); // LRU key 20 is removed, cache is {10=10, 30=30}
  cache.get(20);     // returns -1 (not found)
  cache.put(40, 40); // LRU key 10 is removed, cache is {40=40, 30=30}
  cache.get(10);     // returns -1 (not found)
  cache.get(30);     // returns 30
  cache.get(40);     // returns 40
  

Constraints

• 1 ≤ capacity ≤ 2000
• 0 ≤ key ≤ 104
• 0 ≤ value ≤ 105
• The number of calls to get and put will not exceed 105.