O(1) Cache Design | Dataford Interview Questions

Design a cache with O(1) get and put operations.

Implement an LRU cache with a fixed positive capacity. get(key) returns the value or -1 when absent. put(key, value) inserts or updates an entry, evicting the least recently used entry when full. Both operations must run in O(1) average time.

Use lru_cache(capacity, operations), where each operation is ['get', key] or ['put', key, value]. Return the values produced by get operations in order.

Constraints

1 <= capacity <= 10^5
1 <= operations.length <= 10^5
Keys and values are integers
Each operation is either ['get', key] or ['put', key, value]
The cache must use O(1) average time for get and put

Function Signature

def lru_cache(capacity, operations):

Your question is O(1) Cache Design. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Design a cache with O(1) get and put operations.

Use lru_cache(capacity, operations), where each operation is ['get', key] or ['put', key, value]. Return the values produced by get operations in order.

Constraints

1 <= capacity <= 10^5
1 <= operations.length <= 10^5
Keys and values are integers
Each operation is either ['get', key] or ['put', key, value]
The cache must use O(1) average time for get and put

Function Signature

def lru_cache(capacity, operations):

Your question is O(1) Cache Design. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.