Challenge
Simulate a least-recently-used cache and return one value for each get operation. Operations are ["put", key, value], ["get", key], and ["resize", new_capacity]. A successful get and every put make that key most recent. A missing get returns null (None) and changes no recency. Put on an existing key updates its value. When over capacity, evict least-recent keys. Resize can evict several keys and otherwise preserves recency. At capacity zero, nothing is retained.
Input and output contract
0 ≤ initial and resized capacity ≤ 5,000; at most 15,000 operations, including at most 1,500 gets; integer keys and values with absolute value ≤ 1,000,000. All operation shapes are valid. Put and resize emit no result. c is maximum cache capacity; m is operation count.
All tests follow this contract. You do not need to validate malformed input. Return the requested result from lru_cache; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(m) expected total time; O(c) cache space plus returned get results
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Arguments
[2, [['put', 1, 10], ['put', 2, 20], ['get', 1], ['put', 3, 30], ['get', 2], ['resize', 1], ['get', 1], ['get', 3]]]
Expected return
[10, None, None, 30]
Arguments
[0, [['put', 1, 5], ['get', 1], ['resize', 1], ['put', 1, 9], ['get', 1]]]
Expected return
[None, 9]
Arguments
[1, [['put', 1, 4], ['put', 1, 8], ['get', 1]]]
Expected return
[8]
Hint
A dictionary locates entries. A doubly linked list makes removing and moving a known entry constant time; head is least recent.
The worked solution unlocks after completion, or with Premium access.