An LRU cache stores key/value pairs up to a fixed capacity. Every time a key is accessed it is marked as the most recently used. When the cache is full and a new key needs to be inserted, the least recently used key is evicted to make room. The result is a cache that automatically keeps the hottest entries and discards the coldest.
Implemented naively, the access tracking is O(n) and the cache becomes slower than the storage it is supposed to be accelerating. The standard efficient implementation pairs a hash map (for O(1) lookups by key) with a doubly-linked list (for O(1) reordering of access recency). Every operation on the cache — get, put, evict — runs in constant time once those two structures are wired together correctly.
The LRU Cache shows up so often in technical interviews because it sits at exactly the right level: complex enough to require thinking about two data structures cooperating, simple enough to write in a 45-minute slot. The five-level coding-interview prep post in this topic ends with a complete LRU implementation precisely for that reason. In production code, the same structure appears everywhere — HTTP response caches, database query caches, image decoders, the file system page cache underneath your operating system.