Designing an LRU Cache

MediumPython

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):

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.

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.