How do you implement an LRU cache in Python?

Combine a dict with a structure that keeps keys in recency order. The quickest version uses collections.OrderedDict: call move_to_end on every read or write, and popitem(last=False) to drop the oldest key when the size passes capacity. Without OrderedDict, let the dict point at nodes of a two-way linked list framed by sentinel head and tail nodes, and move or unlink nodes by hand. Both give O(1) get and put.

How do you add TTL expiry to an LRU cache?

Save an absolute expiry time, now plus ttl, with each item. On get, treat an item whose expiry is at or before now as a miss and delete it. To clear stale items before evicting live ones without scanning the whole cache, keep a min-heap of expiry times with a version number per entry, and ignore any popped entry whose version differs from the item now cached.

Why are get and put O(1) in an LRU cache?

The dict finds a key's entry in constant time, and the doubly linked list lets you unlink that entry and attach it at the newest end by changing a few pointers, with no shifting of other items. Eviction removes the node at the oldest end, also a fixed number of pointer changes. No step depends on how many items are cached, so both operations are O(1) on average.

AceOffer·

MediumAbout 35 minFree

Helpful?Is this question helpful?

Back

Part 1 · LRU cache

Design a cache that holds at most capacity items and, when it is full, throws out the item that was used least recently.

Implement LRUCache(capacity) (capacity >= 1) with:

get(key) returns the value stored for key, or -1 if it is not in the cache. A successful get makes key the most recently used item.
put(key, value) saves value for key; afterwards key counts as the newest item. An existing key just gets the new value. When the item count goes above capacity, drop the item that has gone unused the longest.

Both operations should run in O(1) time. The textbook design pairs a dict with a two-way linked list. collections.OrderedDict is allowed here, but be ready to explain what it does for you.

Clarify before coding5 questions ▸

Does updating an existing key count as using it?
What should get return for a missing key: -1, None, or an exception?
Is an item still readable at exactly now + ttl?
With weights, do we evict until the total fits, or evict one item and stop?
Can updating an item's weight cause other items to be evicted, and what if one item is heavier than the whole cache?

Covers the whole problem: what candidates report interviewers adding on questions with this pattern, the mistakes to avoid, and where to go next.

What candidates report interviewers add

Make the cache usable from many threads concurrently, and discuss how coarse or fine the locks should be.6 reports · Amazon, Microsoft, Anthropic, Databricks

Keep the cache's contents across a crash or restart by writing them to disk and loading them back.6 reports · Anthropic, Databricks

Give entries an expiry time, check it lazily on reads, and avoid scanning the whole cache to find expired keys.2 reports · Amazon, Microsoft · Part 2

Give each entry a size and measure capacity as the total size instead of the number of entries.1 report · xAI · Part 3

Swap the eviction rule: least frequently used, or a custom eviction function.1 report · Citadel

Why practise this

LRU and LFU caches shows up in 1.7% of the 1,447 coding interview reports we studied, at 6 companies. Build a cache with a size limit and an eviction rule, then change the rule.

Reported at: Anthropic, Amazon, xAI, Citadel, Snowflake, OpenAI.

This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.

Common mistakes5 ▸

Not moving a key to the newest position when it is read or updated.
Forgetting to update the tail (or head) pointer when the removed node is at the end of the list.
Evicting before checking whether the put is just an update, so an item is thrown out for nothing.
Evicting a live item while an expired one is still taking up space.
With weights, evicting only one item per put, or leaving the total wrong after an update changes an item's weight.

Where an interviewer could take it next3 ▸

Keep hit, miss and eviction counters and report a hit rate.
Remove expired items in the background instead of only when the cache is full.
Rewrite it without OrderedDict, with your own node class, and compare memory per entry.

Frequently asked3 ▸

How do you implement an LRU cache in Python?: Combine a dict with a structure that keeps keys in recency order. The quickest version uses collections.OrderedDict: call move_to_end on every read or write, and popitem(last=False) to drop the oldest key when the size passes capacity. Without OrderedDict, let the dict point at nodes of a two-way linked list framed by sentinel head and tail nodes, and move or unlink nodes by hand. Both give O(1) get and put.
How do you add TTL expiry to an LRU cache?: Save an absolute expiry time, now plus ttl, with each item. On get, treat an item whose expiry is at or before now as a miss and delete it. To clear stale items before evicting live ones without scanning the whole cache, keep a min-heap of expiry times with a version number per entry, and ignore any popped entry whose version differs from the item now cached.
Why are get and put O(1) in an LRU cache?: The dict finds a key's entry in constant time, and the doubly linked list lets you unlink that entry and attach it at the newest end by changing a few pointers, with no shifting of other items. Eviction removes the node at the oldest end, also a fixed number of pointer changes. No step depends on how many items are cached, so both operations are O(1) on average.

