Implement an LRU cache with a fixed capacity.

Question

Implement an LRU cache with a fixed capacity.

Brief Answer

An LRU (Least Recently Used) cache is a fixed-capacity cache that intelligently evicts the least recently used item when it needs to make space for new entries. It’s a common solution for optimizing performance by storing frequently accessed data, particularly when data access exhibits temporal locality.

Core Components:

  • Hash Map (e.g., Map, Dictionary): This stores key -> node reference pairs. It’s crucial for achieving O(1) average time complexity for checking if a key exists and retrieving its associated data.
  • Doubly Linked List: This maintains the access order of items. Each node in the list represents a cache entry (containing key and value). The head of the list always points to the Most Recently Used (MRU) item, while the tail points to the Least Recently Used (LRU) item. This structure enables O(1) operations for moving nodes to the head (after access) and for removing the tail node (during eviction).

How Operations Work (O(1) Average Time Complexity):

  • get(key):
    1. Check if the key exists in the Hash Map.
    2. If found: Retrieve the corresponding node. Crucially, move this node to the head of the Doubly Linked List (marking it as MRU) and return its value.
    3. If not found: Return -1 (or null).
  • put(key, value):
    1. If the key already exists in the Hash Map: Update the node’s value and move the node to the head of the Doubly Linked List.
    2. If the key is new:
      • First, check if the cache is at its fixed capacity. If it is full, remove the tail node (the LRU item) from both the Doubly Linked List and the Hash Map.
      • Then, create a new node for the key, value pair, add this new node to the head of the Doubly Linked List, and store the key -> new node mapping in the Hash Map.

Key Strengths & Interview Considerations:

  • Optimal Performance: Both get and put operations typically achieve O(1) average time complexity, making LRU caches highly efficient for high-throughput systems.
  • Concurrency: In multi-threaded environments, proper synchronization (e.g., using locks or leveraging language-specific concurrent collections like ConcurrentHashMap) is essential to ensure thread safety and data consistency.
  • Trade-offs: While generally effective, LRU might not be optimal for all access patterns (e.g., purely random access). For certain scenarios (like caching extremely expensive but rarely used items), other strategies like LFU (Least Frequently Used) or more advanced adaptive algorithms might be considered.

Super Brief Answer

An LRU (Least Recently Used) cache is a fixed-capacity cache that evicts the least recently used item when it’s full. It’s implemented using two core data structures for O(1) average time complexity on operations:

  • Hash Map: Stores key -> node reference for fast lookups.
  • Doubly Linked List: Maintains the usage order. The head is MRU, the tail is LRU.

On get or put, the accessed/new item’s node is moved to the list’s head (MRU). If put causes overflow, the node at the list’s tail (LRU) is removed from both the list and the map.

Detailed Answer

An LRU (Least Recently Used) cache efficiently stores and manages data by combining a hash table and a doubly linked list. When the cache reaches its fixed capacity, it automatically evicts the least recently used item to make space for new entries.

Implementing an LRU cache with a fixed capacity is a fundamental concept in computer science and a common interview question, particularly for roles involving system design or performance optimization. An LRU cache is a type of cache that intelligently discards the least recently used items first when it reaches its predefined capacity. This strategy is highly effective for managing memory and improving performance in applications where data access exhibits temporal locality (i.e., recently accessed items are likely to be accessed again soon).

The core of an LRU cache implementation relies on two primary data structures:

  • A hash table (or hash map) for quick lookups of cached items by key.
  • A doubly linked list to track the usage order of items, allowing for efficient identification and removal of the least recently used entry.

Core Components of an LRU Cache

1. Hash Table (Map) for O(1) Access

The hash table (often implemented as a Map or Dictionary in modern programming languages) is crucial for providing fast retrieval of cached data. It stores key-value pairs, where the value is typically a reference to a node in the doubly linked list. Each key (e.g., a product ID, a user session token, or a file path) is hashed, and this hash value directly points to the location of the cached data. This design enables retrieving items in near-constant time, O(1) on average, regardless of the cache’s current size.

