LRU Cache
Medium · Linked List
Design a fixed-capacity cache that maps integer keys to integer values. It supports getting the value for a key and inserting or updating a key-value pair, and both operations should run in constant time. Whenever the cache is asked to get or put a key, that key becomes the most recently used one; when a put would exceed the cache's capacity, the least recently used key must be evicted first.
Examples
Input: capacity=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]
Why: Adding key 3 evicts key 2 (least recently used since key 1 was just accessed); adding key 4 then evicts key 1.Input: capacity=1; put(2,1); get(2); put(3,2); get(2); get(3)
Output: [null,null,1,null,null,-1,2]
Why: With capacity 1, inserting key 3 immediately evicts key 2.Constraints
1 <= capacity <= 3000, 0 <= key <= 10^4, 0 <= value <= 10^5, at most 2*10^5 calls total to get and put
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of LRU Cache. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.