Bird
Raised Fist0

Design an LRU Cache - O(1) Get and Put Using HashMap and Doubly Linked List

LLDhardInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design an LRU Cache - O(1) Get and Put Using HashMap and Doubly Linked List
Implement an LRU Cache with O(1) get and put operations using HashMap and Doubly Linked List
hardInfrastructure and Utility SystemsFreq: high
Prerequisites:HashMapDoubly Linked List
⚙️
Functional Requirements
  • get(key): Return value if key exists, else return -1
  • put(key, value): Insert or update key-value pair
  • Evict least recently used entry when capacity exceeded
  • Maintain usage order to identify least recently used
  • Support thread-safe concurrent get and put operations
  • Cache capacity is fixed and set at initialization
  • Clear cache method to remove all entries
👤
Use Cases
  • Retrieve value by key with O(1) time complexity
  • Insert or update key-value pair with O(1) time complexity
  • Evict least recently used entry when capacity is full
  • Handle concurrent access from multiple threads safely
  • Clear cache on demand
🧑‍💻
Actors
  • Client Application
  • Cache Manager
❓
Clarifying Questions to Ask
  • How many concurrent threads will access the cache?
  • Is the cache size fixed or dynamic?
  • Should the cache support null keys or values?
  • What is the expected eviction policy if multiple entries have same usage?
  • Is there a pricing or cost model for cache misses?
  • Should get operation update usage order?
  • Is the cache expected to be used in a multi-CPU environment?
Out of Scope
✗ Distributed cache synchronization
✗ Persistence of cache data
✗ Cache expiration based on time
✗ Cache size auto-scaling
🔢
Enumerations
enum CacheOperation
GET | PUT | EVICT
Defines cache operations explicitly to avoid string literals and enable exhaustive switch-case handling.
enum NodeStatus
ACTIVE | EVICTED
Tracks node lifecycle state to prevent stale references and support safe eviction.
📦
LRUCache
3 fields
private final int capacityprivate final Map<Integer, Node> cacheMapprivate final DoublyLinkedList usageList
Manages cache operations, maintains capacity, coordinates HashMap and DoublyLinkedList for O(1) get and put.
Why thisHashMap provides O(1) average time complexity for key lookups; DoublyLinkedList maintains usage order efficiently for eviction.
Why notUsing a TreeMap or LinkedHashMap would not guarantee O(1) for both get and put with eviction control; other data structures like singly linked list do not support efficient removal.
Key Methods
public synchronized int get(int key)Returns value for key if present, else -1; updates usage order.
public synchronized void put(int key, int value)Inserts or updates key-value pair; evicts least recently used if capacity exceeded.
public synchronized void clear()Clears all cache entries and resets usage list.
📦
Node
5 fields
int keyint valueNode prevNode nextvolatile NodeStatus status
Represents a doubly linked list node holding key-value pair and linkage pointers.
Why thisNode structure supports quick insertion and removal from doubly linked list, enabling O(1) updates to usage order.
Why notUsing singly linked list nodes would require O(n) removal; arrays do not support dynamic reordering efficiently.
Key Methods
public Node(int key, int value)Initializes node with key and value; sets status to ACTIVE.
📦
DoublyLinkedList
2 fields
private Node headprivate Node tail
Maintains order of nodes from most recently used (head) to least recently used (tail).
Why thisDoubly linked list allows O(1) insertion and removal of nodes from any position, essential for LRU updates.
Why notSingly linked list or array-based structures would not support efficient removal of arbitrary nodes.
Key Methods
public void addFirst(Node node)Adds node at the head of the list.
public void remove(Node node)Removes specified node from the list.
public Node removeLast()Removes and returns the tail node (least recently used).
📦
CacheEvictionListener
1 fields
none
Interface to notify external components when a cache entry is evicted.
Why thisObserver pattern allows decoupling eviction notification from cache logic, enabling extensibility.
Why notDirect callbacks or polling would tightly couple eviction logic and reduce flexibility.
Key Methods
void onEvict(int key, int value)Callback invoked when a cache entry is evicted.
📦
CacheStatistics
2 fields
private AtomicInteger hitCountprivate AtomicInteger missCount
Tracks cache hit and miss counts in a thread-safe manner.
Why thisAtomicInteger provides lock-free thread-safe counters for accurate statistics.
Why notUsing synchronized counters would reduce performance; non-thread-safe counters risk data races.
Key Methods
public void incrementHit()Atomically increments hit count.
public void incrementMiss()Atomically increments miss count.
public int getHitCount()Returns current hit count.
public int getMissCount()Returns current miss count.
🔗
Relationships
LRUCache◇──►Node[1..*]
aggregationNode can exist independently but managed by LRUCache
LRUCache◆──►DoublyLinkedList[1]
compositionDoublyLinkedList lifecycle bound to LRUCache
LRUCache──►CacheEvictionListener[0..1]
associationListener exists independently, LRUCache holds reference
CacheStatistics──►LRUCache[1]
associationCacheStatistics exists independently, LRUCache uses it
🗄️
CacheEntries
PK: cacheId
cacheId UUIDkey intvalue intlastAccessTime timestamp
Stores cache entries with keys and values, partitioned by cache instance.
🗄️
CacheStatistics
PK: cacheId
cacheId UUIDstatType textcount bigint
Stores hit and miss counts per cache instance.
🔌
GET /cache/{cacheId}/entry/{key}
Request
{
  "cacheId": "UUID",
  "key": "int"
}
Response
{
  "value": "int",
  "found": "boolean"
}
Retrieves value for key from specified cache; returns found=false if key missing.
🔌
PUT /cache/{cacheId}/entry
Request
{
  "cacheId": "UUID",
  "key": "int",
  "value": "int"
}
Response
{
  "success": "boolean"
}
Inserts or updates key-value pair in specified cache.
🔌
POST /cache/{cacheId}/clear
Request
{
  "cacheId": "UUID"
}
Response
{
  "success": "boolean"
}
Clears all entries in specified cache.

