Designing an LRU cache: the low-level design interview, explained

Designing an LRU cache: the low-level design interview, explained

The LRU cache sits on a strange line between a data-structure puzzle and a low-level design interview. You may have solved it once on LeetCode by memorising that the trick is "a hash map and a doubly linked list" — but in an LLD round, reciting the trick is the start of the conversation, not the end. The interviewer is not checking that your solution passes hidden tests; they are watching how you design the class: the API you expose, the internal structures you choose and why, how you keep both operations genuinely O(1), and what you do when they add thread safety, a different eviction policy, or an expiry time. The LRU cache is a favourite precisely because the happy-path answer is well known, so all the signal is in how you reason about the design around it.

This guide walks the LRU cache the way a strong candidate works it in an LLD / OOD interview: pin down the requirement that forces the design, choose the data structures and justify them against the alternatives, sketch the class, and then defend the decisions the interviewer always pushes on — making it thread-safe, swapping the eviction policy, and adding TTL. In a low-level design round you write this class out in an editor and explain each pointer move and each design choice out loud, not as a puzzle you are racing to finish but as a component you are designing to last.

Why the LRU cache comes up in low-level design interviews

The LRU cache earns its place because it forces one hard constraint — both get and put in O(1) — and that single constraint drives every design decision that follows. Choose the wrong data structure and you cannot hit it; choose the right pair and the whole design falls out. On top of that, the interviewer can extend it in directions that are pure design, not algorithm: make it safe for concurrent callers, let the eviction policy change, bound entries by age. That mix of a crisp constraint and open-ended extension is exactly what an LLD round wants.

The interviewer rarely lets "a hash map and a doubly linked list" stand on its own. "Good — now two threads hit this cache at the same time: one calls get(x), which moves node x to the front of your list, while the other calls put(y), which evicts from the tail and might be touching the same pointers. Walk me through exactly where those two operations collide, what breaks in your linked list, and how you'd make it thread-safe without turning every call into a global bottleneck." That question — concurrency on shared pointers — is the one a memorised solution can never survive, and the one the LRU cache is really testing in an LLD round.

The rounds on Zynter are modelled on how the loop runs, not scraped from any candidate's recall. What matters for prep is the shape: you state the data-structure choice, and the next sentence attacks a seam — the O(1) claim, a concurrent access, a different policy, or an entry that should have expired.

What the interviewer is really testing

A low-level design answer is read on the same four dimensions as any design round. Problem solving — did you pick structures that actually deliver O(1) and justify them, or reach for a list and hope? Communication — can you explain why a doubly linked list, not a singly linked one, in a single sentence? Technical execution — do you handle the real extensions (thread safety, policy, TTL) without breaking the O(1) guarantee, or only the single-threaded happy path? Time management — did you nail the core structure quickly and leave room for the follow-ups, rather than over-polishing the get method? Reading this guide teaches the design; it does not teach you to defend it while someone says "now make it thread-safe" mid-sentence.

Step 1: Clarify the requirement that forces the design

The LRU cache has fewer requirements than most LLD prompts, but the few it has are sharp — state them out loud, because they are what justify every later choice.

• A fixed capacity of entries.
• get(key) returns the value if present, else a miss — and marks that entry most recently used.
• put(key, value) inserts or updates — and if the cache is at capacity, evicts the least recently used entry first.
• Both get and put must run in O(1) average time. This is the requirement that drives everything.

Non-functional constraints worth surfacing (this is where senior candidates separate themselves):

• Thread safety — will multiple threads call the cache concurrently? Almost always "yes, assume so" once you ask, and it changes the design.
• Extensibility — might the eviction policy change (LRU today, LFU later), or entries need a TTL? Designing as if they might keeps the structure clean.

State your assumptions explicitly: "I'll assume a fixed integer capacity, O(1) required for both operations, and I'll design the eviction behind an interface so we can swap LRU for LFU — tell me if entries also need a time-to-live." That one sentence shows you prioritise, which is itself part of the score.

Step 2: Choose the data structures (and justify them)

