Python Caching Function

MediumPython

Problem

Alvarez & Marsal analysis workflows may repeatedly request the same computed result. Implement a fixed-capacity least recently used (LRU) cache that stores integer key-value pairs and evicts the item that has not been accessed for the longest time.

Create a function that processes a sequence of cache operations and returns the results of all get operations. A get for a missing key must return -1. Both a successful get and a put operation make the key the most recently used item. If put updates an existing key, its value changes and its recency is refreshed.

Formal Specification

Implement lru_cache_operations(capacity, operations).

capacity is a positive integer.
operations is a list of commands. Each command is either ['get', key] or ['put', key, value].
key and value are integers.
Return a list containing one integer for every get command, in input order.

Constraints

1 <= capacity <= 10^4
1 <= len(operations) <= 10^5
0 <= key <= 10^9
-10^9 <= value <= 10^9
Every operation is valid and has the required number of fields

Function Signature

def lru_cache_operations(capacity, operations):

Formal Specification

Implement lru_cache_operations(capacity, operations).

capacity is a positive integer.
operations is a list of commands. Each command is either ['get', key] or ['put', key, value].
key and value are integers.
Return a list containing one integer for every get command, in input order.