Practice

(1/5)
1. In the Library Management System, should the Book entity be designed as an abstract class or an interface, considering it has state like title and author and behavior like checkAvailability()? Why?
easy
A. Interface, because it only defines behavior and allows multiple inheritance.
B. Abstract class, because it holds common state and behavior that subclasses share.
C. Interface, because state can be stored externally and behavior defined separately.
D. Abstract class, because it forces all subclasses to implement all methods explicitly.

Solution

  1. Step 1: Analyze state and behavior requirements

    Book has common state (title, author) and behavior (checkAvailability) shared by all book types.

  2. Step 2: Abstract class vs interface for stateful entities

    Abstract classes can hold state and provide default behavior; interfaces cannot hold instance state in Java.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Stateful entity with shared behavior -> Abstract class [check]
Hint: State + behavior shared -> Abstract class, not interface [check]
Common Mistakes:
2. In designing a logging framework, should the LogFormatter be an abstract class or an interface? Consider that formatters have no shared state but must implement a format(LogRecord) method. Why?
easy
A. Interface, because formatters only define behavior without shared state.
B. Abstract class, to allow shared state and default method implementations.
C. Abstract class, because Java interfaces cannot have methods with parameters.
D. Interface, to enforce singleton instances of formatters.

Solution

  1. Step 1: Analyze formatter requirements

    Formatters define a behavior (format method) without shared state or common implementation, making interface a natural fit.

  2. Step 2: Why interface over abstract class

    Interfaces allow multiple implementations without forcing inheritance or shared state. Abstract classes imply shared state or default behavior, which is unnecessary here.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    No shared state + behavior only -> interface [check]
Hint: Behavior only, no state -> interface [check]
Common Mistakes:
3. In a multi-threaded parking lot system, if parkVehicle() is not synchronized, which exact sequence of Thread 1 and Thread 2 calls causes double-booking of the same spot?
medium
A. Thread 1 checks spot availability -> true, context switch; Thread 2 checks spot availability -> true; both park simultaneously.
B. Thread 1 parks vehicle, Thread 2 waits for Thread 1 to finish, then parks vehicle.
C. Thread 1 parks vehicle, Thread 2 parks vehicle immediately after without checking availability.
D. Thread 1 releases spot, Thread 2 parks vehicle before Thread 1 finishes updating status.

Solution

  1. Step 1: Identify race condition

    Without synchronization, both threads can read spot availability as true before either marks it occupied.

  2. Step 2: Trace exact interleaving

    Thread 1: isAvailable() -> true, context switch; Thread 2: isAvailable() -> true; both proceed to park, causing double-booking.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Check-then-act gap without synchronization -> double-booking [check]
Hint: Check availability then park must be atomic to avoid double-booking [check]
Common Mistakes:
4. You want to add a WeekendFeeStrategy to the rate limiter's fee calculation without modifying existing classes. Which SOLID principle applies and what is the minimum change?
medium
A. Add weekend flag to RateLimiter and use if-else inside existing fee method
B. Create new WeekendFeeStrategy implementing FeeStrategy interface; inject it via constructor (OCP and DIP enforced)
C. Modify RateLimiter class to add weekend fee logic directly, violating OCP
D. Create WeekendFeeStrategy but modify existing FeeStrategy implementations to handle weekend

Solution

  1. Step 1: Identify SOLID principle for adding new fee logic

    Open-Closed Principle (OCP) requires adding new behavior without modifying existing code.

  2. Step 2: Evaluate options for minimal change respecting OCP and DIP

    Add weekend flag to RateLimiter and use if-else inside existing fee method adds weekend flag and if-else inside existing method, violating OCP by modifying existing class. Create new WeekendFeeStrategy implementing FeeStrategy interface; inject it via constructor (OCP and DIP enforced) respects OCP and DIP by adding new class and injecting it.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Minimal change but violates OCP by modifying existing class [check]
Hint: OCP: add new class, not modify existing code [check]
Common Mistakes:
5. In a parking lot system, if the parkVehicle() method is NOT synchronized, which exact sequence of Thread 1 and Thread 2 causes double-booking of the same spot?
medium
A. Thread 1 parks vehicle, Thread 2 waits for Thread 1 to release lock before parking.
B. Thread 1 parks vehicle, Thread 2 parks vehicle after Thread 1 finishes.
C. Thread 1 checks spot availability -> true, context switch; Thread 2 checks spot availability -> true; both park simultaneously.
D. Thread 1 and Thread 2 both wait on a condition variable before parking.

Solution

  1. Step 1: Identify the race condition in check-then-act

    Without synchronization, Thread 1 reads spot as available (true) but before it marks it occupied, context switches to Thread 2.

  2. Step 2: Thread 2 also reads spot as available and proceeds to park

    Both threads proceed to park the vehicle, causing double-booking.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Unsynchronized check-then-act -> both threads see available -> double-booking [check]
Hint: Unsynchronized check-then-act -> double-booking race [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard