Implementing an LRU Cache | Dataford Interview Questions

Code out an LRU cache.

Implement lru_cache(operations, capacity), where each operation is a list of strings and integers. A put operation has the form ["put", key, value]; a get operation has the form ["get", key]. Return the values produced by get operations in order, using -1 for missing keys. Both get and put must run in O(1) average time. Accessing or updating a key makes it the most recently used item. When the cache exceeds capacity, evict the least recently used item.

Constraints

1 <= capacity <= 500
1 <= operations.length <= 500
Each operation is either ["get", key] or ["put", key, value]
0 <= key <= 10^9
0 <= value <= 10^9
A get operation returns -1 when its key is absent

Function Signature

def lru_cache(operations, capacity):

Your question is Implementing an LRU Cache. 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

Code out an LRU cache.

Constraints

1 <= capacity <= 500
1 <= operations.length <= 500
Each operation is either ["get", key] or ["put", key, value]
0 <= key <= 10^9
0 <= value <= 10^9
A get operation returns -1 when its key is absent

Function Signature

def lru_cache(operations, capacity):

Your question is Implementing an LRU Cache. 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.