The Question
Coding

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. Constraints: - $1 \le capacity \le 3000$ - $0 \le key \le 10^4$ - $0 \le value \le 10^5$ - At most $2 \cdot 10^5$ calls will be made to get and put. - The functions get and put must each run in $O(1)$ average time complexity.
Java
HashMap
Doubly Linked List
Questions & Insights

Clarifying Questions

What are the capacity constraints? Is it guaranteed that the capacity will be at least 1?
What should the get operation return if the key is not present (e.g., -1 or throw an exception)?
Are the keys and values restricted to certain types (e.g., integers), or should the implementation be generic?
Is thread safety a requirement for this implementation?
Assumptions:
The capacity will be a positive integer.
get(key) returns -1 if the key does not exist.
Keys and values are integers.
Operations must run in O(1) average time complexity.
Thread safety is not required for the base implementation but will be considered in advanced topics.

Thinking Process

To achieve O(1) lookup, a HashMap is essential to map keys to their corresponding values or node locations.
To achieve O(1) updates for the "Least Recently Used" property, we need a data structure that allows fast removals and insertions at both ends; a Doubly Linked List (DLL) is ideal for this.
When a key is accessed (get) or updated (put), its corresponding node must be moved to the "most recently used" position (the head of the DLL).
When the cache exceeds its capacity during a put operation, the "least recently used" node (the tail of the DLL) must be evicted from both the DLL and the HashMap.
Using dummy head and tail nodes in the DLL simplifies the logic by eliminating null checks during node insertions and deletions.
Implementation Breakdown

Problem Set

Functional Requirements:
LRUCache(int capacity): Initializes the cache with a positive size.
int get(int key): Returns the value of the key if it exists, otherwise -1. Updates the key's status to "most recently used".
void put(int key, int value): Updates the value if the key exists, or inserts the key-value pair. If capacity is reached, evicts the least recently used item.
Constraints:
Time Complexity: O(1) for both get and put.
Space Complexity: O(\text{capacity}) to store keys and nodes.

Approach

Algorithm: Hash Map with Doubly Linked List.
Data Structure: java.util.HashMap and a custom Doubly Linked List.
Complexity: Time O(1), Space O(\text{capacity}).

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: In Java, one could extend LinkedHashMap and override removeEldestEntry(Map.Entry eldest). This is much cleaner (readability) but a manual implementation is often preferred in interviews to demonstrate low-level pointer manipulation.
Concurrency: To make this thread-safe, one could use ReentrantReadWriteLock. get operations could acquire a read lock (though moving nodes still requires a write lock), or simply wrap methods in synchronized blocks for a standard thread-safe cache.
Scale Out: In a distributed system, a single-machine LRU cache is insufficient. We would use a distributed caching layer like Redis (which supports LRU eviction policies) or a consistent hashing mechanism to shard keys across multiple LRU cache instances.
Generic Implementation: The current version uses int. In a production environment, this should be implemented using Generics LRUCache<K, V> to support any object types.