Practise next

Parking Lot Design · Stateful class design In-Memory Key-Value Store with Transactions · In-memory database or key-value store Time-Based Key-Value Store with TTL · Time-based state (expiry, TTL, snapshots)

Preparing for a specific company? The company guides collect the questions candidates report, with every part and follow-up.

Python 3

Tests4 tests · not run yet

Run the part to execute this test.

Expected

1
-1
-1 3 4

Test code

c = LRUCache(2)
c.put(1, 1)
c.put(2, 2)
print(c.get(1))
c.put(3, 3)
print(c.get(2))
c.put(4, 4)
print(c.get(1), c.get(3), c.get(4))

LRU Cache

Medium3 partsabout 35 minLRU and LFU caches Stateful class design Time-based state (expiry, TTL, snapshots)

Build the classic O(1) least recently used cache, then add per-item expiry with time passed in and a capacity measured in total weight.

Also known as: Design LRU cache, LRU cache with TTL, Time-based LRU cache

Why practise this

LRU and LFU caches shows up in 1.7% of the 1,447 coding interview reports we studied, at 6 companies. Build a cache with a size limit and an eviction rule, then change the rule.

Reported at: Anthropic, Amazon, xAI, Citadel, Snowflake, OpenAI.

This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.

What candidates report interviewers add

Follow-ups candidates reported on questions with this pattern, in our words. Parts marked “from reports” below are built on them.

Make the cache usable from many threads concurrently, and discuss how coarse or fine the locks should be.6 reports · Amazon, Microsoft, Anthropic, Databricks
Keep the cache's contents across a crash or restart by writing them to disk and loading them back.6 reports · Anthropic, Databricks
Give entries an expiry time, check it lazily on reads, and avoid scanning the whole cache to find expired keys.2 reports · Amazon, Microsoft · Part 2
Give each entry a size and measure capacity as the total size instead of the number of entries.1 report · xAI · Part 3
Swap the eviction rule: least frequently used, or a custom eviction function.1 report · Citadel

Design a cache that holds at most capacity items and, when it is full, throws out the item that was used least recently.

Questions to ask before you code

Does updating an existing key count as using it?
What should get return for a missing key: -1, None, or an exception?
Is an item still readable at exactly now + ttl?
With weights, do we evict until the total fits, or evict one item and stop?
Can updating an item's weight cause other items to be evicted, and what if one item is heavier than the whole cache?

Part 1: LRU cache

Implement LRUCache(capacity) (capacity >= 1) with:

get(key) returns the value stored for key, or -1 if it is not in the cache. A successful get makes key the most recently used item.
put(key, value) saves value for key; afterwards key counts as the newest item. An existing key just gets the new value. When the item count goes above capacity, drop the item that has gone unused the longest.

Both operations should run in O(1) time. The textbook design pairs a dict with a two-way linked list. collections.OrderedDict is allowed here, but be ready to explain what it does for you.

Part 2: Per-item expiryfrom reports

Items can now expire. Time is an integer passed in, and calls arrive with now never decreasing. Earlier calls without now still work, because it defaults to 0.

put(key, value, now, ttl=None): with ttl=None the item never expires. Otherwise ttl is a positive integer and the item can be read while t < now + ttl; at now + ttl and later it has expired.
get(key, now): an expired item is a miss. Return -1 and remove it.

When a put pushes the cache over capacity, first remove every item that has expired at that now. Only if it is still over capacity, remove the least recently used item. So an expired item always goes before a live one, even a live one that is older.

Part 3: Weighted capacityfrom reports

Items now have different sizes. put(key, value, now, ttl, weight=1) takes a positive integer weight, and capacity becomes the largest total weight the cache may hold. With every weight left at 1, this is exactly Part 1.

After a put, if the total weight is over capacity, remove expired items first (as in Part 2), then remove least recently used items one at a time until the total fits. One put can therefore remove several items.
Updating an existing key replaces its value and its weight. If the new weight pushes the total over capacity, other items are removed as above. The key just put is never removed.
If weight > capacity, raise ValueError and leave the cache unchanged.

Open this page on a laptop or desktop to write and run your code against the tests in the browser.

Approach

Spoilers: try each part before reading its walkthrough.

Part 1: LRU cache