Here is where the LLD round diverges from the LeetCode solve: you do not just state the hash-map-plus-list answer, you justify it against the alternatives, because the justification is the signal.

The requirement is O(1) for two different jobs: look up a value by key (random access) and track recency order so you can find and evict the least-recently-used entry and move any entry to "most recent." No single structure does both:

• A hash map gives O(1) lookup by key, but has no order.
• An ordered list / array can express recency, but finding and removing an arbitrary element is O(n).
• A queue tracks insertion order, but you cannot move an already-queued element to the front in O(1).

The answer is to combine two structures: a hash map from key to a node, plus a doubly linked list of those nodes ordered most-recently-used at the head to least-recently-used at the tail.

• get: the map finds the node in O(1); you then unlink that node and move it to the head (most recent) in O(1).
• put: insert a new node at the head and record it in the map; if over capacity, evict the node at the tail (least recent) and delete its key from the map — all O(1).

Two justifications an interviewer specifically listens for: why a doubly linked list (you need to unlink a node in O(1), which requires its prev pointer — a singly linked list would be O(n) to find the predecessor), and why the map stores the node itself (so you jump straight to it, instead of scanning the list). Mention that Java's LinkedHashMap (or Python's OrderedDict) packages exactly this, but that the point of the round is to design it from parts.

Step 3: Sketch the class

Now write the class — as a design you can talk through, leading with the node and the pointer moves, because that is where the O(1) guarantee lives.

class Node {
    int key, value;
    Node prev, next;
    Node(int k, int v) { key = k; value = v; }
}

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    // sentinel head/tail avoid null checks at the ends
    private final Node head = new Node(0, 0);
    private final Node tail = new Node(0, 0);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;          // miss
        moveToHead(n);                      // mark most-recently-used
        return n.value;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) { n.value = value; moveToHead(n); return; }
        if (map.size() == capacity) {       // at capacity -> evict LRU
            Node lru = tail.prev;
            removeNode(lru);
            map.remove(lru.key);
        }
        Node fresh = new Node(key, value);
        map.put(key, fresh);
        addToHead(fresh);
    }

    private void addToHead(Node n) {        // all pointer moves are O(1)
        n.prev = head; n.next = head.next;
        head.next.prev = n; head.next = n;
    }
    private void removeNode(Node n) {
        n.prev.next = n.next; n.next.prev = n.prev;
    }
    private void moveToHead(Node n) { removeNode(n); addToHead(n); }
}

Talk through the choices as you write them: the sentinel head and tail nodes mean addToHead and removeNode never special-case an empty list or the ends; every mutation is a fixed number of pointer assignments, so both public methods are genuinely O(1); and the map holds the Node so you never walk the list to find an entry. Narrate the pointer moves out loud — that is what an interviewer is grading, far more than whether the code compiles first try.

Step 4: The design decisions interviewers probe

The core structure is the easy half. The follow-ups live in the extensions, and having an answer ready for each is what the round rewards.

• Thread safety — this is the follow-up from the opening scenario. Both get and put mutate the shared list (even a read reorders it), so concurrent calls race on the prev/next pointers and can corrupt the list or lose an entry. The options to name, with trade-offs: wrap the critical section in a single lock / synchronized (correct and simple, but serialises every call — a bottleneck under load); use finer-grained locking or a ConcurrentHashMap for the map combined with careful locking of the list (more throughput, much harder to get right); or, in languages with one, use a ready concurrent cache. The insight to state: because get reorders the list, it is a writer, not a reader — so a read-write lock does not help here the way people expect.
• Pluggable eviction policy — the interviewer may ask for LFU (least frequently used) instead of LRU, or a mix. Put eviction behind an EvictionPolicy strategy so the cache delegates "who gets evicted" and "record an access" to a policy object; LRU is the doubly-linked-list implementation, LFU adds frequency counts (often a map of frequency to a list of nodes). The cache's get/put stay the same; only the policy changes. This is the open/closed principle in action.
• TTL (time-to-live) — if entries expire by age, store an expiry timestamp on the node and treat an expired entry as a miss on get (lazily evicting it), optionally with a background sweep for proactive cleanup. Note that TTL is orthogonal to LRU — you can have both — and that lazy expiry keeps get O(1).
• Edge cases — a capacity of zero, updating an existing key (move to head, do not evict), and the generic key/value types in a real implementation. You will not design all of them; naming them shows you see past the single-threaded int version.

