Implement LRU Cache with Expiry

PYTHON coding challenge · Difficulty: hard · +200 XP

Class to Implement

------------------

class LRUCacheTTL:

def __init__(self, capacity: int,

ttl: int)

def get(self, key: int) -> int

def put(self, key: int, value: int,

timestamp: int)

Problem

-------

Extend LRU Cache with Time-To-Live (TTL).

Each key expires after ttl seconds from

the time it was inserted/updated.

get(key, timestamp):

• Return -1 if key not found

• Return -1 if key has expired

(current_time - insert_time >= ttl)

• Otherwise return value and mark used

put(key, value, timestamp):

• Insert/update with current timestamp

• Evict LRU non-expired key if full

Example

-------

cache = LRUCacheTTL(capacity=2, ttl=5)

cache.put(1, 100, timestamp=1)

cache.put(2, 200, timestamp=2)

cache.get(1, timestamp=4) → 100

age = 4-1 = 3 < ttl=5 → valid

cache.get(1, timestamp=7) → -1

cache.put(3, 300, timestamp=3)

cache.get(2, timestamp=5) → -1 (evicted)

Timeline view

+-----+-------+-----------+--------+

| key | value | insert_t  | ttl    |

+-----+-------+-----------+--------+

|  1  |  100  |     1     | exp @6 |
|  3  |  300  |     3     | exp @8 |

+-----+-------+-----------+--------+

Constraints

-----------

• 1 <= capacity <= 1,000

• 1 <= ttl <= 10,000

• Timestamps are always non-decreasing