LRU Cache
Medium Hash TableLinked ListDesignDoubly-Linked List
Design a fixed-capacity cache that evicts the least-recently-used entry when full. Both
get and put must run in O(1), which forces the combination of a hash map (for direct lookup) with a doubly-linked list (for ordering).Description
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity)— initialize the cache with a positivecapacity.int get(int key)— return the value of thekeyif it exists, otherwise return-1.void put(int key, int value)— update the value of thekeyif present, otherwise add thekey-valuepair. If the number of entries exceedscapacity, evict the least recently used entry first.
Both get and put must run in O(1) average time complexity.
A get or put on an existing key counts as a use — it should be considered the most recently used after the operation.
Examples
Input: LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
Output: [null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation: After
put(3,3) the cache is full and key 2 was the least recently used (key 1 was just accessed by get(1)), so 2 is evicted. The next get(2) returns -1. Then put(4,4) evicts key 1 (now the LRU).Input: LRUCache(1); put(1,1); put(2,2); get(1); get(2)
Output: [null, null, null, -1, 2]
Explanation: With capacity
1, put(2,2) evicts key 1 immediately. Subsequent get(1) returns -1; get(2) returns 2.Input: LRUCache(2); put(2,1); put(2,2); get(2); put(1,1); put(4,1); get(2)
Output: [null, null, null, 2, null, null, -1]
Explanation:
put(2,2) updates key 2's value to 2 and counts as a use. put(4,1) evicts the LRU entry — at that point key 2 had been used most recently (the get(2)), so key 1 is evicted... but key 1 was the most recent put. Walk through: after put(1,1) order is [2,1]; after put(4,1) capacity exceeded, evict 2 (LRU because put(1,1) made 1 MRU). So get(2) returns -1.Constraints
1 ≤ capacity ≤ 30000 ≤ key ≤ 10^40 ≤ value ≤ 10^5- At most
2 × 10^5calls will be made togetandputcombined - Both
getandputmust run inO(1)average time complexity
Hints
Code Editor