How to Implement an LRU Cache in Python for Technical Interviews

LRU Cache: Python Basics & Intuition

Think of your music streaming app's "recently played" playlist. It only holds, say, 10 songs. When you play a new song, it gets added to the front. If the playlist is full, the song at the very back—the one you haven't heard in the longest time—gets kicked out to make room.

That's the core intuition of an LRU (Least Recently Used) cache: it automatically discards the least recently accessed item when it reaches capacity. An LRU cache is a fixed-size storage that remembers the most recently used items. When you get or put an item, it becomes "most recent."

A common mistake is thinking you can build this with just a Python list or a plain dict. Let's see why they fail for our O(1) time requirement.

Why a simple list fails

You could keep items in order of use. To get an item, you'd have to search the list—O(n) time. To update it to "most recent," you'd have to remove it from its current position and insert at the front—also O(n) because shifting elements is expensive.

# This feels intuitive but is too slow for interviews
class SlowListCache:
    def __init__(self, capacity):
        self.cache = []  # [(key, value)] ordered by recency
        self.capacity = capacity

    def get(self, key):
        for i, (k, v) in enumerate(self.cache):
            if k == key:
                # O(n) search + O(n) move to front
                self.cache.pop(i)
                self.cache.insert(0, (k, v))
                return v
        return -1

    def put(self, key, value):
        # O(n) search for existing key
        for i, (k, _) in enumerate(self.cache):
            if k == key:
                self.cache.pop(i)
                self.cache.insert(0, (key, value))
                return
        if len(self.cache) >= self.capacity:
            self.cache.pop()  # O(1) remove last, but...
        self.cache.insert(0, (key, value))  # O(n) insert at front

Why a simple dict fails

A Python dict gives you O(1) lookups and inserts, but it doesn't remember order of use. Starting in Python 3.7, dicts preserve insertion order, not access order. If you update an existing key's value, its position doesn't change.

# Dict remembers insertion order, not access order
d = {'a': 1, 'b': 2}
d['a'] = 3  # 'a' stays in first position. It updates in place.

# But if we 'get' 'a', we want it to become "most recent".
# Dict can't do that automatically without extra work.

The key insight: we need fast lookup (like a dict) and fast reordering (to move items to "most recent" and evict the "least recent"). This is why the standard solution combines a hash map (for O(1) access) with a doubly linked list (for O(1) rearrangement). You'll implement that next. For now, internalize this: LRU isn't just a rule—it's a performance constraint that demands a specific data structure marriage.

LRU Cache Implementation Strategies

To achieve that holy grail of O(1) time complexity for both get and put, we face a dilemma. No single built-in Python structure does both instant lookup and instant reordering.

The solution is to combine two data structures so they work together as one cohesive unit:

Think of the Hash Map as the index of a book. It tells you exactly which page (memory address) a topic is on. The Doubly Linked List is the book itself, ordered by how often you read the pages.

Why a Doubly Linked List?

You might wonder: "Why not just a standard Linked List?"

When we get(key), we find the node instantly via the Map. But now we need to move it to the front. In a standard (singly) linked list, removing a node from the middle requires access to its previous node to update its next pointer. Without that previous node, you'd have to traverse from the start—costing O(n).

A Doubly Linked List solves this. Every node has a prev and next pointer. Once the Map gives us the target node, we can "splice" it out of its current spot and plug it into the head using just its neighbors' pointers. This is an O(1) pointer operation.

The "List + Dict" Trap

A common trap for beginners is trying to use a Python list to store the keys in order, and a dict to store the values.

# ❌ The Trap: Moving items in a Python list is O(n)
def bad_approach(self, key):
    # 1. O(1) lookup in dict
    value = self.dict[key] 
    
    # 2. O(n) search to find index in list
    index = self.list_of_keys.index(key) 
    
    # 3. O(n) remove and insert (shifting elements)
    self.list_of_keys.pop(index)
    self.list_of_keys.insert(0, key)
    
    return value

Even if you store the index in the dict, moving one item shifts the indices of all subsequent items, forcing you to update them all. The Doubly Linked List is the only way to move an item without touching its neighbors' indices.

Data Structures Deep Dive: The LRU Recipe

When an interviewer asks you to implement an LRU cache, they aren't just testing your coding speed. They are testing your ability to choose the right tools for the job.

The correct answer isn't "use a dict and a list"—it's about combining a hash map and a doubly linked list to meet the strict O(1) requirement. Let's break down why these two structures, and only these two, work together.

You need two things simultaneously:

