Least Recently Used Data Structure

EasyPython

Problem

Tencent services such as WeChat and Tencent Cloud may cache frequently accessed data. Implement an LRU cache that removes the least recently used entry when its capacity is exceeded.

Given a positive capacity and a sequence of operations, process each operation in order. A get operation returns the value for a key, or -1 if the key is absent. A put operation inserts or updates a key and returns no output. Both successful get operations and put operations mark the key as most recently used. Return the results of all get operations in order.

Formal Specification

Implement lru_cache(capacity, operations):

capacity is an integer.
operations is a list of operation lists. Each operation is either ['get', key] or ['put', key, value].
key and value are integers.
Return a list of integers containing one result for each get operation.

The cache must support lookup, insertion, update, and eviction in average O(1) time. Do not use Python's built-in ordered cache structures.

Constraints

1 <= capacity <= 10^5
1 <= len(operations) <= 2 * 10^5
0 <= key, value <= 10^9
Each operation is either ['get', key] or ['put', key, value]

Function Signature

def lru_cache(capacity, operations):

Tencent services such as WeChat and Tencent Cloud may cache frequently accessed data. Implement an LRU cache that removes the least recently used entry when its capacity is exceeded.

Formal Specification

Implement lru_cache(capacity, operations):

capacity is an integer.
operations is a list of operation lists. Each operation is either ['get', key] or ['put', key, value].
key and value are integers.
Return a list of integers containing one result for each get operation.

The cache must support lookup, insertion, update, and eviction in average O(1) time. Do not use Python's built-in ordered cache structures.