Design and Implement a Scalable LRU Cache

PYTHON coding challenge · Difficulty: hard · +200 XP

Class to Implement

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

class LRUCache:

def __init__(self, capacity: int)

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

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

Problem

-------

Design a Least Recently Used (LRU) cache

with a fixed capacity.

get(key):

• Return value if key exists

• Mark key as recently used

• Return -1 if key not found

put(key, value):

• Insert or update the key-value pair

• Mark key as recently used

• If at capacity, evict the LEAST

recently used key first

Both operations must run in O(1) time.

Example

-------

cache = LRUCache(capacity=3)

cache.put(1, 10) # cache: {1:10}

cache.put(2, 20) # cache: {1,2}

cache.put(3, 30) # cache: {1,2,3} FULL

cache.get(1) → 10 # 1 is now most recent

order: 2→3→1 (LRU first)

cache.put(4, 40)

cache.get(2) → -1 # was evicted

cache.get(3) → 30 # still present

Constraints

-----------

• 1 <= capacity <= 3,000

• 0 <= key, value <= 10,000

• O(1) time for get and put

• Hint: use OrderedDict or doubly linked

list + hash map