The cache needs two things at once: find any key in O(1), and know which key has gone unused the longest. A dict answers the first question, and a list ordered by recency answers the second, but a plain Python list makes moving an item O(n). The fix is a doubly linked list whose nodes the dict points to: unlinking a node and relinking it at the newest end only touches its neighbours, so it is O(1). The oldest item sits at the other end, ready to drop. The reference solution uses OrderedDict, which is exactly this pairing built in: move_to_end(key) marks a key as newest and popitem(last=False) removes the oldest. On put, delete an existing key first so an update never triggers an eviction by mistake.

Part 2: Per-item expiry

Store each item's absolute expiry, now + ttl, or None when it never expires. A get compares now against that number; if the item is stale it is removed and the call returns -1. The harder rule is on put: when the cache is over capacity, every expired item must go before any live one. Scanning all items would be O(n), so the solution also pushes (expiry, version, key) onto a min-heap. When space is needed it pops from the heap while the top has expired, and removes the key only if the version still matches, because a later put of the same key leaves an outdated heap entry behind. Each heap entry is popped once, so the cost is amortized O(log n). If the cache is still too full after that, plain LRU eviction takes over.

Part 3: Weighted capacity

Weights change one thing: the cache is full when the sum of weights passes capacity, not when the item count does. Keep that sum in a counter, _total, and adjust it in exactly one helper that removes an entry, so inserts, updates and evictions can never disagree with it. On put, reject an item heavier than the whole cache before touching anything, so a failed call leaves the cache as it was. An update first removes the old entry, subtracting its old weight, then inserts the new one as the newest item. If the total is now too high, clear expired items, then pop from the oldest end in a loop until the total fits. The new key sits at the newest end and fits on its own, so the loop stops before reaching it. Each item is removed at most once, so eviction is amortized O(1).

Hints

Part 1 hint

Map each key to its list node so you can find it in O(1), and keep the nodes on a doubly linked list from newest to oldest. Sentinel nodes at both ends mean you never handle an empty list specially.

Part 2 hint

To find expired items without scanning, push (expiry, version, key) onto a min-heap and ignore heap entries whose version no longer matches the stored item.

Part 3 hint

Keep a running total of the stored weight. Update it on every insert, update and removal, then remove from the oldest end while the total is over capacity.

Common mistakes

Not moving a key to the newest position when it is read or updated.
Forgetting to update the tail (or head) pointer when the removed node is at the end of the list.
Evicting before checking whether the put is just an update, so an item is thrown out for nothing.
Evicting a live item while an expired one is still taking up space.
With weights, evicting only one item per put, or leaving the total wrong after an update changes an item's weight.

Where an interviewer could take it next

Keep hit, miss and eviction counters and report a hit rate.
Remove expired items in the background instead of only when the cache is full.
Rewrite it without OrderedDict, with your own node class, and compare memory per entry.

Complexity

get and put are O(1) with a hash map and doubly linked list (or OrderedDict). With ttl, put also pushes onto a heap in O(log n), and removing expired items is amortized O(log n) each because every heap entry is popped once. Weighted eviction removes each item at most once, so it is amortized O(1) per put. Memory is O(n) plus stale heap entries.

Frequently asked

How do you implement an LRU cache in Python?: Combine a dict with a structure that keeps keys in recency order. The quickest version uses collections.OrderedDict: call move_to_end on every read or write, and popitem(last=False) to drop the oldest key when the size passes capacity. Without OrderedDict, let the dict point at nodes of a two-way linked list framed by sentinel head and tail nodes, and move or unlink nodes by hand. Both give O(1) get and put.
How do you add TTL expiry to an LRU cache?: Save an absolute expiry time, now plus ttl, with each item. On get, treat an item whose expiry is at or before now as a miss and delete it. To clear stale items before evicting live ones without scanning the whole cache, keep a min-heap of expiry times with a version number per entry, and ignore any popped entry whose version differs from the item now cached.
Why are get and put O(1) in an LRU cache?: The dict finds a key's entry in constant time, and the doubly linked list lets you unlink that entry and attach it at the newest end by changing a few pointers, with no shifting of other items. Eviction removes the node at the oldest end, also a fixed number of pointer changes. No step depends on how many items are cached, so both operations are O(1) on average.

Practise next

Parking Lot Design

Stateful class design

In-Memory Key-Value Store with Transactions

In-memory database or key-value store

Time-Based Key-Value Store with TTL

Time-based state (expiry, TTL, snapshots)

See what candidates report at each company

The company guides collect the questions candidates report, with every part, the follow-ups interviewers added, and how often each one comes up.

Browse the interview guides