Advanced
Build an LRU cache
Write a class LRUCache(capacity) (least recently used). get(key) returns the value, or -1 if the key is missing, and marks the key as recently used. put(key, value) stores a value and marks it recently used; if the cache is over capacity afterwards, it removes the least recently used key.
Both operations should take constant time, which means the work does not grow as the cache gets bigger. Hint: collections.OrderedDict is a dictionary that remembers the order of its keys, and it has move_to_end and popitem(last=False).
What Check tests
- get returns stored values and -1 for missing keys
- The least recently used key is evicted
- get counts as a use
- Updating a key keeps size and refreshes it
- Falsy values are real values
- Capacity 1
Stuck? One hint at a time
The solution unlocks after your first Check. Try first: that is where the learning happens.
main.py
Sign in to run your code.
Output
Press Run to see what your program prints.