The Question
Coding

Design an LRU Cache

Design and implement a data structure for a Least Recently Used (LRU) Cache. It should support 'get' and 'put' operations in O(1) time complexity. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.
Java
HashMap
Doubly Linked List
LRU Cache
Questions & Insights

Clarifying Questions

What are the constraints on capacity? Can the capacity be zero or negative, and what is the maximum expected number of elements?
What should the behavior be for `get` operations on non-existent keys? (Standard is returning -1 or null).
Are the keys and values restricted to integers, or should the solution be generic?
Is thread safety required for this implementation?

Thinking Process

To achieve O(1) lookup, a Hash Map is essential to map keys to their corresponding values or nodes.
To achieve O(1) updates for the "Least Recently Used" ordering, a Doubly Linked List (DLL) is the ideal structure. It allows us to remove a node from the middle and move it to the "head" (most recent) in constant time, provided we have a reference to the node.
Each time a key is accessed (get) or updated (put), we move the corresponding node to the head of the DLL.
When the cache exceeds its capacity during a put operation, we remove the node at the tail of the DLL (the least recently used item) and delete its entry from the Hash Map.
Implementation Breakdown

Problem Set

Functional Requirements:
LRUCache(int capacity): Initialize the cache with a fixed size.
int get(int key): Return the value if the key exists, otherwise -1. Move the key to the "most recently used" position.
void put(int key, int value): Update the value if the key exists or insert the key-value pair. If capacity is reached, evict the least recently used item.
Constraints:
Time Complexity: O(1) for both get and put.
Space Complexity: O(capacity).

Approach

Algorithm: LRU Eviction Policy logic.
Data Structure: HashMap<Integer, Node> + Custom Doubly Linked List.
Complexity:
Time: O(1)
Space: O(N) where N is the capacity.

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: In Java, one could extend LinkedHashMap and override removeEldestEntry. While concise, a custom DLL (as shown above) is often preferred in interviews to demonstrate low-level pointer manipulation and data structure design.
Concurrency: To make this thread-safe, one could wrap operations in synchronized blocks or use ReentrantReadWriteLock. However, a ReadWriteLock is tricky here because get operations modify the DLL (a write operation), making every call essentially a write.
Distributed Adaptation: In a distributed system (like Redis), LRU is often approximated using sampling rather than a strict DLL to save memory and reduce lock contention across multiple shards.