L2 · Working engineerAdvanced L2~15 min · 5 tests#81

Implement an LRU Cache in Python

Build an LRU cache with O(1) get and put using OrderedDict (or a dict plus doubly linked list) and capacity-based eviction. A top Python interview question.

The problem

Implement LRUCache(capacity):

get(key) returns the value, or -1 if missing. A successful get marks the key most recently used.
put(key, value) inserts or updates. If this exceeds capacity, evict the least recently used key.

Both operations must be O(1).

Examples

Example 1

Input

run_ops(LRUCache, [2], [["put", 1, "A"], ["put", 2, "B"], ["get", 1], ["put", 3, "C"], ["get", 2]])

Expected output

[None, None, 'A', None, -1]

Example 2

Input

run_ops(LRUCache, [2], [["put", 1, 1], ["put", 2, 2], ["put", 1, 10], ["put", 3, 3], ["get", 2], ["get", 1]])

Expected output

[None, None, None, None, -1, 10]

+ 3 hidden tests on Submit — capacity 1.

Edge cases to ask about

Capacity 1
Updating an existing key refreshes it
Get on a missing key

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · LRUCache

class LRUCache:
    def __init__(self, capacity):
        pass

    def get(self, key):
        pass

    def put(self, key, value):
        pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
List of keys for recency	O(n) per op	O(n)	list.remove and pop(0) are linear.
OrderedDict	O(1) per op	O(n)	move_to_end and popitem(last=False) are O(1).
bestDict + doubly linked list	O(1) per op	O(n)	What OrderedDict does inside — expected if the interviewer bans OrderedDict.

Walkthrough of the optimal approach (try it yourself first)

An LRU cache needs a hash map (O(1) lookup) and an ordering (O(1) move-to-front, O(1) remove-oldest). OrderedDict is exactly that pair: move_to_end(key) on every access, popitem(last=False) to evict the oldest.

If the interviewer bans OrderedDict, build it: a dict of key → node, with nodes in a doubly linked list between sentinel head and tail nodes. Updating an existing key must also refresh its recency — the second visible case checks that.

Complexity: O(1) time, O(n) space. OrderedDict keeps a hash map for lookup and a linked list for order, so lookup, move-to-end and evict-oldest are all O(1). It stores up to `capacity` entries.

Reveal the reference solution

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

The brute force, for comparison

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.keys = []          # least recent first — O(n) remove
        self.values = {}

    def get(self, key):
        if key not in self.values:
            return -1
        self.keys.remove(key)
        self.keys.append(key)
        return self.values[key]

    def put(self, key, value):
        if key in self.values:
            self.keys.remove(key)
        self.keys.append(key)
        self.values[key] = value
        if len(self.keys) > self.capacity:
            del self.values[self.keys.pop(0)]

Follow-ups interviewers ask

Implement it without OrderedDict.
Make it thread-safe.
LFU cache instead.

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Implement an LRU Cache in Python?

The optimal solution runs in O(1) time and O(n) auxiliary space. OrderedDict keeps a hash map for lookup and a linked list for order, so lookup, move-to-end and evict-oldest are all O(1). It stores up to capacity entries.

What is the brute-force approach, and how do you optimise it?

List of keys for recency: O(n) per op time, O(n) space. list.remove and pop(0) are linear. OrderedDict: O(1) per op time, O(n) space. move_to_end and popitem(last=False) are O(1). Dict + doubly linked list: O(1) per op time, O(n) space. What OrderedDict does inside — expected if the interviewer bans OrderedDict.

What follow-up questions do interviewers ask about Implement an LRU Cache in Python?

Implement it without OrderedDict. Make it thread-safe. LFU cache instead.