Getting Ready: LRU Cache

Caching is one of the most universal performance optimization techniques in software engineering. Every time you open a web page, your browser checks its cache before making a network request. Every time a database query runs, the query result may be served from an in-memory cache instead of hitting the disk. Every time your CPU fetches a memory address, it first checks its L1/L2/L3 caches.

But caches have a fundamental constraint: memory is finite. You can't store everything forever. When the cache is full and a new entry arrives, something must be evicted. This leads to the core question: which item should be removed?

The Least Recently Used (LRU) eviction policy answers this question with a simple but powerful heuristic: evict the item that hasn't been accessed for the longest time. This is grounded in the principle of temporal locality — if data was accessed recently, it's likely to be accessed again soon.

Real-world systems that rely on LRU caching include:

• Redis and Memcached — the two most popular caching systems use LRU (or approximations of it) as their default eviction policy
• Operating Systems — page replacement in virtual memory systems uses LRU variants (Linux's page cache, Windows' working set manager)
• CDNs (Cloudflare, Akamai) — cache recently requested content at edge servers
• CPU caches — hardware LRU approximations determine which cache lines to evict
• Database query caches (MySQL, PostgreSQL) — keep recently executed query results in memory

This problem is also one of the most frequently asked in technical interviews at companies like Google, Meta, Amazon, and Microsoft — both as a standalone data structure question (LeetCode #146) and as a building block within larger system design discussions.

In this design problem, you will:

• Design a data structure from scratch — combine a HashMap and a Doubly Linked List to achieve O(1) time complexity for both get and put operations
• Model the system with UML — create a class diagram showing how the cache, its internal data structures, and node objects relate to each other
• Implement in Python and Java — write complete, compilable code for both languages
• Add thread safety — extend the basic LRU Cache to handle concurrent access from multiple threads safely
• Apply the Decorator Pattern — understand how TTL (time-to-live) expiration can be layered on top of the base cache without modifying it
• Test edge cases — handle scenarios like single-capacity caches, duplicate key updates, and concurrent evictions

Unlike most design problems in this course that model a real-world system (like a Parking Lot or Elevator), the LRU Cache is a data structure design problem. The focus is on algorithmic efficiency and internal structure rather than domain modeling with many interacting actors.

Before starting this problem, make sure you're comfortable with:

• Hash Maps (Dictionaries) — O(1) average-case lookup by key. You should understand how hash tables work internally (hashing, collision handling)
• Linked Lists — specifically doubly linked lists, where each node has pointers to both the next and previous nodes. You should be comfortable with insertion, deletion, and pointer manipulation
• OOP Fundamentals — classes, encapsulation, composition (Fundamentals S1-S4). The LRU Cache composes a HashMap and a Doubly Linked List internally
• Time & Space Complexity — you should understand why O(1) matters here — a cache that takes O(n) to read defeats the purpose of caching
• UML Class Diagrams — how to read class boxes, relationships, and multiplicities (Fundamentals S5)

If you've completed the Parking Lot (DP1), Tic Tac Toe (DP2), and Snake and Ladder (DP3) problems, you're well-prepared for this one. The LRU Cache introduces a new challenge: designing for algorithmic efficiency rather than domain complexity.

We will design: The core LRU Cache data structure — classes for the cache itself, the internal doubly linked list, and node objects. We'll implement get(key) and put(key, value) with O(1) time complexity, add thread safety with locks, and discuss how the Decorator Pattern enables TTL expiration.

We will NOT design: A distributed caching system (like Redis cluster), network protocols, serialization, cache warming strategies, or persistence layers. This is a Low Level Design (object-oriented) exercise focused on the data structure's internal design, not a System Design (infrastructure) problem.

Difficulty: Easy — This is one of the simpler design problems in the course because it has a small number of classes (4-5) and a focused scope. However, the algorithmic elegance of combining two data structures for O(1) operations makes it a deeply satisfying design to understand.