Designing an LRU Cache | Dataford Interview Questions

Your question is Designing an 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

Elsevier content services may cache recently accessed article or ScienceDirect document metadata to reduce repeated computation. Implement a fixed-capacity least recently used (LRU) cache.

Create a function that processes cache operations and returns the result of every get operation. Both retrieving a key and inserting or updating a key make that key the most recently used. When inserting a new key would exceed capacity, evict the least recently used key.

Formal Specification

Implement lru_cache(capacity, operations):

capacity is a positive integer.
operations is a list of operations. Each operation is either ['put', key, value] or ['get', key].
key and value are integers.
Return a list containing one integer for each get operation, in the same order. Return -1 when a key is absent.

Your implementation must provide average O(1) time for both get and put. Do not use a library LRU cache.

Constraints

1 <= capacity <= 10^4
1 <= len(operations) <= 10^5
Each operation is either ['get', key] or ['put', key, value]
Keys and values are integers in the range [-10^9, 10^9]

Function Signature

def lru_cache(capacity, operations):