LFU Cache

Reported in interviews at Bank of America Citadel The Voleon Group

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):
  • capacity is the maximum number of keys the cache can hold.
  • ops is 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 -1 if the key is absent.
  • For a ["put", key, value], insert or update the key, then append None (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