Low-Level Design
LLD · LRU Cache
Design the LRU cache and defend the thread-safety plan out loud

Practise on Zynter →

Design patterns that fit the LRU cache

You do not need to force patterns in, but naming the ones that fit — and why — is a strong signal in an OOD round.

• Strategy — the eviction policy. An EvictionPolicy interface lets LRU, LFU and FIFO be swapped without touching the cache's get/put. The cleanest, most reused design decision in this problem once the interviewer asks for a second policy.
• Decorator — a clean way to add cross-cutting features like TTL, metrics or logging by wrapping the base cache, so the core stays a pure LRU implementation.
• Singleton — an application-wide cache is often a single shared instance; note the trade-off that it must be thread-safe and kept injectable for tests.
• Generics over inheritance — more a principle than a pattern: a real cache is Cache<K, V>, not hard-coded to int; mentioning it signals you are designing a reusable component, not just passing a test.

Say it crisply: Strategy for the eviction policy is the one that pays off most the moment they ask for LFU; Decorator keeps TTL and metrics out of the core; and I'd make it generic and thread-safe if it is a shared instance. Naming the trade-off, not just the pattern, is what reads as experience.

Low-Level Design
LLD · Core skills
Apply Strategy and thread-safe design out loud

Practise on Zynter →

How to talk about a low-level design in an interview

The probes from every section rhyme. Master these five and you can defend any LLD, not just the LRU cache.

• "Which data structures, and why these?" → A hash map for O(1) lookup plus a doubly linked list for O(1) recency reordering — because no single structure gives both random access and cheap reordering, and the map stores the node so I never scan the list. (communication)
• "Why a doubly linked list, not singly?" → I need to unlink an arbitrary node in O(1), which requires its predecessor pointer; a singly linked list would be O(n) to find the node before it. (problem solving)
• "Two threads call get and put at once — what breaks?" → Both mutate the shared list, so they race on prev/next pointers; I guard the critical section with a lock, noting that get is a writer too, so a read-write lock does not help, and finer-grained locking trades complexity for throughput. (technical execution)
• "Switch the policy to LFU — what changes?" → Only the eviction policy behind an EvictionPolicy strategy; the cache's get/put are unchanged — open to extension, closed to modification. (technical execution)
• "Entries should expire after a while — how?" → A TTL timestamp on each node, treated as a miss on get and lazily evicted, optionally with a background sweep; TTL is orthogonal to LRU and keeps get O(1). (time management)

Each maps to a debrief dimension. Reading them teaches the answers; it does not teach you to deliver them while someone says "now make it generic and thread-safe" — that only comes from saying them out loud.

How to prepare: a short plan

You do not need to memorise one reference solution. You need the design reasoning automatic, so the LRU cache becomes requirement → structures → class → extensions, not a trick you recall.

• Day 1: Drill the core — state the O(1) requirement, justify the hash-map-plus-doubly-linked-list against the alternatives, and write the class with sentinel nodes until the pointer moves are automatic.
• Day 2: Drill the extensions — thread safety (and why get is a writer), the eviction policy behind a Strategy, and TTL. These are where the follow-ups live.
• Day 3: Do it out loud, timed, with someone adding "make it thread-safe," "now LFU," "now with a TTL" mid-answer, then move to a second LLD (parking lot, vending machine) to prove the process transfers.

This explainer feeds the broader low-level design interview track — the LRU cache is a classic that doubles as a data-structure and a design question, and the "requirement → structures → class → extensions" process transfers directly to the rest.

Frequently asked questions

What is an LRU cache low-level design interview actually testing?

In an LLD round it is testing design reasoning, not whether you can recall a LeetCode trick. The interviewer wants to see how you choose data structures and justify them against alternatives, how you keep both get and put genuinely O(1), and — crucially — how you handle the extensions they add: thread safety, a different eviction policy, a time-to-live. Stating "a hash map and a doubly linked list" is the beginning of the conversation; the signal is in explaining why those structures, narrating the pointer moves, and designing the class so that a new policy or a concurrency requirement does not force a rewrite. Your API design, your justification, and your handling of the follow-ups are what get scored.

Why does an LRU cache use a hash map and a doubly linked list?

Because the O(1) requirement applies to two different jobs and no single structure does both. You need O(1) lookup of a value by its key, which a hash map gives you, and you need to track recency order so you can move any entry to "most recently used" and evict the "least recently used" in O(1), which a doubly linked list gives you. The hash map stores a pointer to the node in the list, so a get jumps straight to the node and then unlinks and re-inserts it at the head in constant time, and a put at capacity removes the tail node and deletes its key from the map. A plain list or array would be O(n) to find and move an arbitrary element, and a queue cannot promote an existing element to the front cheaply, which is why the two structures are combined.

Why a doubly linked list rather than a singly linked one?

Because an LRU cache needs to remove an arbitrary node from the middle of the list in O(1) — specifically the node a get just found via the hash map, so it can be moved to the head. Removing a node requires linking its predecessor to its successor, and in a singly linked list you do not have a pointer to the predecessor, so finding it is O(n), which breaks the constant-time guarantee. A doubly linked list gives every node a prev pointer as well as a next, so unlinking it is a fixed number of pointer assignments. Using sentinel head and tail nodes on top of that removes the special cases for an empty list or the ends, keeping the pointer logic simple and uniform.

How do you make an LRU cache thread-safe?

The key realisation is that both operations mutate shared state: put obviously does, but get also reorders the linked list to mark the entry most recently used, so it is effectively a writer too. That means concurrent calls race on the list's prev and next pointers and can corrupt it or lose entries, and a read-write lock does not help the way people expect because there are no pure readers. The simplest correct answer is to guard the critical section with a single lock or synchronized block, accepting that it serialises calls and can become a bottleneck under heavy load. For higher throughput you can use finer-grained locking or a concurrent map for the lookups combined with careful locking of the list, but that is significantly harder to get right, so you should name the trade-off explicitly rather than claim it is free.

How would you add a different eviction policy or a TTL?

For a different eviction policy, put eviction behind an EvictionPolicy strategy interface so the cache delegates "which entry to evict" and "record this access" to a policy object. LRU is then one implementation backed by the doubly linked list, and LFU is another that tracks access frequencies (commonly a map from frequency to a list of nodes), with the cache's get and put unchanged — an application of the open/closed principle. For a TTL, store an expiry timestamp on each node and treat any entry past its expiry as a miss on get, evicting it lazily, optionally with a background sweep to reclaim expired entries proactively. TTL is orthogonal to the eviction policy, so you can combine them, and lazy expiry keeps get O(1).

How do I practise a low-level design interview out loud?

Reading an LRU cache solution is not the same as defending your design while an interviewer asks you to make it thread-safe or swap in LFU. On Zynter, the LLD track runs live voice rounds modelled on how real low-level design loops run — you write your class in the editor and a voice interviewer follows up one question at a time ("why a doubly linked list?", "two threads hit it at once — what breaks?", "now switch the policy to LFU"), then gives you a debrief on problem solving, communication, technical execution and time management. The score is a practice signal, not a hiring decision.

Practise it on Zynter

You can recite "hash map and doubly linked list." The round is won on defending the thread-safety plan out loud.

Pick the LRU Cache low-level design round, write your class in the editor, and defend it out loud to a voice interviewer that keeps asking "why a doubly linked list?" and "two threads just hit this cache at once — where's the race, and how do you fix it without a global bottleneck?" — then read the debrief. Zynter.ai is on-demand mock interviews modelled on real company loops, with 150+ rounds across 20 companies including the low-level design track (Sep 2026).

Practise the LRU Cache LLD round →
Browse all interview tracks