• Instant key lookup → use a hash map (Python dict). This lets you find any entry by key in O(1) time.
• Instant reordering and eviction → use a doubly linked list. This lets you move any node to the front (most recent) or remove the tail (least recent) in O(1) time, as long as you already have a pointer to that node.

The magic is in how they connect: the hash map doesn't store values directly—it stores pointers to nodes in the linked list. So when you get(key), the hash map instantly gives you the node; you then move that node to the head of the list via pointer manipulation. No searching, no shifting.

Intuition: Hash Map for Key Lookup, Linked List for Order

Think of the doubly linked list as a timeline: head = most recently used, tail = least recently used. Every node holds (key, value). The hash map is your fast-access directory: key → node_pointer.

Here is how the operations flow:

• get(key): Hash map finds node → move node to head (O(1) pointer updates) → return value.
• put(key, value): If key exists, update value and move node to head. If new and cache full, evict tail (remove tail node from list and its key from hash map) → add new node to head and store its pointer in hash map.

All operations are O(1) because hash map lookup is always instant, and linked list operations are instant when you have the node—and the hash map gives you that node instantly.

Mapping Keys to Nodes

This is the critical integration point. Your hash map's values are not the raw data—they are references to list nodes. Here is the mental model you need to build:

# The Node Structure
class Node:
    def __init__(self, key, value):
        self.key = key    # Needed to delete from hash map on eviction
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key → Node
        
        # Dummy Head and Tail eliminate edge cases
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

Notice the dummy head and tail—they eliminate edge cases when adding/removing nodes. The cache dict maps keys directly to Node objects. When you need to evict, you go to self.tail.prev (the real least-recent node), get its key, and delete self.cache[key].

Common Misconception: Any Linked List Works?

Some students think: "Why not a singly linked list? I can still add to head and remove from tail." The problem is removing an arbitrary node (when you get an existing key and need to move it to the head).

In a singly linked list, to remove a node you need its predecessor. To find the predecessor, you'd have to traverse from the head—O(n) time. That breaks the O(1) guarantee.

A Doubly Linked List gives each node a prev pointer. When the hash map hands you a node, you can immediately:

# Splicing out a node in O(1) using prev/next pointers
node.prev.next = node.next
node.next.prev = node.prev

You do this in constant time, without traversal. Then you reinsert at head. That's why the doubly linked list is non-negotiable for O(1) LRU. In an interview, explicitly stating this—"a singly linked list would require O(n) traversal to remove a node, so we need doubly linked for O(1) removal given a pointer"—shows deep understanding.

Cache Eviction Policies: Why LRU?

Before we write a single line of code, we need to agree on the rules of the game. When your cache is full, what do you throw away?

This rule is called the Eviction Policy. It is a design choice, not just a coding detail. While LRU (Least Recently Used) is the gold standard for interviews, it's important to understand why we choose it over the alternatives.

In the simulation above, notice the critical difference at the end:

• FIFO kicked out A because it was the oldest entry. This is bad if A is actually the most popular item!
• LRU kicked out B because it was the least recently used. It correctly identified that A was accessed in step 3, making it "hotter."
• LFU also kicks out B (assuming we track frequency), because A was accessed twice while B only once.

Intuition: The "Desk Drawer" Analogy

Imagine a small desk drawer (your cache) with limited space. You put tools in when you need them.

LRU is based on human intuition: If you haven't used a tool in months, it's probably safe to remove it to make room for a new one. If you use a tool every day, you keep it at the front.

This matches the Principle of Temporal Locality in computer science: programs tend to reuse data they've used recently. LRU exploits this by keeping "hot" items accessible.

Common Misconception: "LRU = Oldest Entry"

This is the most dangerous trap in interviews. Students often think:

"LRU just means 'remove the oldest item I put in here'."

Incorrect. LRU removes the item that was accessed the longest time ago.

Look at the sequence again:

Even though A was inserted before B, A was accessed after B. Therefore, A is "more recent." LRU correctly preserves A and evicts B.

Edge Cases & Limitations

LRU isn't perfect. It assumes that recent use predicts future use. This fails in specific scenarios:

• Thrashing: If your working set is larger than the cache, LRU will constantly evict items you need again immediately. Example: Capacity 2, access pattern [1, 2, 3, 1, 2, 3...]. You will never hold both 1 and 2 at the same time.
• One-Hit Wonders: If a user scans through 100 unique items, LRU will fill the cache with "junk" and evict the "hot" items that were used long ago but might be needed again later.

Despite these flaws, LRU is the standard interview answer because it balances implementation complexity (easy to do with a Doubly Linked List) with performance (great for most web/database workloads).

System Design Caching Considerations

In a real-world system architecture, a cache is your speed layer sitting in front of a slower data store (like a database). Its job is to absorb read load and reduce latency. But simply slapping an LRU cache on top isn't a silver bullet. The eviction policy determines what data lives in that speed layer.

LRU's role is to automatically retain the most relevant recent data based on access patterns. This leverages temporal locality: the data you accessed a moment ago is the data you're likely to access again soon.

The simulation shows the critical difference:

• Read-Heavy: LRU shines. When you access "User A" repeatedly, it stays at the front (hot). The cache learns what's popular without extra configuration.
• Write-Heavy: LRU struggles. Every new log (D, E, F) is "recent" by definition. It pushes out old logs (A, B, C) even if you might need them later. In this case, a simple FIFO (First-In, First-Out) is often just as effective and cheaper to implement.

Rule of Thumb: Match the Policy to the Pattern

Don't just default to LRU. Ask yourself: "Is my workload dominated by reads or writes?"

The Distributed Systems Trap

A common interview pitfall is assuming the LRU design that works on a single server scales perfectly to a distributed system (like Redis Cluster or Memcached). It doesn't.

This is why true Global LRU is expensive to implement at scale—it requires constant synchronization between nodes.

Interview Takeaway: When discussing caching in system design, always clarify the scope.

# Interview Answer Strategy
"For a single-server cache, LRU with a hash map + doubly linked list is O(1) and perfect."
"In a distributed cache, we typically use per-node LRU and accept approximate behavior."
"We rely on high capacity per node so that even with skew, the hot set fits locally."

Testing and Debugging LRU Cache in Python

Testing an LRU cache isn't just about checking if get and put return the right values. The most subtle bugs hide in the recency ordering invariant.

You might have a broken linked list (e.g., a missed prev update) but still get the correct value from the hash map. Your tests must verify that the internal order is correct after every operation. If the order is wrong, your eviction policy will fail later.

Intuition: Stress-Test the Recency Order

Think of your cache as a timeline. Every get or put on an existing key should move that key to the "most recent" end. Your tests need to peek at the internal order to confirm these movements happen correctly.

If you only test return values, you might miss that the list order is corrupted. The hash map lookup might still work, but the eviction order will be broken.

Unit Test Strategy: Expose the Order

Add a simple method to your LRUCache class for testing only. This is your "debugging window" into the linked list.

# Helper method for testing only
def _get_order(self):
    """Return list of keys from most recent (head) to least recent (tail)."""
    keys = []
    node = self.head.next
    while node != self.tail:
        keys.append(node.key)
        node = node.next
    return keys

# Now you can write precise assertions
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache._get_order() == [2, 1]  # 2 is most recent, 1 is least recent

cache.get(1)  # moves 1 to most recent
assert cache._get_order() == [1, 2]

cache.put(3, 3)  # evicts 2 (least recent)
assert cache._get_order() == [3, 1]
assert cache.get(2) == -1  # confirm eviction

Test Cases for Eviction and Ordering

Cover these scenarios systematically to ensure your pointers are wired correctly:

• Basic eviction at capacity: Capacity 2: put(1), put(2), put(3) → evicts 1. Verify order is [3, 2].
• Update existing key: put(1), put(2), put(1, 10) → order becomes [1, 2] (1 moves to front). No eviction occurs.
• Repeated get: get(1), get(1) → order remains [1, 2].
• Alternating access: Capacity 3: put(1,2,3), get(1), put(4) → evicts 2. Order: [4, 1, 3].
• Capacity 1 edge case: put(1), put(2) → evicts 1. Order [2].

Common Misconception: Identical Keys Hide Bugs

A test that only checks return values might pass even with a broken list order.

"I tested get(1) and it returned 1. The cache works!"

Incorrect. If your _remove logic forgot to update node.next.prev, the list has a "hole." The hash map still finds the value, so get passes. But your eviction logic will break later because the "least recent" pointer is pointing to the wrong node.

To catch this, always assert the order after each operation when testing. The order is the single source of truth for LRU behavior.

How to Detect Subtle State Errors

If your implementation fails a test, the order assertion will show what the list thinks is most/least recent. Common failure patterns:

• Node not moved on get/put update: Order stays the same after accessing an existing key. Fix: ensure you call _remove(node) then _add_to_front(node).
• Evicts wrong node: After put when full, check _get_order(). The evicted key should be the last element before insertion.
• Duplicate keys in list: Happens if you add a new node without removing the old one when put-ing an existing key. Check that the number of nodes equals len(self.cache).
• Circular reference or lost nodes: If _get_order() runs forever or returns fewer keys than expected, your prev/next pointers are miswired.

Debugging tip: After each operation in your test, print _get_order() and compare to your expected sequence. The moment the order diverges, you know exactly which operation caused the pointer error. This beats guessing from failed return values alone.

Remember: the hash map must always agree with the list. After every put/get, len(self.cache) should equal the number of nodes between head and tail.

Performance Profiling of LRU Cache in Python

You've built an LRU cache that should run in O(1) time per operation. But in an interview, "should" isn't enough. You need to prove it.

This is where profiling comes in. Profiling means measuring execution time across varying input sizes to see if runtime stays constant (O(1)) or grows (O(n), O(log n), etc.). For an LRU cache, you test get and put with different capacities and check if the time per operation remains flat as capacity increases.

If your implementation is truly O(1), doubling the cache size should not double the time for a single get or put. The time should hover around the same baseline. If time grows linearly with capacity, you've accidentally introduced an O(n) operation—likely from a list search you thought was constant.

Simple Profiling Setup in Python

Here is how you would structure a basic profiler script to verify your own code:

# Basic Profiling Script
import timeit
from your_module import LRUCache

def profile_operations(capacity, num_ops):
    cache = LRUCache(capacity)
    # Warm up
    for i in range(capacity):
        cache.put(i, i)
    
    # Measure 'get' operations
    get_times = []
    for _ in range(num_ops):
        key = _ % capacity  # Ensure a 'hit'
        start = timeit.default_timer()
        cache.get(key)
        get_times.append(timeit.default_timer() - start)
    
    return sum(get_times) / num_ops

# Test across capacities
for cap in [10, 100, 1000, 10000]:
    avg_time = profile_operations(cap, 1000)
    print(f"Cap {cap}: avg_get_time={avg_time:.8f}s")

Intuition: Using Profiling Tools to Confirm O(1)

The key insight is to isolate the operation you're measuring. A single timeit call measures one operation, but you need many repetitions to average out noise (like CPU interrupts). More importantly, you must test both hits and misses, and updates vs. inserts, because they exercise different code paths.

• get hit: Hash map lookup + move node to head.
• get miss: Hash map lookup only (fast path).
• put update: Hash map lookup + move node + value update.
• put insert (with eviction): All of the above plus tail removal and hash map delete.

Each path should be O(1). When profiling, vary the mix of these operations to match realistic workloads. A common interview follow-up is: "How would you test that your LRU actually evicts the least recently used item?" That's where the order-checking tests from the previous section come in—profiling alone doesn't verify correctness, only speed. You need both.

Common Misconception: Microbenchmarks vs. Real World

A microbenchmark that only tests one operation in isolation (e.g., 10,000 consecutive get hits) can be misleading. It shows the best-case scenario. But real workloads have mixed access patterns that stress different parts of your code.

Pitfalls in Self-Testing

When you profile your own code, watch for these common traps:

• Python's Garbage Collection: Large, repeated object creation (like many new Node instances during evictions) can trigger GC pauses that skew timing. Run multiple trials and take medians.
• CPU Caching Effects: For very small capacities (e.g., 10), everything fits in CPU cache, making it artificially fast. As capacity grows and spills to RAM, times increase—but that's memory latency, not algorithmic complexity.
• Measurement Overhead: timeit itself has tiny overhead. Use large num_ops (e.g., 10,000) so the per-operation overhead becomes negligible.

Interview Tip: You don't need to actually run the profiler during the interview (unless asked). But you should be able to describe how you'd set up the test and what results would confirm O(1) behavior. Mention the two patterns (best-case hits vs. worst-case evictions) and the importance of varying capacity. That demonstrates engineering rigor.

Frequently Asked Questions (FAQ)

"Professor, I think I understand the theory, but I have some specific concerns."
Don't worry. These are the exact questions I hear most often in my office hours. Let's clear up the confusion about implementation, memory, and system design.

# This looks clean but fails the O(1) requirement
class SlowCache:
    def __init__(self, capacity):
        self.order = []  # keys in recency order
        self.cache = {}  # key → value
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        # O(n) search to find key in list
        idx = self.order.index(key)
        self.order.pop(idx)      # O(n) due to shifting
        self.order.insert(0, key)  # O(n) again
        return self.cache[key]