Thread-Safe LRU Cache for Serving | Dataford Interview Questions

Your question is Thread-Safe LRU Cache for Serving. 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.

Goldman Sachs Marquee model-serving workers need a bounded cache for recently used model results. Implement a thread-safe least recently used (LRU) cache that supports constant-time get and put operations.

Your function receives a positive capacity and a sequence of operations. Each operation is either ["get", key] or ["put", key, value]. Return the results of all get operations in order. A missing key returns -1; put operations produce no output.

The cache must satisfy these rules:

A successful get marks the key as most recently used.
Inserting an existing key replaces its value and marks it as most recently used.
If insertion exceeds capacity, evict the least recently used key.
Protect every cache operation with synchronization so a get cannot observe a partially completed update or eviction. It is acceptable to process the supplied operations sequentially while using a lock internally.

Formal Specification

Input: integer capacity and a list of operation lists containing integer keys and values. Output: a list of values from get operations, in order.

Constraints

1 <= capacity <= 10^5
1 <= operations.length <= 10^5
Each operation is either ["get", key] or ["put", key, value]
Keys and values are integers

Function Signature

def lru_cache(capacity, operations):