The Question

LRU Cache Design

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: - LRUCache(int capacity): Initialize the LRU cache with positive size capacity. - int get(int key): Return the value of the key if the key exists, otherwise return -1. - void put(int key, int value): Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in $O(1)$ average time complexity.

Java

Doubly Linked List

Hash Map

Questions & Insights

Clarifying Questions

What are the constraints on capacity? Will the capacity always be a positive integer, or do we need to handle zero/negative cases?

Are there specific requirements for time complexity? Standard LRU implementations usually require

O(1)

for both get and put.

Should the cache be thread-safe? Usually, in a coding interview, a single-threaded version is expected first, but we can discuss ReentrantLock or synchronized blocks later.

What are the types for keys and values? I will assume Integer for both to keep the implementation focused on the data structure logic, though generics could be used.

Assumptions:

Capacity is a positive integer.

Both get and put operations must perform in

O(1)

average time.

The cache does not need to be thread-safe for the initial implementation.

Thinking Process

To achieve

O(1)

lookup, a Hash Map is essential. However, a standard map does not maintain order based on access recency.

To achieve

O(1)

insertion and deletion at both ends (tracking the most and least recently used items), a Doubly Linked List is the ideal companion structure.

I will use Dummy Head and Tail nodes in the doubly linked list to eliminate edge cases related to null pointers when adding or removing the first/last elements.

When get(key) is called: If the key exists, locate the node via the map, move it to the "Most Recently Used" (MRU) position, and return the value.

When put(key, value) is called: If the key exists, update the value and move the node to MRU. If it's a new key, check capacity; if the cache is full, remove the "Least Recently Used" (LRU) node (the one near the tail/head) from both the map and the list, then insert the new node.

Implementation Breakdown

Problem Set

Functional Requirements:

LRUCache(int capacity): Initialize the cache with a positive size.

int get(int key): Return value of key if exists, else -1.

void put(int key, int value): Update value if key exists, otherwise insert key-value pair. If capacity is exceeded, evict the least recently used item.

Constraints:

1 \le capacity \le 3000

0 \le key, value \le 10^4

At most

2 \times 10^5

calls to get and put.

Approach

Algorithm: LRU Eviction Policy logic.

Data Structure: HashMap<Integer, Node> + Custom Doubly Linked List.

Complexity:

Time:

O(1)

for both get and put.

Space:

O(capacity)

to store nodes and map entries.

Implementation

Wrap Up

Advanced Topics

Thread Safety: To make this thread-safe, one could wrap the operations in a ReentrantReadWriteLock (though put needs a write lock, and get also needs a write lock because it modifies the list order). Alternatively, use ConcurrentHashMap combined with synchronized blocks on the linked list nodes.

Java's Built-in Solution: In a real-world scenario, one might extend java.util.LinkedHashMap and override the removeEldestEntry method, which provides a concise LRU implementation.

LFU vs LRU: Discussing the trade-offs between Least Recently Used (temporal locality) and Least Frequently Used (frequency-based) can demonstrate deeper knowledge of caching strategies.

Distributed Cache: If the cache size exceeds a single machine's memory, we would transition to a distributed cache (like Redis) using consistent hashing to determine which node stores which key.