2. Doubly Linked List for Usage Order

The doubly linked list maintains the access order of items in the cache. Each node in the list represents a cache entry, containing the key and value of the cached item. The head of the list always points to the most recently used item, while the tail points to the least recently used item. This structure is chosen specifically because it allows for:

  • O(1) Time to Move to Head: When an item is accessed (either via get or put), its corresponding node is efficiently moved to the head of the list, marking it as the most recently used.
  • O(1) Time to Remove Tail: When the cache needs to evict an item due to capacity limits, the least recently used item (at the tail of the list) can be removed in constant time. A singly linked list would require O(n) time to remove the tail because it would necessitate traversing the entire list to find the node preceding the tail.

3. Fixed Capacity Management

An LRU cache is initialized with a fixed capacity, meaning it can only hold a maximum number of items. When a new item is to be added, and the cache is already full, the eviction process begins:

  1. The cache identifies the least recently used item, which is always located at the tail of the doubly linked list.
  2. This LRU node is removed from both the doubly linked list and the hash table.
  3. This action effectively evicts the LRU item, freeing up space for the new entry.

The new item is then added to the cache, specifically by creating a new node and placing it at the head of the doubly linked list and adding its key-node pair to the hash table.

4. The LRU Algorithm Explained

The LRU algorithm’s logic is elegant and efficient:

  • On a get operation: If the requested key exists in the cache, retrieve its value. Crucially, then move its corresponding node to the head of the doubly linked list to signify it’s now the most recently used.
  • On a put operation:
    • If the key already exists: Update the node’s value and move the node to the head of the list.
    • If the key is new:
      1. Check if the cache is at its fixed capacity.
      2. If full, evict the LRU item (the node at the tail of the list) by removing it from both the list and the hash table.
      3. Finally, add the new item (as a new node) to the head of the doubly linked list and its key-node pair to the hash table.

This ensures that the most recently used items always reside near the head of the list, making them resistant to eviction, while less frequently accessed items migrate towards the tail, becoming candidates for removal.

Advanced Considerations & Interview Insights

1. Time Complexity (O(1) Average)

Both the get and put operations in an LRU cache achieve an impressive O(1) average time complexity. This optimal performance is a direct result of the chosen data structures:

  • The hash table provides constant-time access for checking a key’s presence and retrieving its associated node.
  • The doubly linked list allows for constant-time addition, removal, and reordering of nodes (specifically, moving to the head or removing from the tail).

This O(1) performance is critical in high-performance systems. For example, in a real-time analytics dashboard, using an LRU cache to store frequently accessed data can dramatically improve response times by avoiding repeated database queries, which often become a significant bottleneck.

2. LRU vs. Other Eviction Strategies

While LRU is a robust and widely applicable caching strategy, especially when temporal locality is present (i.e., recently accessed items are likely to be accessed again soon), it’s not always the optimal choice. Here’s a brief comparison:

  • Advantages of LRU:
    • Generally effective for workloads exhibiting temporal locality (e.g., caching web pages, user session data, or recent posts in a social media feed).
    • Outperforms simpler strategies like FIFO (First-In, First-Out) by preventing frequently accessed items from being evicted simply because they were added earlier.
  • When LRU might not be ideal:
    • If data access patterns are random or do not show strong temporal locality, LRU’s effectiveness diminishes.
    • For scenarios where some items are extremely expensive to generate but rarely used, LRU might evict them prematurely. In such cases, LFU (Least Frequently Used) might be a better alternative, as it prioritizes keeping items that have been accessed the most times, regardless of recentness. Other strategies like ARC (Adaptive Replacement Cache) or LIRS (Low Inter-reference Recency Set) offer more sophisticated solutions for mixed workloads.

3. Handling Concurrency in LRU Caches

