LFU Eviction Order

Problem

Simulate an LFU cache where each access puts the given key. A hit increases the key's frequency; inserting a new key into a full cache evicts the key with the smallest frequency, breaking ties by least recent use, then inserts the new key. Return the evicted keys in eviction order, and [] when capacity <= 0.

Hint

Ties on frequency are broken by the last-access timestamp; every key has a unique timestamp.

Test cases

case 1

in: [2,[1,2,1,3,2]]

expected: [2,3]

case 2

in: [2,[1,2,3]]

expected: [1]

case 3

in: [1,[1,1,2]]

expected: [1]

case 4

in: [3,[1,2,1,3,1,2]]

expected: []

case 5

in: [0,[1,2]]

expected: []

Starter codePython

def lfu_eviction_order(capacity, accesses):
    # Your code here
    pass

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