Your question is Low-Latency 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.
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.
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.
def process_lru(capacity, operations):