LRU Cache From Scratch

EasyPython

Problem

The AWS Inferentia2 inference path in Annapurna Labs (U.S.) may cache recently used results under a fixed memory budget. Implement an LRU cache from scratch so lookups, insertions, updates, and evictions are efficient.

Define lru_cache(operations, capacity), where operations is a list of commands:

['put', key, value]: insert or update key with value. An updated key becomes most recently used.
['get', key]: return the value for key, or -1 if absent. A successful lookup becomes most recently used.

Return a list containing the result of every get operation, in order. Use a hash map and a doubly linked list. Do not use Python's cache or ordered-map utilities.

Formal Specification

Input: operations, a list of operation lists, and capacity, a positive integer.
Keys and values are integers.
Output: a list of integers produced by get operations.
The least recently used entry must be evicted when an insertion exceeds capacity.

Constraints

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

Function Signature

def lru_cache(operations, capacity):

Define lru_cache(operations, capacity), where operations is a list of commands:

['put', key, value]: insert or update key with value. An updated key becomes most recently used.
['get', key]: return the value for key, or -1 if absent. A successful lookup becomes most recently used.

Return a list containing the result of every get operation, in order. Use a hash map and a doubly linked list. Do not use Python's cache or ordered-map utilities.

Formal Specification

Input: operations, a list of operation lists, and capacity, a positive integer.
Keys and values are integers.
Output: a list of integers produced by get operations.
The least recently used entry must be evicted when an insertion exceeds capacity.