LRU Miss Statistics

Problem

Simulate an LRU cache of the given capacity. operations contains "get" or "put" and keys supplies the key for each. A get of a missing key is a miss, and a put of an absent key is also a miss; an access to a key already in the cache is a hit. Return [total_misses, longest_miss_streak], where capacity 0 makes every access a miss.

Hint

Store a logical timestamp per key; the eviction victim is the key with the smallest timestamp.

Test cases

case 1

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

expected: [4,2]

case 2

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

expected: [5,3]

case 3

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

expected: [4,4]

case 4

in: [1,["put","get","put","get"],[1,1,2,1]]

expected: [3,2]

Starter codePython

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

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