mediumDesign as codingLinked listsHash maps and sets target 25 min
LRU cache
Build a class LRUCache that stores up to capacity key-value pairs and, when it runs out of room, forgets the least recently used key: the key whose last use is furthest in the past. A key is used each time a get finds it or a put stores it.
LRUCache(capacity)makes an empty cache.get(key)returns the value stored forkey, or-1if the key is not in the cache. Agetthat finds the key counts as a use.put(key, value)storesvalueunderkey, replacing the old value if the key is already there. It counts as a use. If the key is new and the cache already holdscapacitykeys, first remove the least recently used key.
Both methods must take O(1) time on average, however many keys the cache holds.
Example 1
Input
LRUCache(2), put(4, 40), put(7, 70), get(4), put(9, 90), get(7), get(9)Outputget(4) returns 40, get(7) returns -1, get(9) returns 90get(4) made key 4 the most recent, so put(9, 90) removed key 7, the least recently used.
Example 2
Input
LRUCache(2), put(1, 10), put(2, 20), put(1, 15), put(3, 30), get(1), get(2)Outputget(1) returns 15, get(2) returns -1Updating key 1 counts as a use, so key 2 is the one removed.
Constraints
1 ≤ capacity ≤ 105
Keys and values are integers, and values are never negative, so -1 always means "missing".
Up to 2 × 105 calls in total.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.