LRU Key-Value Cache Operations
Updated
Problem statement
Implement a key-value cache with a fixed positive capacity, then process the rows in operations in order.
"PUT key value"inserts or updates an integer key. Updating a key replaces its value without increasing the number of stored keys."GET key"returns the stored integer value, or-1when the key is absent.
Every PUT and every successful GET makes that key the most recently used. A missing GET does not change recency. When inserting a new key would exceed capacity, evict the least recently used key first.
Return the result of every GET operation in encounter order. Build the eviction behavior directly rather than using a library-provided LRU cache.
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"]return = [10,-1,30]GET 1 makes key 1 most recent, so inserting key 3 evicts key 2.
Example 2
capacity = 1operations = ["PUT 4 7","PUT 4 9","GET 4","PUT 5 5","GET 4"]return = [9,-1]Updating key 4 replaces its value and refreshes its recency. Inserting key 5 later evicts it because the capacity is one.
Example 3
capacity = 2operations = ["GET 7","PUT 0 0","GET 0"]return = [-1,0]The first lookup misses without changing the cache. Key and value zero are both valid.
Constraints
1 <= capacity <= 100000.1 <= operations.length <= 200000.- Every row is exactly
"GET key"or"PUT key value", with single spaces between tokens. -1000000000 <= key <= 1000000000.0 <= value <= 1000000000, so-1is reserved for a missing key.
More Cohesity interview questions
Similar questions at other companies
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- 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
- LRU CacheCoupang · PHONE SCREEN
- LRU CacheBlinkit · PHONE SCREENBlinkit interview questions
- LRU Cache with Thread-Safety Follow-UpSnap Inc. · PHONE SCREENSnap Inc. interview questions
- Least Recently Used CacheIllumio · PHONE SCREENIllumio interview questions
- LRU Key-Value Cache OperationsNVIDIA · PHONE SCREENNVIDIA interview questions