LFU Cache
Problem statement
Implement a Least Frequently Used (LFU) cache and replay a sequence of operations against it.
Write a function with the signature:
def run_ops(capacity, ops):
capacityis the maximum number of keys the cache can hold.opsis a list where each element is either["get", key]or["put", key, value].
Apply each op in order and build a result list:
- For a
["get", key], append the stored value for that key, or-1if the key is absent. - For a
["put", key, value], insert or update the key, then appendNone(a put returns nothing).
Return the list of results, in order.
Eviction rule: when a put would exceed capacity, evict the least frequently used key. A key's use count increases by 1 on every get and every put (insert or update) that touches it. Ties are broken by least recently used: among keys sharing the minimum frequency, evict the one accessed longest ago. If capacity is 0, the cache stores nothing and every get returns -1.
Example
run_ops(2, [["put", 1, 1], ["put", 2, 2], ["get", 1], ["put", 3, 3], ["get", 2], ["get", 3]])
-> [None, None, 1, None, -1, 3]
After putting keys 1 and 2 (each freq 1), get(1) returns 1 and raises key 1 to freq 2. Putting key 3 overflows capacity, so the least-frequently-used key (key 2, still at freq 1) is evicted; hence get(2) returns -1 while get(3) returns 3.
Show hint
Can you group keys by how many times they have been used, so the eviction victim is always found without scanning?
Relevant roles: ML Engineer, AI Engineer, MLOps Engineer, Forward Deployed Engineer and LLM Engineer.
Related free problems
- LRU CacheMedium