BeginnerCoder
DonateLesson 24 — LRU cache
LRU cache: forget the least recently used
A cache keeps recent results so you do not recompute or re-download them. It has limited room, so when full it must evict something. LRU (least recently used) evicts the item nobody has touched for the longest. An OrderedDict remembers order: move_to_end(k) marks k as just used, and popitem(last=False) removes the oldest.
from collections import OrderedDict
d = OrderedDict(a=1, b=2)
d.move_to_end("a") # order: b, a
d.popitem(last=False) # removes b
Why it matters: browsers, CPUs and databases all use LRU caches.
In get(), mark k as recently used. In put(), evict the oldest item when there are more than cap. Expected: -1 3 1.
Run your code — when the output matches the task, you will see a green check. Then mark the lesson complete.
Test your knowledgeA quick 3-question quiz on this lesson — instant feedback.
Ready for more? Optional paid resources that pick up where this lesson leaves off.
Some links on this page are affiliate links: we may earn a commission at no extra cost to you. As an Amazon Associate I earn from qualifying purchases.
Project-based Data Structures courses if you want a structured paid path after the free lessons. Wait for a sale — prices drop often.
Browse on Udemy →Search Amazon for Data Structures books — check the publication year so the examples match current versions.
Search Amazon →