In a multi-threaded environment, where multiple threads might simultaneously try to get or put items into the cache, concurrency becomes a vital consideration. Without proper synchronization, data consistency issues and race conditions can occur, leading to corrupted cache states or incorrect data.

Common approaches to ensure thread safety:

  • Locking: A straightforward method involves placing a global lock (e.g., a mutex or semaphore) around the entire get and put operations. While simple to implement, this can lead to significant contention and become a performance bottleneck in high-throughput systems, as only one thread can access the cache at any given time.
  • Concurrent Collections: A more efficient and scalable solution is to leverage built-in concurrent collections provided by programming languages or libraries. For instance, a ConcurrentDictionary in .NET or similar structures in Java (ConcurrentHashMap) or Python (using `threading.Lock` for the dictionary and linked list, or `collections.OrderedDict` with careful locking) offer thread-safe operations with optimized internal locking mechanisms (e.g., fine-grained locks or lock-free algorithms). This approach significantly reduces lock contention and increases overall throughput in high-concurrency scenarios.

Code Sample: LRUCache Implementation in JavaScript


class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // Key -> Node mapping for O(1) lookups
        this.list = new DoublyLinkedList(); // Doubly linked list to maintain usage order
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1; // Key not found in cache
        }

        const node = this.cache.get(key);
        this.list.moveToHead(node); // Move the accessed node to the head (most recently used)
        return node.value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            // Key already exists: update value and move to head
            const node = this.cache.get(key);
            node.value = value; 
            this.list.moveToHead(node); 
        } else {
            // New key: check capacity and add
            if (this.cache.size >= this.capacity) {
                // Cache is full, remove the least recently used item (tail of the list)
                const lruNode = this.list.removeTail();
                if (lruNode) { // Ensure a node was actually removed
                    this.cache.delete(lruNode.key);
                }
            }

            // Add new node to the head of the list and to the cache map
            const newNode = new Node(key, value);
            this.list.addToHead(newNode);
            this.cache.set(key, newNode);
        }
    }
}

// Node class for the Doubly Linked List
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

// Doubly Linked List class to manage usage order
class DoublyLinkedList {
    constructor() {
        // Dummy head and tail nodes simplify edge cases (empty list, adding/removing at ends)
        this.head = new Node(null, null);
        this.tail = new Node(null, null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    // Add a node right after the head (making it the MRU)
    addToHead(node) {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next.prev = node;
        this.head.next = node;
    }

    // Remove a node from its current position in the list
    removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        // Optional: clear node's references to aid garbage collection
        node.prev = null;
        node.next = null;
    }

    // Move an existing node to the head (after access)
    moveToHead(node) {
        this.removeNode(node);
        this.addToHead(node);
    }

    // Remove the node just before the tail (which is the LRU node)
    removeTail() {
        // If the list only contains dummy head and tail, it's empty
        if (this.tail.prev === this.head) {
            return null; 
        }
        const lruNode = this.tail.prev;
        this.removeNode(lruNode);
        return lruNode;
    }
}

// Example Usage:
const lru = new LRUCache(2);
lru.put(1, 1); // Cache: {1=1}
lru.put(2, 2); // Cache: {1=1, 2=2}
console.log(lru.get(1)); // returns 1. Cache state (order): {2=2, 1=1} (1 is now MRU)
lru.put(3, 3); // evicts key 2 (LRU), adds key 3. Cache state: {1=1, 3=3}
console.log(lru.get(2)); // returns -1 (not found)
lru.put(4, 4); // evicts key 1 (LRU), adds key 4. Cache state: {3=3, 4=4}
console.log(lru.get(1)); // returns -1 (not found)
console.log(lru.get(3)); // returns 3. Cache state (order): {4=4, 3=3} (3 is now MRU)
console.log(lru.get(4)); // returns 4. Cache state (order): {3=3, 4=4} (4 is now MRU)