LFU Cache Operations

Problem

Simulate an LFU (least frequently used) cache with the given capacity.

operations contains "put" (keys[i] and values[i]) or "get" (keys[i]); get returns the stored value or -1. When the cache is full, put evicts the key with the smallest access frequency, breaking ties by least recent use.

Return the list of recorded results (None for put).

Hint

Track frequency and last-use tick for every key; evict the minimum of the pair (frequency, tick).

Test cases

case 1

in: [2,["put","put","get","put","get","get","put","get","get","get"],[1,2,1,3,2,3,4,1,3,4],[1,2,0,3,0,0,4,0,0,0]]

expected: [null,null,1,null,-1,3,null,-1,3,4]

case 2

in: [1,["put","put","get","get"],[1,2,1,2],[10,20,0,0]]

expected: [null,null,-1,20]

case 3

in: [2,["get"],[5],[0]]

expected: [-1]

case 4

in: [2,["put","put","get","put","get","get"],[1,2,1,1,2,1],[5,6,0,7,0,0]]

expected: [null,null,5,null,6,7]

Starter codePython

def lfu_cache(capacity, operations, keys, values):
    # Your code here
    pass

4 test cases · run your code against them in the editor