#11MediumDesign· Hash Map with Doubly Linked List

LRU Cache

Implement a fixed-capacity key-value cache that evicts the **least recently used** entry when it runs out of room. Implement the class `LRUCache`: - `LRUCache(capacity)` creates an empty cache that can hold at most `capacity` keys. - `get(key)` returns the value stored for `key`, or `-1` if the key is not present. A successful `get` counts as a use of that key. - `put(key, value)` stores `value` under `key`, replacing any old value; this also counts as a use. If inserting a new key makes the cache exceed `capacity`, first remove the key whose most recent use is the oldest. Both operations must run in `O(1)` average time. **Test format.** `operations[i]` names the call and `arguments[i]` holds its arguments. The first operation is always the constructor. The expected output lists each call's return value, with `null` for the constructor and for `put`.

Input format

operations: array of strings ("LRUCache", "get", "put"), arguments: array of argument arrays

Output format

Array: `null` for the constructor and each `put`, the returned integer for each `get`

Examples

Input: operations = ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"], arguments = [[2], [1, 10], [2, 20], [1], [3, 30], [2], [4, 40], [1], [3], [4]]
Output: [null, null, null, 10, null, -1, null, -1, 30, 40]
After put(3, 30) the cache is full, so key 2 (least recently used) is evicted. After put(4, 40), key 1 is evicted. Keys 3 and 4 remain.
Input: operations = ["LRUCache", "put", "put", "put", "put", "get", "get", "get"], arguments = [[2], [1, 1], [2, 2], [1, 100], [3, 3], [1], [2], [3]]
Output: [null, null, null, null, null, 100, -1, 3]
put(1, 100) updates key 1 and makes it the most recently used, so put(3, 3) evicts key 2 instead.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls are made to get and put.

Study first

  • #design
  • #hash-table
  • #doubly-linked-list
  • #caching