LRU Cache
Problem statement
Design and implement a Least Recently Used (LRU) cache and drive it with a sequence of operations.
Implement the function run_ops(capacity, ops):
capacityis the maximum number of key-value pairs the cache holds.opsis a list of operations, each of the form["get", key]or["put", key, value].
Replay the operations in order against an LRU cache of the given capacity and return a list containing one entry for every "get" operation (in order): the value stored for that key, or -1 if the key is absent. "put" operations produce no output.
The underlying cache supports two operations:
get(key)-- Return the value associated withkeyif it exists, otherwise-1. Accessing a key marks it as most recently used.put(key, value)-- Insert or update the key-value pair. If the cache is already at capacity, evict the least recently used entry before inserting the new one.
Both cache operations must run in $O(1)$ average time, using $O(C)$ space where $C$ is the capacity.
Constraints:
- $1 \leq C \leq 3000$
- $0 \leq \text{key} \leq 10^4$
- $0 \leq \text{value} \leq 10^5$
- At most $2 \times 10^5$ calls to
getandputcombined
Example
run_ops(2, [["put", 1, 1], ["put", 2, 2], ["get", 1], ["put", 3, 3],
["get", 2], ["get", 3], ["put", 4, 4], ["get", 1],
["get", 3], ["get", 4]]) -> [1, -1, 3, -1, 3, 4]
Only the six "get" operations produce output. get(1) returns 1; inserting key 3 evicts key 2 (the LRU), so get(2) returns -1; get(3) returns 3; inserting key 4 evicts key 1, so get(1) returns -1; then get(3) and get(4) return 3 and 4.
Show hint
What does each operation need to find quickly, and can any single standard structure provide all of it?
Relevant roles: ML Engineer, AI Engineer, MLOps Engineer, Forward Deployed Engineer and LLM Engineer.
Related free problems
- LFU CacheHard