The Question
Coding

LRU Cache Implementation

Design and implement a system that functions as a Least Recently Used (LRU) cache. The system should support retrieving values by key and inserting or updating key-value pairs. If the cache reaches its predefined capacity, it must automatically discard the item that has not been accessed for the longest period. Ensure that both retrieval and insertion operations are optimized to perform in constant time on average.
Java
LRU Cache
Questions & Insights

Clarifying Questions

What are the constraints on the capacity? (Assumption: Capacity will be a positive integer provided at initialization).
What should the `get` operation return if the key is not present? (Assumption: Return -1 for cache misses).
Is the cache expected to be thread-safe for concurrent access? (Assumption: A standard single-threaded implementation is expected; thread safety can be achieved via external synchronization or ConcurrentHashMap).
What are the data types for keys and values? (Assumption: Both keys and values are integers).

Thinking Process

To achieve O(1) for both get and put operations, we need a combination of two data structures: a HashMap for constant-time lookups and a Doubly Linked List to maintain the usage order.
The Doubly Linked List will store nodes where the head represents the most recently used (MRU) item and the tail represents the least recently used (LRU) item.
When an item is accessed via get or updated via put, we move its corresponding node to the head of the list.
When the cache exceeds its capacity during a put operation, we remove the node at the tail of the list and delete its entry from the HashMap to make room for the new element.
Implementation Breakdown

Problem Set

Functional Requirements:
LRUCache(int capacity): Initialize the cache with a positive size.
int get(int key): Return the value of the key if it exists, otherwise return -1.
void put(int key, int value): Update the value if the key exists or insert the key. If capacity is reached, evict the least recently used item.
Constraints:
Both get and put must run in O(1) average time complexity.
Space complexity should be O(C), where C is the capacity.

Approach

Algorithm: Doubly Linked List + Hash Map (LRU Policy).
Data Structure: java.util.HashMap for mapping keys to nodes; custom Node class for the doubly linked list.
Complexity:
Time: O(1) for both get and put.
Space: O(\text{capacity}) to store the nodes and map entries.

Implementation