Low-Latency LRU Cache | Dataford Interview Questions

Capital One transaction services need low-latency access to recently requested transaction results. Implement an LRU cache that supports constant-time lookup, insertion, update, and eviction.

The cache stores integer keys and values. A successful get marks the key as most recently used. A put inserts or updates a key and also marks it as most recently used. When inserting into a full cache, evict the least recently used key.

Formal Specification

Implement process_lru(capacity, operations). capacity is an integer, and operations is a list where each operation is either ['get', key] or ['put', key, value]. Return a list containing the result of every get operation, using -1 when the key is absent.

All cache operations must run in O(1) average time. Do not use a library LRU cache.

Constraints

1 <= capacity <= 10^5
1 <= operations.length <= 2 * 10^5
Keys and values are integers in [-10^9, 10^9]
Every operation is valid and has the required number of fields

Function Signature

def process_lru(capacity, operations):

Your question is Low-Latency 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