Basic LRU behavior
Input
run_sequence(2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2)])
Output
[1, -1]
After accessing key 1, key 2 becomes LRU and is evicted when key 3 is added.
Full lesson preview
Implement a simple LRU cache
Build a small LRUCache class with get and put using an order-maintaining structure.
Python practice25 minModules & Standard LibraryAdvancedLast updated March 23, 2026
Problem statement
Create an LRU cache with a fixed positive capacity. The cache should support:
- get(key): return the value if present and mark the key as recently used; otherwise return -1.
- put(key, value): insert or update the key with value and mark it as recently used. If insertion causes the number of keys to exceed capacity, remove the least recently used key.
You may assume keys are hashable. Implement LRUCache using an order-preserving mapping (e.g., collections.OrderedDict or dict with move-to-end semantics).
A helper function run_sequence(capacity, ops) is provided to run a sequence of operations and return a list of results for every 'get' operation. Use it in tests.
Task
Implement LRUCache(capacity) with methods get(key) -> value or -1 and put(key, value). When capacity is exceeded evict the least-recently-used key.
Examples
Input format
Use run_sequence(capacity, ops) where ops is a list of tuples: ('put', key, value) or ('get', key).
Output format
A list of results corresponding to each 'get' call, in order.
Constraints
capacity is a positive integer (>=1). Keys are hashable. get returns -1 for missing keys.
Samples
Sample 1
Input
run_sequence(1, [('put',1,1), ('put',2,2), ('get',1), ('get',2)])
Output
[-1, 2]
Capacity 1 - inserting key 2 evicts key 1.