LRU Caches: How to Explain Them in an Interview (2026)

When an interviewer asks about an LRU (Least‑Recently‑Used) cache, they want to see that you understand both the what and the how.

One‑Sentence Definition

An LRU cache stores a limited number of items and discards the item that hasn't been accessed for the longest time whenever a new entry needs space.

Core Mechanism

The classic implementation uses two data structures working together:

1. Hash map – maps keys to nodes for O(1) lookup.
2. Doubly‑linked list – orders nodes from most‑recent to least‑recent. On every get or put, you move the accessed node to the front; when the capacity is exceeded you remove the tail node.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}                     # key -> node
        self.head = Node(0, 0)            # dummy head
        self.tail = Node(0, 0)            # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_front(node)
        return node.val

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self._add_to_front(node)
        self.map[key] = node
        if len(self.map) > self.capacity:
            # evict LRU
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

The code shows the constant‑time operations that interviewers love to see.

Trade‑offs

If the cache is tiny or the workload is read‑only, a simple array with a FIFO policy can be enough. When you need to weight recentness against frequency, a LFU or 2Q variant may be more appropriate, but those add algorithmic complexity.

Concrete Example

Imagine a web service that fetches user profiles from a database. The service receives many requests for the same handful of users during a peak hour. By caching the last 100 profiles, you avoid repeated DB hits. If a request for a new user arrives when the cache is full, you evict the profile that hasn't been requested for the longest time. This keeps the most active users in memory and reduces latency.

Typical Interview Questions

1. Explain the data structures you would use and why. – Expect you to mention the hash map + doubly‑linked list and argue O(1) operations.
2. What is the time and space complexity? – Answer O(1) for get/put, O(n) overall space where n is capacity.
3. How would you modify the design for a multi‑threaded environment? – Discuss locking strategies or lock‑free structures.
4. What if the items have different sizes? – Suggest a size‑aware eviction policy or a weighted LRU.
5. Can you implement remove(key)? – Show that you can locate the node via the hash map and splice it out.
6. How would you test the cache? – Propose unit tests for insertion, eviction order, and edge cases like capacity 0.

60‑Second Spoken Answer

"An LRU cache holds a fixed number of items and throws away the one that hasn't been used for the longest time when it needs space. The usual implementation combines a hash map for O(1) lookups with a doubly‑linked list that tracks recency; each access moves the node to the front, and when the capacity is exceeded you pop the tail. This gives constant‑time operations and predictable memory use, though you pay a small overhead for the extra pointers. In practice, it's useful for things like caching recent database rows or API responses, where you want to keep hot data readily available. Interviewers often follow up by asking about thread safety, handling variable‑size items, or writing a quick implementation."

If you rehearse this answer aloud, you can keep the flow tight and avoid filler. Call Assistant can record your practice run and surface follow‑up prompts so you stay on topic.

How to practice this

1. Write the code from memory – Close the editor, sketch the hash‑map + list implementation on paper, then type it out without looking.
2. Run a mock interview – Use a colleague or a tool like Call Assistant to ask you the common follow‑up questions and time your spoken answer.
3. Create edge‑case tests – Build unit tests for capacity 0, duplicate puts, and concurrent access to solidify your mental model.

---