LRU Cache
Updated
Problem statement
Build a least recently used (LRU) cache that holds at most capacity keys, then run the operations in operations in order.
"PUT key value"storesvalueunderkey. If the key is already stored, its value is replaced and nothing is evicted. If the key is new and the cache already holdscapacitykeys, first remove the least recently used key."GET key"returns the stored value, or-1if the key is not in the cache.- A
PUTand aGETthat finds its key both make that key the most recently used. AGETthat misses changes nothing.
Return the results of all GET operations, in order.
Function
runLRU(capacity: int, operations: String[]) → int[]Examples
Example 1
capacity = 3operations = ["PUT 1 100","PUT 2 200","PUT 3 300","GET 1","PUT 4 400","GET 2","GET 3","GET 1","GET 4"]return = [100,-1,300,100,400]Keys 1, 2 and 3 fill the cache. GET 1 returns 100 and makes key 1 the most recent, so the least recently used key is now 2. PUT 4 400 needs room and evicts key 2. The gets then return -1 for key 2, 300 for key 3, 100 for key 1 and 400 for key 4.
Example 2
capacity = 2operations = ["PUT 8 1","PUT 9 2","GET 5","PUT 9 7","PUT 6 3","GET 8","GET 9","GET 6"]return = [-1,-1,7,3]GET 5 misses, returns -1 and changes nothing. PUT 9 7 replaces the value of key 9 and makes it the most recent without evicting anything. When PUT 6 3 needs room, key 8 is the least recently used and is removed. The gets return -1, 7 and 3.
Example 3
capacity = 1operations = ["PUT 0 5","GET 0","PUT 1 6","GET 0","GET 1"]return = [5,-1,6]With capacity 1, the cache holds one key. GET 0 returns 5. Putting key 1 evicts key 0, so the next gets return -1 and 6.
Constraints
1 <= capacity <= 10001 <= operations.length <= 2000- Each operation is
"PUT key value"or"GET key", with single spaces and no leading zeros. 0 <= key <= 10^4and0 <= value <= 10^5- At least one operation is a
GET.
Similar questions at other companies
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- LRU CacheBNSF Railway · PHONE SCREENBNSF Railway interview questions
- Max Frequency TrackerProcol · PHONE SCREEN
- Balanced Session ManagerPalantir · PHONE SCREENPalantir interview questions
- LRU Cache Operation SequenceCARS24 · PHONE SCREEN
- LRU Key-Value Cache OperationsCohesity · PHONE SCREEN
- Least Recently Used CacheMicrosoft · OA · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- LRU CacheApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions
- Least Recently Used CacheByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- LRU CacheServiceNow · PHONE SCREEN