LRU Cache (Least Recently Used)

Design a data structure that follows the constraints of a **Least Recently Used (LRU) cache**. Implement the `LRUCache` class with `get(key)` and `put(key, value)` methods in $O(1)$ average time complexity.

Examples:

Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Constraints:

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

#Hash Table#Linked List#Doubly-Linked List#Design

UTF-8 • 4 Spaces • TypeSafe

Click “Run Code” or “Submit” to execute the test suite against edge cases.