Implement LFU Cache | Dataford Interview Questions

Implement an LFU (least frequently used) cache.

Asked in the Coding stage. Senior research engineer loop; the candidate implemented set assuming doubly-linked-list APIs.

Interface

Implement lfu_cache(capacity, operations). Each operation is ['put', key, value] or ['get', key]. Return a list containing the result of every get, using -1 for a missing key. A put on an existing key updates its value and increases its frequency. When full, evict the least frequently used key; break ties by evicting the least recently used key.

Constraints

0 <= capacity <= 10^5
Keys and values are integers
There are at most 2 * 10^5 operations
Each operation is either ['put', key, value] or ['get', key]

Function Signature

def lfu_cache(capacity, operations):

Your question is Implement LFU Cache. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem