20 LRU Cache Interview Questions and Answers

20 LRU cache interview questions and answers that go past the canonical solution and show how to defend the design with invariants, edge cases, and correct.

Memorizing the hash map plus doubly linked list trick is not the hard part of LRU cache interview questions. The hard part is what comes after: the interviewer nods, says "okay, and why does that stay correct?", and suddenly the candidate who rehearsed the pattern has nothing left to say. That gap — between knowing the solution and being able to defend it — is where most mid-level engineers lose points they didn't expect to lose.

This guide is built around closing that gap. Not by giving you a longer solution to memorize, but by giving you the reasoning layer that makes every answer defensible: the two invariants the design has to maintain, the exact behavior of each operation, the edge cases that expose broken logic, and the bugs that show up in real interview code. Work through this once and you'll be able to answer the follow-up, not just the question.

The 30-Second Answer Interviewers Actually Want

What is the simplest interview-ready explanation of how an LRU cache works?

An LRU cache holds at most N items. Every time you access a key — whether reading or writing — that key becomes the most recently used. When the cache is full and a new key arrives, the least recently used item gets evicted to make room. The rule is simple: the item that hasn't been touched the longest is always the first to go.

The interview-ready version of that explanation has a specific shape: state the eviction rule first, then state the capacity constraint, then say what data structures enforce both. "We need O(1) lookup and O(1) recency updates, so we use a hash map for lookup and a doubly linked list for ordering. The map points to nodes in the list. Every access moves the node to the front. Eviction removes from the tail." That's 30 seconds. It tells the interviewer you understand what you're building before you start drawing boxes.

Why do interviewers keep pushing past the basic definition?

Because the definition is easy to recite and hard to understand. The probe that separates the two is almost always some version of: "Why not just use a hash map?" A hash map gives you O(1) lookup — but it gives you no ordering. You can find a key instantly. You cannot find the least recently used key without scanning everything. So eviction becomes O(N), which defeats the purpose of the cache entirely.

That probe exists because the interviewer wants to know whether you understand the constraint the design is solving, not just the design itself. Candidates who've only memorized the solution answer "because we need a linked list" without being able to say why. Candidates who understand the constraint answer "because a map alone can't tell you which key was touched least recently in constant time."

What should you say before you even draw the data structures?

State the two requirements the design has to satisfy, because everything else is just an implementation of those requirements. First: lookup must be O(1). Second: recency order must always be current. If either of those breaks, the cache breaks — not just in theory, but in the next operation. Framing the answer this way before touching a whiteboard signals to the interviewer that you're reasoning about correctness, not pattern-matching to a memorized solution.

This is the invariant-first framing, and it's what distinguishes answers that sound confident from answers that sound rehearsed. The structures come second. The requirements come first.

The Two Invariants That Make LRU Cache Work

What exactly has to stay true after every get and put?

An LRU cache implementation is correct if and only if two invariants hold after every single operation. First: the hash map always contains exactly the live keys, and each key maps to the correct node in the list. Second: the doubly linked list always reflects true recency order — most recently used at the head, least recently used at the tail. If either invariant breaks, the cache is lying. A lookup returns a stale pointer. An eviction removes the wrong item. The whole design depends on both invariants holding simultaneously, always.

These aren't abstract correctness conditions — they're the checklist you run through when you're done writing code. "Does every operation update the map? Does every operation update the list position?" If the answer to either is "sometimes," you have a bug.

How do you prove the recency order is never lying?

Walk through a small example and show the list state after each step. Start with an empty cache of capacity 2. Put A: list is [A]. Put B: list is [B → A]. Get A: A moves to the front, list is [A → B]. Put C: cache is full, tail is B, evict B, insert C at the front, list is [C → A].

At every step, the tail is genuinely the least recently used item. That's not a coincidence — it's the invariant in motion. Every access promotes to the head. Every eviction removes the tail. If you can trace that sequence out loud on a whiteboard and explain why the tail is always the right victim, you've proven the recency order is correct. That trace is the interview answer, not just the code.

Why the O(1) promise depends on both structures doing different jobs

The map solves lookup. Given a key, find the node in O(1). The list solves ordering. Given a node, move it to the front or remove it from the tail in O(1). Neither structure can do the other's job without a cost. A map with no list can find keys instantly but can't maintain order. A list with no map can maintain order perfectly but finding a specific key requires a linear scan. The doubly linked list is critical — not singly linked — because node removal requires updating the previous pointer, which you can only do in O(1) if you have a reference to the predecessor. Singly linked lists turn removal into another scan.

According to MIT OpenCourseWare's algorithm materials, hash tables with a good hash function provide expected O(1) lookup and insertion. Doubly linked list head/tail operations are unconditionally O(1). The combination is what makes the LRU design work — each structure is doing exactly the job it's built for.

Why One Data Structure Alone Always Fails

Why a hash map alone cannot solve recency updates

The failure mode is precise. A hash map can tell you whether a key exists and retrieve its value in O(1). What it cannot do is answer "which key was touched least recently?" without scanning every entry and comparing timestamps or counters. If you add a timestamp field to every value and then evict by scanning for the minimum timestamp, you've turned eviction into O(N). For a cache with a million entries, that's a million comparisons on every insert. The whole point of a cache is to make access fast — an O(N) eviction step makes the cache slower than not caching at all for write-heavy workloads.

This is the exact answer to "why not just use a map?" and you should be able to give it in two sentences without hesitating.

Why a doubly linked list alone cannot solve O(1) lookup

A list preserves order beautifully. It can move nodes to the front in O(1) if you already have a pointer to the node. But if someone calls `get("some_key")` and all you have is the key, you have to walk the list from the head until you find it. That's O(N) in the worst case. For a least recently used cache under real access patterns, the key you're looking for might be anywhere in the list — not just at the head. A list alone is a correct ordering structure and a broken lookup structure.

Why ordered collections are tempting — and still not the same answer

Python's `OrderedDict` and Java's `LinkedHashMap` are real implementations of LRU-like behavior. Python's `collections.OrderedDict` maintains insertion order and supports move-to-end operations, which is exactly what LRU needs. Using one in an interview is not wrong — but it's not what the interviewer is testing.

When an interviewer asks you to design an LRU cache, they're asking whether you understand why the underlying structure works: that ordered maps are themselves implemented with a hash table and a doubly linked list under the hood. If you reach for `OrderedDict` without explaining that, you've answered a different question. The right move is to acknowledge the library option, then say "but the underlying design is a hash map and doubly linked list, and here's why that combination satisfies both O(1) constraints." That answer gets full credit. The library shortcut without the explanation gets partial credit at best.

The Exact Behavior of get, put(existing), and put(full cache)

What happens on get when the key exists?

The full sequence for a cache hit: look up the key in the hash map, retrieve the pointer to the node in the doubly linked list, detach the node from its current position, reattach it at the head of the list, and return the value. Every step matters. The detach-and-reattach is where bugs live — you have to update four pointers correctly (the node's neighbors close the gap, the node takes the old head's position, the head pointer updates). If you skip any of those, the list silently corrupts.

The reason the move matters: if you call `get("A")` ten times in a row, A should stay at the head every time. A correct implementation handles repeated reads without creating duplicate nodes or leaving stale pointers. An LRU cache design that only moves nodes on write and not on read is wrong — reads are accesses, and accesses update recency.

What happens on put when the key already exists?

This is the operation that most sloppy implementations get wrong. The sequence: look up the key in the map, update the value in the existing node, detach the node from its current position, reattach it at the head. Do not insert a new node. Do not add a second map entry. The cache size should not change.

The duplicate put is the stress test for this path. If you call `put("A", 1)` and then `put("A", 2)`, a broken implementation might insert a second node for A, leaving two entries in the list and one in the map — or two in both. Now the map is inconsistent and eviction will eventually remove the wrong item. The correct implementation checks for existence first, every time, without exception.

What happens on put when the cache is full?

This is the eviction path, and it has four steps that must happen in the right order. First: identify the tail node — that's the least recently used item. Second: remove its key from the hash map. Third: detach the tail node from the list. Fourth: insert the new key-value pair as a new node at the head, and add the new key to the map pointing at that node.

The order matters because if you insert the new node before removing the tail's map entry, you might accidentally overwrite a map entry if the new key happens to be the same as the tail's key — which is a degenerate case, but a correct implementation handles it. Remove first, insert second. This is also where a sentinel head and tail node pattern pays off: with dummy head and tail nodes, you never have to check for null neighbors during eviction. The tail sentinel's previous node is always the real LRU item.

CLRS (Introduction to Algorithms) covers doubly linked list operations with sentinel nodes in detail — the sentinel pattern eliminates the null-check edge cases that cause pointer bugs in interview code.

The Edge Cases People Forget Until the Interview Goes Sideways

Why capacity 1 is the easiest way to expose broken logic

A cache with capacity 1 has no room for subtlety. Every put either updates the single existing item or evicts it and replaces it. Every get either hits the one item or misses. This strips away every assumption about "there's always something in the list" and forces your implementation to handle the case where head and tail are the same node simultaneously.

Run this sequence mentally: capacity 1, put(A, 1). Cache: [A]. Put(B, 2). Cache should be [B], A evicted. Get(A): should return -1. Put(B, 3): should update B's value, list stays [B], size stays 1. If any of those produce wrong output, the implementation has a bug that a larger capacity was hiding.

What should happen when you ask for a missing key?

The standard contract is to return -1 (or null, depending on the language). The important follow-up is: does a miss affect recency? It should not. A get on a missing key is a no-op for the list. Nothing moves. Nothing gets promoted. The list state after a miss is identical to the list state before it. Implementations that accidentally update recency on a miss — perhaps by inserting a null entry — are wrong and will fail on the next eviction.

Why repeated gets can hide a bug in plain sight

Call `get("A")` five times in a row on a cache where A is the only item. The correct behavior: A stays at the head each time, value returned correctly, no structural changes after the first promotion. A buggy implementation might create a new node on each call, gradually corrupting the list. Or it might fail to close the gap when detaching A from a position it was already at — which is a no-op for a single-item cache but breaks on the second item.

The LRU cache algorithm invariant check here: after five repeated gets on A, the map should have exactly one entry, the list should have exactly one node, and that node should be at the head. If any of those fail, the bug was always there — the test just didn't expose it until now.

How to Prove the Implementation Is Correct

What is the shortest correctness argument that still sounds serious?

State the two invariants, then show that each operation preserves both. "After every operation, the map contains exactly the live keys pointing to correct nodes, and the list is ordered from most to least recently used." Then walk through each operation type and show it maintains both invariants. That's a proof by maintained invariant — the same structure used in formal algorithm analysis — and it takes about 90 seconds to deliver out loud.

This is the answer that separates candidates who've done LRU cache interview questions seriously from candidates who've only coded the solution. The code can be right by accident. The invariant argument can only be right if you understand why.

How do you talk through the state before and after each operation?

For each of the three operation types, describe the before state, describe what the operation does, and describe the after state. Get (hit): before, key K is somewhere in the list. After, K is at the head, everything else shifted one position later in recency. Put (existing): before, K is somewhere in the list with old value V. After, K is at the head with new value V', same node, same map entry. Put (full): before, cache has N items, tail is the LRU item. After, tail is evicted, new key is at the head, map updated for both the evicted key (deleted) and the new key (inserted).

If you can describe those three state transitions cleanly without looking at code, you've demonstrated the kind of reasoning that makes interviewers confident the implementation is correct — not just the implementation itself.

What follow-up question usually tries to break your proof?

"How do you know the tail is really the least recently used?" This is the right question to ask, and interviewers who are paying attention will ask it. The answer is the invariant: every access moves a node to the head, and no operation ever moves a node toward the tail except relative displacement from a newer access. The tail is the LRU item because the only way to become the tail is to have been displaced by every other item in the cache. That's not a claim you verify by inspection — it's a consequence of the invariant holding after every operation.

Skiena's Algorithm Design Manual discusses invariant-based correctness arguments for data structure operations — the same reasoning pattern applies directly here.

The Bugs That Show Up in Real Interview Code

Which pointer bug destroys the list fastest?

Broken node removal. When you detach a node from the middle of the list, you need to update four references: the node's previous neighbor's `next` pointer, the node's next neighbor's `prev` pointer, and then the node's own `prev` and `next` pointers (typically set to null or to the new position). Missing any one of those leaves a dangling reference. The next operation that touches either neighboring node will follow a stale pointer and corrupt the list silently — no exception, no immediate failure, just wrong behavior on the next eviction.

The fix is to always write node removal as a single isolated function that handles all four pointer updates, and call that function everywhere. Never inline the pointer manipulation at the call site — it's too easy to miss one.

Why do people forget to update the hash map after moving a node?

Because moving a node doesn't change the key or the value — it only changes the node's position in the list. The map still points to the same node object, so the pointer stays valid. But if the implementation creates a new node instead of moving the existing one (a common mistake in put-existing), the map now points to the old, detached node. The next get on that key retrieves the old value from a node that's no longer in the list. The next eviction might try to remove a node that's already orphaned.

The rule: never create a new node for a key that already exists in the map. Always reuse the existing node and update its value in place.

What does a bad eviction step usually look like?

The most common version: the implementation removes the tail node from the list but forgets to delete its key from the hash map. The next `get` on the evicted key finds the map entry, follows the pointer to the detached node, and returns the value — even though that item was supposed to be gone. The cache now has a ghost entry: present in the map, absent from the list, invisible to eviction. Over time, ghost entries accumulate and the effective cache capacity shrinks.

The fix is simple: always delete the map entry before or immediately after detaching the tail node, in the same operation, with no code path that can skip it.

When LRU Is the Wrong Policy Entirely

When does least-recently-used stop being the right rule?

Recency is a good proxy for future usefulness when access patterns have temporal locality — recently used items are likely to be used again soon. That assumption breaks under sequential scans. If a workload reads every item in a large dataset once, in order, LRU evicts items that are about to be accessed again and keeps items that will never be accessed again. This is called cache pollution, and it's why database buffer pools often use variants like LRU-K or clock-based policies for scan-heavy workloads.

Frequency-based policies like LFU (Least Frequently Used) are better when some items are accessed constantly across long time windows — a small set of hot keys that LRU would never evict anyway, but where the surrounding access pattern makes LRU's recency tracking irrelevant.

What should you say about TTL, memory pressure, and production reality?

A production cache almost never runs pure LRU. Real systems add TTL (time-to-live) so stale data expires even if it's frequently accessed. They add memory pressure handling so the cache shrinks gracefully when the host is under load, rather than holding its capacity limit rigidly. They add tiered eviction — soft limits that trigger background eviction before hard limits that block writes.

The senior-level point is this: the interview solution is a correct LRU cache. A production cache is an LRU cache plus expiry, plus memory accounting, plus monitoring, plus fallback behavior when the backing store is slow. Knowing where the clean interview design ends and the real engineering begins is what distinguishes a senior answer from a mid-level one.

Why concurrency changes the conversation

The clean interview implementation is single-threaded. A concurrent get and put on the same key, running simultaneously, can corrupt the list in ways that are nearly impossible to reproduce in testing. The standard fix — a global lock around every operation — is correct but turns the cache into a serial bottleneck under high read concurrency.

Real systems use read-write locks, sharded caches (partition the key space so different shards lock independently), or lock-free structures like concurrent skip lists. Java's `ConcurrentLinkedHashMap` (the basis for Caffeine, a widely used caching library) uses a different approach entirely: it batches recency updates asynchronously rather than updating the list on every access. That's a deliberate tradeoff — slightly stale ordering in exchange for dramatically better throughput. If the interviewer asks about thread safety, the right answer is to name the tradeoff, not to pretend a global lock is the only option.

How Verve AI Can Help You Ace Your Software Engineer Coding Interview

The problem with practicing LRU cache on a whiteboard alone is that the invariant argument only gets sharp when someone pushes back. You can trace the capacity-1 edge case perfectly in your notes and still fumble it when an interviewer asks "but how do you know the tail is really the LRU item?" — because the pressure of a live follow-up is a different skill than solo preparation. Verve AI Interview Copilot is built for exactly that gap. It listens in real-time to your answer as you give it, responds to what you actually said rather than a canned prompt, and surfaces the follow-up you weren't ready for — the one about pointer correctness, or why your eviction step leaves a ghost entry in the map. Verve AI Interview Copilot stays invisible while it does this, so you're practicing under realistic conditions rather than a sanitized rehearsal environment. The specific capability that changes the calculus for LRU prep is that Verve AI Interview Copilot can run the full get/put/eviction sequence with you, catch the moment your invariant argument gets vague, and push back before the real interviewer does.

Conclusion

The move that makes LRU cache answers defensible is not memorizing more code — it's being able to say, at any point in the answer, "here's what has to be true after this operation, and here's why it is." The hash map and doubly linked list are just the structures that make those invariants cheap to maintain. The invariants are the actual answer.

Before your next interview, do two things. First, practice the 30-second version out loud: eviction rule, capacity constraint, two structures, two invariants, one sentence each. Second, trace the capacity-1 sequence — put(A), put(B), get(A), put(C) — and explain the list state after every step without looking at code. If you can do both without hesitating, you're not just prepared to answer the question. You're prepared to defend it.