LRU Cache for Job Listings | Dataford Interview Questions

Robert Half's job search experience may cache frequently accessed job listings. Implement an LRU cache that stores key-value pairs and evicts the least recently used entry when its capacity is exceeded.

The cache must support get and put operations in O(1) average time. A successful get marks the key as most recently used. Updating an existing key with put also marks it as most recently used. A missing key returns None.

Formal Specification

Implement lru_cache(capacity, operations):

capacity is a positive integer.
operations is a list of operations. Each operation is either ['get', key] or ['put', key, value].
Keys are integers. Values are strings representing cached listing data.
Return a list containing the result of every get operation, in order. put operations produce no result.

Constraints

1 <= capacity <= 10^5
0 <= operations.length <= 2 * 10^5
Each operation is either ['get', key] or ['put', key, value].
Keys are integers and values are non-empty strings.

Function Signature

def lru_cache(capacity, operations):

Your question is LRU Cache for Job Listings. 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