Memory-Layered LRU Cache | Dataford Interview Questions

Your question is Memory-Layered LRU Cache. Start with the requirements on the right.

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

Problem

Cloudflare Workers can use an in-memory cache layer to avoid repeatedly computing or fetching recently used values. Implement a fixed-capacity LRU cache where the least recently used entry is evicted when the cache is full.

Use a hash map for direct key lookup and a doubly linked list to maintain recency. The most recently used entry must be at the front of the list, and the least recently used entry must be at the back.

Formal Specification

Implement lru_cache_operations(capacity, operations):

capacity is a positive integer.
operations is a list of operations. ['get', key] reads a value, and ['put', key, value] inserts or updates a value.
Return a list containing the result of every get operation, in order.
A missing key returns -1.
A successful get and every put mark the key as most recently used.
Updating an existing key changes its value but does not increase the cache size.

Constraints

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

Function Signature

def lru_cache_operations(capacity, operations):