Mastering LRU Cache: Theory, C++ Implementation, and Interview Strategies

In the highly competitive tech job market, major companies such as Baidu and ByteDance set high interview standards, and the LRU cache algorithm is a frequent interview topic, reflecting its importance.

First, it is a classic cache eviction strategy widely used in operating systems, databases, browsers, and other scenarios; mastering it demonstrates a candidate’s grasp of data structures, algorithm design, and time‑complexity analysis.

Second, it tests problem‑solving ability and programming mindset, as engineers often face performance optimization and resource‑management challenges that involve efficiently maintaining access order and evicting under limited resources.

Part1 LRU Algorithm Core Principles

1.1 LRU Overview

LRU (Least Recently Used) is a cache eviction policy. When the cache is full and new data must be stored, the algorithm evicts the data that has not been accessed for the longest time, based on the assumption that recently unused data is less likely to be needed soon.

An analogy is a bookshelf with limited space: you remove books you haven’t read for a long time and keep the ones you frequently consult, mirroring how LRU decides which items to discard.

1.2 Working Mechanism Analysis

The mechanism revolves around two operations: data access and cache eviction. Accessed data is moved to the front (or tail) of a data structure that records usage order, while the least‑recently used items drift to the opposite end.

When the cache is full and a new item arrives, the algorithm evicts the item at the tail (the least recently used). For example, with capacity 3 and accesses A, B, C, the cache holds [A, B, C]. Accessing A moves it to the most recent position, yielding [B, C, A]. Inserting D then evicts B, resulting in [C, A, D].

Web browsers use LRU to manage cached resources: frequently visited pages stay cached, while rarely visited pages are evicted to make room for new content.

Part2 Implement LRU Cache in C++

2.1 Required Data Structures

The implementation relies on a doubly linked list and a hash table. The list maintains the order of accesses; each node represents a cached entry and supports O(1) insertion and deletion. The head denotes the least recently used item, the tail the most recent.

The hash table maps keys to list iterators, enabling O(1) lookup of a node’s position in the list.

Combining both structures yields an efficient LRU cache where all operations run in constant time.

2.2 C++ Code Line‑by‑Line Explanation

Below is the complete C++ implementation of an LRU cache:

#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

class LRUCache {
private:
    struct Node {
        int key;
        int value;
        Node(int k, int v) : key(k), value(v) {}
    };
    list<Node> cacheList;               // doubly linked list
    unordered_map<int, list<Node>::iterator> cacheMap; // hash table
    int capacity;
public:
    LRUCache(int cap) : capacity(cap) {}
    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) {
            return -1;
        }
        moveToTail(cacheMap[key]);
        return cacheMap[key]->value;
    }
    void put(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            cacheMap[key]->value = value;
            moveToTail(cacheMap[key]);
            return;
        }
        if (cacheList.size() == capacity) {
            cacheMap.erase(cacheList.front().key);
            cacheList.pop_front();
        }
        cacheList.emplace_back(key, value);
        cacheMap[key] = --cacheList.end();
    }
private:
    void moveToTail(list<Node>::iterator it) {
        Node node = *it;
        cacheList.erase(it);
        cacheList.emplace_back(node);
        cacheMap[node.key] = --cacheList.end();
    }
};

Explanation of each function:

Constructor : Initializes the cache with a given capacity and prepares the list and hash map.

get(int key) : Returns the value for a key if present; otherwise returns -1. Moves the accessed node to the tail to mark it as most recent.

put(int key, int value) : Inserts a new key‑value pair or updates an existing one. If the cache is full, evicts the head node (least recent) before insertion.

moveToTail(iterator it) : Removes a node from its current position and re‑adds it at the tail, updating the hash map accordingly.

2.3 Complexity Analysis

Both get and put run in O(1) time thanks to the hash table for fast lookup and the doubly linked list for constant‑time insertion and deletion.

The space complexity is O(capacity) because the list and hash map together store at most capacity entries.

Part3 Practical Exercises and Case Studies

3.1 Test Code Demonstration

The following test program validates the implementation:

int main() {
    LRUCache cache(2);
    cache.put(1, 100);
    cache.put(2, 200);
    cout << "Get key 1: " << cache.get(1) << endl; // 100
    cout << "Get key 3: " << cache.get(3) << endl; // -1
    cache.put(3, 300); // evicts key 2
    cout << "Get key 2: " << cache.get(2) << endl; // -1
    cout << "Get key 3: " << cache.get(3) << endl; // 300
    cache.put(1, 400); // updates key 1
    cout << "Get key 1: " << cache.get(1) << endl; // 400
    return 0;
}

The output confirms that when the cache reaches capacity, the least recently used entry is evicted, and updates correctly refresh the usage order.

3.2 Real‑World Application Scenarios

Operating‑system memory management: page replacement algorithms use LRU‑like policies to decide which memory pages to swap out.

Browser cache optimization: browsers keep recently visited resources cached and evict older ones using LRU, improving load times.

Database caching: systems such as MySQL InnoDB employ LRU to manage buffer pools, reducing disk I/O.

Part4 Interview Techniques and Extensions

4.1 Interview Strategies

When faced with an LRU problem, first articulate the overall approach—using a doubly linked list combined with a hash map—before writing code. Emphasize code readability, add comments, and be prepared to discuss why both get and put achieve O(1) time and the O(capacity) space usage.

4.2 Algorithm Extensions

In some workloads, LRU may not be optimal. Variants such as LFU (Least Frequently Used) consider access frequency, while LRU‑K records the last K accesses to make more informed eviction decisions. Choosing the right policy depends on the specific access patterns of the application.