LRU Cache
Updated
Problem statement
Design a cache that keeps at most capacity key-value pairs and, when it is full, throws away the least recently used key. Run a list of operations on an empty cache, in order:
"GET key": ifkeyis in the cache, return its value and mark the key as just used. Otherwise return-1."PUT key value": ifkeyis already in the cache, replace its value and mark it as just used. Otherwise, if the cache already holdscapacitykeys, first remove the key that was used longest ago, then add the new key as just used.
Both reading a key with GET and writing it with PUT count as using it. A GET of a missing key changes nothing. Return the results of all GET operations, in order. Each operation should take O(1) average time.
Function
runLRU(capacity: int, operations: String[]) → int[]Examples
Example 1
capacity = 2operations = ["PUT 1 10","PUT 2 20","GET 1","PUT 3 30","GET 2","GET 3","GET 1"]return = [10,-1,30,10]After the two PUTs the cache holds keys 1 and 2. GET 1 returns 10 and makes key 2 the least recently used. So PUT 3 30 removes key 2. Then GET 2 returns -1, GET 3 returns 30, and GET 1 returns 10.
Example 2
capacity = 2operations = ["PUT 5 1","PUT 6 2","PUT 5 7","PUT 8 3","GET 6","GET 5","GET 8"]return = [-1,7,3]PUT 5 7 updates key 5 and marks it as just used, so key 6 becomes the least recently used. PUT 8 3 removes key 6. The GETs return -1 for key 6, 7 for key 5, and 3 for key 8.
Example 3
capacity = 1operations = ["GET 4","PUT 4 0","GET 4","PUT 9 9","GET 4"]return = [-1,0,-1]The first GET 4 misses and returns -1. After PUT 4 0, GET 4 returns 0, which is a real value, not a miss. With capacity 1, PUT 9 9 removes key 4, so the last GET 4 returns -1.
Constraints
1 <= capacity <= 30001 <= operations.length <= 2 * 10^4- Each operation is
"GET key"or"PUT key value", with single spaces. 0 <= key <= 10^40 <= value <= 10^5
More LotusFlare Onsite Interview questions
Similar questions at other companies
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- LRU CacheJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions
- LRU Cache OperationsHevo Data · ONSITE INTERVIEW
- LRU Cache OperationsLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- LRU Cache Operation SequenceGoogle · ONSITE INTERVIEWGoogle interview questions
- Least Recently Used CacheMicrosoft · OA · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- LRU CacheAMD · ONSITE INTERVIEWAMD interview questions
- LRU CacheApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions
- Least Recently Used CacheByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- Least Recently Used CacheGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions