How do you implement an LRU cache in O(1) time?

Use a hash map combined with a doubly linked list. The hash map provides O(1) key lookup. The doubly linked list maintains access order, with the most recently used element at the head and the least recently used at the tail. On get: look up the node in the hash map, move it to the head, return its value. On put: if the key exists, update the value and move to head. If the key is new and capacity is full, remove the tail node and its hash map entry, then insert the new node at the head and add to the hash map. Both operations are O(1).

Why is LRU cache such a common interview question?

LRU cache is an almost perfect interview question because it tests multiple skills simultaneously: data structure design (combining a hash map and doubly linked list), pointer manipulation (moving nodes in a linked list without corrupting it), edge case handling (capacity of 1, getting a non-existent key, putting when full), and system design awareness (knowing why caches exist and what eviction policies trade off). It is also directly practical: LRU is used in browser caches, database buffer pools, and distributed key-value stores.

What are the common variations of LRU cache interview questions?

Common variations include: LFU cache (evict the least frequently used, then break ties by least recently used), time-based cache with TTL expiration, thread-safe LRU cache requiring concurrent reads, distributed LRU cache design at system design level, and implementing LRU as a component inside a larger system (CDN cache, database page cache). LFU is significantly harder than LRU and appears in senior-level Google and Meta onsite rounds.

What are the most common implementation bugs in LRU cache?

The most common bugs are: (1) not moving a node to the head on get (updating value but forgetting to update order), (2) not removing the existing node before re-inserting it on a put with an existing key, (3) forgetting to delete the hash map entry when evicting the LRU node from the tail, (4) off-by-one in capacity check (evicting when size equals capacity, not exceeds it), and (5) using dummy head and tail sentinels incorrectly. Using dummy sentinel nodes eliminates most edge cases in the linked list manipulation.

How does LeakCode help with LRU cache prep?

LeakCode has 51,000+ real interview reports from companies including Google, Meta, Amazon, and Microsoft. You can filter LRU cache questions by company to see how often it appears versus related cache design problems, and whether your target company asks pure implementation or extends it into system design territory. This company-level view lets you calibrate your preparation depth.

LRU Cache Interview Questions: Complete Guide (2026)

How to implement an LRU cache correctly in O(1) time, which companies ask it most, common variants and bugs, and what LeakCode's 51,000+ real reports reveal about how it appears in practice.

Why LRU cache is an enduring interview staple

The LRU cache problem has appeared in technical interviews for over a decade and shows no sign of disappearing. It tests pointer manipulation, combined data structure design, and practical engineering intuition all within a single problem that typically takes 25-35 minutes. LeakCode's data shows it consistently appears in the top 20 most reported coding problems across FAANG companies.

What makes it durable as an interview question is its adjustable depth. At the coding level, it tests linked list implementation and hash map usage. At the system design level, it naturally extends to cache sizing, write policies, distributed invalidation, and cache coherence, making it a bridge between coding and system design rounds. LeakCode's reports show it appearing in both contexts at different company levels.

Candidates who prepare LRU cache but skip related variants (LFU cache, time-expiring cache, thread-safe cache) often get surprised in senior-level rounds. LeakCode's company-filtered data tells you which variants your specific target company has asked recently.

LRU cache problem categories

Classic LRU cache implementation

Implement a cache with O(1) get and O(1) put. Put evicts the least recently used item when at capacity. The canonical implementation uses a doubly linked list for O(1) node movement and a hash map for O(1) key lookup. Using dummy head and tail sentinel nodes eliminates empty-list edge cases. This exact problem is the most reported cache question in LeakCode's database.

LFU cache (least frequently used)

Evict the least frequently used item, breaking ties by least recently used among items with the same frequency. Requires tracking frequency of access per key and maintaining ordered groups by frequency. The standard O(1) implementation uses a hash map from key to (value, freq), a hash map from freq to ordered set of keys, and a min-freq variable. Appears in hard-difficulty rounds at Google and Meta.

Time-based key-value cache with TTL

Design a cache where values expire after a given time-to-live. On get, check if the key exists and if the current time is within its expiration window. Requires storing the timestamp alongside the value, and potentially a cleanup mechanism. Appears in system-aware coding rounds and as a design extension question at Stripe and Amazon.

Thread-safe and distributed cache design

System design extensions asking how to make an LRU cache thread-safe (read-write locks, concurrent hash maps, fine-grained locking) or how to distribute it across multiple nodes (consistent hashing, invalidation protocols, write-through vs write-back). These appear in system design rounds and senior onsite loops where the interviewer starts from the LRU implementation and extends to scale.

Cache as a component in larger problems

Problems where the cache is not the whole question but one component: a memoized recursive function, a two-level caching hierarchy, or a bounded cache inside a larger data pipeline. These test whether candidates can apply the LRU pattern composably rather than only in isolation. Appears in mid and senior Amazon and Google coding rounds.

How to implement LRU cache without bugs

The implementation has two logical parts: the node movement logic and the eviction logic. Separating them into helper functions (add_to_front, remove_node) makes each operation a one-liner composition and eliminates pointer manipulation errors.

1.Use dummy head and tail sentinels. Initialize head.next = tail and tail.prev = head. Every real node lives between them. This eliminates all null checks during node removal and insertion, making the code significantly cleaner.
2.Implement remove_node and add_to_front as helpers. remove_node disconnects a node from wherever it is. add_to_front inserts it right after the dummy head. move_to_front is just remove_node followed by add_to_front. Every cache operation composes these two primitives.
3.On put with existing key, update before moving. Update the node's value first, then call move_to_front. Do not remove and re-insert a new node for an existing key, as the hash map will then point to a dangling old reference.
4.Evict from tail.prev, not tail. The tail is the sentinel. The last real node is tail.prev. Remove that node and delete its key from the hash map before inserting the new node.

Companies that ask LRU cache questions

Browse real LRU cache interview questions from these companies on LeakCode:

Google Meta Amazon Microsoft Uber Stripe Netflix Airbnb

Search LRU Cache on LeakCode

LeakCode has 51,000+ real interview questions from 2,000+ companies. See how LRU cache and its variants appear in your target company's recent coding rounds.

Browse LRU Cache Questions

How LeakCode helps with LRU cache prep

LeakCode indexes real candidate-reported questions from 1Point3Acres, Blind, LeetCode Discuss, Glassdoor, and Reddit. You can filter by company to see how frequently LRU appears versus LFU and time-expiring cache variants, and whether your target company extends the implementation into a system design discussion. This tells you exactly how deep to prepare.