Requirements for the LRU Cache

Let's define exactly what our LRU Cache must do. Each requirement will directly drive a class, method, or design decision later.

1. Fixed Capacity: The cache is initialized with a maximum capacity n. It can hold at most n key-value pairs at any given time.

2. Get Operation — get(key): Retrieve the value associated with a key. If the key exists, return the value and mark it as most recently used. If the key does not exist, return -1 (or null/None).

3. Put Operation — put(key, value): Insert a new key-value pair or update the value of an existing key. In both cases, the key is marked as most recently used. If inserting a new key causes the cache to exceed its capacity, evict the least recently used key before inserting the new one.

4. LRU Eviction Policy: When the cache is full and a new key must be inserted, the key that has not been accessed (via get or put) for the longest time is removed. This is the "least recently used" key.

5. O(1) Time Complexity: Both get and put operations must execute in O(1) average time. This is the defining constraint — a cache that takes O(n) to read negates the performance benefit of caching.

6. Key Uniqueness: Each key in the cache is unique. Calling put(key, newValue) on an existing key updates its value in place (does not create a duplicate entry).

7. Generic Key-Value Types: The cache should support arbitrary key and value types (integers, strings, objects), not just one hardcoded type.

Beyond the core functionality, the design should consider:

1. Thread Safety (Extension): If multiple threads access the cache concurrently, operations must be synchronized to prevent data corruption. A get and a put happening simultaneously should not leave the cache in an inconsistent state. We'll address this in the Thread-Safe LRU Cache tutorial.

2. Extensibility — Eviction Policies: While we implement LRU, the design should make it feasible to swap in alternative eviction policies (LFU, FIFO, TTL-based) without rewriting the core cache structure.

3. Extensibility — TTL Support: It should be possible to add time-to-live expiration on top of the base LRU Cache — entries expire after a specified duration regardless of access. The Decorator Pattern makes this possible without modifying the base class.

4. Memory Efficiency: The internal data structures should not use significantly more memory than the stored key-value pairs themselves. Overhead per entry (node pointers, hash map slots) should be constant.

In Scope:

• Core LRU Cache with get(key) and put(key, value) — O(1) operations
• Internal data structure design (HashMap + Doubly Linked List)
• Class diagram modeling the cache's internal structure
• Thread-safe extension using synchronization primitives
• Design pattern analysis (Decorator for TTL)
• Edge case handling (capacity 1, duplicate keys, empty cache)

Out of Scope:

• Distributed caching (sharding, replication, consistency protocols) — that's System Design territory
• Persistent storage or disk-backed caching (Redis RDB/AOF) — infrastructure concern
• Cache warming, pre-loading strategies — operational concern
• Network protocol for cache access (Memcached protocol, Redis RESP) — not relevant to OOD
• Eviction policy benchmarking (LRU vs LFU hit rates) — algorithmic research, not design
• Serialization of keys and values — language-specific implementation detail

Requirement #5 is what makes this problem interesting from a design perspective. Let's understand why:

Without the O(1) constraint, many simpler implementations work:

• A sorted list ordered by access time → get is O(n), eviction is O(1)
• A min-heap keyed by access time → get is O(n) (searching the heap), eviction is O(log n)
• A simple array with timestamps → get is O(n), eviction is O(n)

None of these meet our requirement. A cache that scans all entries on every get becomes a bottleneck instead of an accelerator.

To achieve O(1) for both operations, we need to combine two data structures:

• HashMap — gives us O(1) key lookup
• Doubly Linked List — gives us O(1) insertion, deletion, and reordering (when we have a direct reference to the node)

The HashMap maps keys to linked list nodes. The linked list maintains access order: the most recently used item is at the head, the least recently used is at the tail. When we access a key, we look it up in the HashMap (O(1)), get the node, remove it from its current position in the linked list (O(1) because it's doubly linked), and move it to the head (O(1)).

This combination — HashMap for lookup, Doubly Linked List for ordering — is the classic solution and the one we'll implement.

In a real interview, spend 2-3 minutes clarifying requirements before jumping into the data structure design. Ask questions like:

• "Should the cache be thread-safe, or can I assume single-threaded access?" — This dramatically changes the implementation (locks, concurrent data structures).
• "Are keys always integers, or should I support generic types?" — Affects your type design.
• "Is there a specific eviction policy you'd like, or should I default to LRU?" — Shows you know alternatives exist (LFU, FIFO, TTL).
• "Should get on a non-existent key return a default value or raise an exception?" — Clarifies error handling.
• "Do we need a delete(key) operation, or just get and put?" — Determines scope.

The classic interview formulation (LeetCode #146) asks for integer keys and values with just get and put. But demonstrating awareness of the broader design space shows engineering maturity.