LRU with TTL Expiry

Problem

Simulate an LRU cache whose entries expire after a time-to-live.

capacity is the maximum number of entries and ttl is the maximum idle time: an entry expires when times[i] - last_access >= ttl. operations contains "put" (keys[i], values[i]) or "get" (keys[i]). Expired entries are purged on every operation, and eviction removes the least recently used entry.

Return the list of recorded results (None for put, the value or -1 for get).

Hint

A successful get refreshes both the expiry timestamp and the LRU position.

Test cases

case 1

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

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

case 2

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

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

case 3

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

expected: [null,10,null,10,30]

case 4

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

expected: [null,1,1]

Starter codePython

def lru_ttl(capacity, ttl, operations, keys, values, times):
    # Your code here
    pass

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