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
▶
Class Trace
Step 1/4
LRUCache composition with DoublyLinkedList and HashMap

LRUCache composes DoublyLinkedList and HashMap to maintain order and O(1) access. Composition means DLL and map lifecycles are bound to LRUCache.

🎯 Tests if candidate understands composition enforces lifecycle ownership and why DLL is used for O(1) eviction and insertion.
public class LRUCache {
    private final int capacity;
    private final HashMap<Integer, Node> map;
    private final DoublyLinkedList dll;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.dll = new DoublyLinkedList();
    }
}
Node as a simple data holder with prev/next references

Node holds key, value, and pointers to prev and next nodes enabling O(1) removal and insertion in DLL. Node is a POJO without behavior.

🎯 Tests if candidate knows Node must hold state (fields) and why it cannot be interface but a concrete class.
public class Node {
    int key, value;
    Node prev, next;
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}
CacheEvictionListener interface and CacheStatistics realization

CacheEvictionListener is an interface for observer pattern; CacheStatistics implements it to track evictions. Realization uses Java interface mechanism.

🎯 Tests if candidate understands interface cannot hold state but enables OCP for eviction listeners.
public interface CacheEvictionListener {
    void onEvict(int key);
}
public class CacheStatistics implements CacheEvictionListener {
    private int hits = 0, misses = 0;
    public synchronized void recordHit() { hits++; }
    public synchronized void recordMiss() { misses++; }
    @Override
    public void onEvict(int key) {
        // update stats on eviction
    }
}
DoublyLinkedList methods for O(1) addFirst, remove, removeLast

DoublyLinkedList provides O(1) operations to add or remove nodes, critical for LRU eviction. It composes Nodes but Nodes can exist independently.

🎯 Tests if candidate can explain why DLL is a separate class for SRP and how composition is used for lifecycle clarity.
public class DoublyLinkedList {
    private Node head, tail;
    public void addFirst(Node node) {
        node.next = head;
        if (head != null) head.prev = node;
        head = node;
        if (tail == null) tail = node;
    }
    public void remove(Node node) {
        if (node.prev != null) node.prev.next = node.next;
        else head = node.next;
        if (node.next != null) node.next.prev = node.prev;
        else tail = node.prev;
    }
    public Node removeLast() {
        if (tail == null) return null;
        Node last = tail;
        remove(last);
        return last;
    }
}
📐
Class Diagram
Class Diagram
       +----------------+
       |    LRUCache    |
       +----------------+
       | -capacity:int  |
       | -map:HashMap   |
       | -dll:DoublyList|
       | -listeners:Set |
       +----------------+
       | +get(key):int  |
       | +put(k,v):void |
       | +addListener() |
       +----------------+
              ◆ Composition
              │
       +--------------------+
       |  DoublyLinkedList  |
       +--------------------+
       | -head:Node         |
       | -tail:Node         |
       +--------------------+
       | +addFirst(Node)    |
       | +remove(Node)      |
       | +removeLast():Node |
       +--------------------+
              ◆ Composition
              │
       +-----------+
       |   Node    |
       +-----------+
       | -key:int  |
       | -value:int|
       | -prev:Node|
       | -next:Node|
       +-----------+
       |           |
       +-----------+
              ─ ─ ─▶ Realization
              │
       +-----------------------+
       | CacheEvictionListener |<<Interface>>
       +-----------------------+
       | +onEvict(key:int)     |
       +-----------------------+
              ─ ─ ─▶ Realization
              │
       +----------------+
       | CacheStatistics|
       +----------------+
       | -hits:int      |
       | -misses:int    |
       +----------------+
       | +recordHit()   |
       | +recordMiss()  |
       +----------------+
Design Rationale

This class diagram illustrates the LRUCache design using composition to tightly couple the cache with its DoublyLinkedList and HashMap, ensuring lifecycle ownership and O(1) operations. The Node class is a concrete data holder with prev and next pointers, essential for efficient DLL operations. The CacheEvictionListener interface enables extensibility via the observer pattern, allowing implementations like CacheStatistics to track evictions without modifying LRUCache, enforcing the Open-Closed Principle. The DoublyLinkedList encapsulates node management, adhering to Single Responsibility Principle and enabling O(1) add and remove operations. These Java-specific design choices leverage composition, interface realization, and concrete classes with state to build a performant and extensible LRU cache.

Primary Focus

✓ Composition lifecycle + Observer realization + Abstract class state + Doubly linked list O(1) ops

Practice

(1/5)
1. Given a Vehicle abstraction in Java that requires both state (like speed) and behavior (like accelerate()), should Vehicle be an abstract class or an interface? Why?
easy
A. Abstract class, because interfaces cannot define any methods.
B. Interface, because it allows multiple inheritance and can hold state variables.
C. Interface, because it can provide default method implementations with state variables.
D. Abstract class, because it can hold state and provide default behavior implementations.

Solution

  1. Step 1: Analyze state and behavior requirements

    Vehicle needs to hold state (speed) and behavior (accelerate()), which requires fields and method implementations.

  2. Step 2: Choose correct OOP construct

    Abstract classes can hold state and provide default behavior, while interfaces cannot hold instance state (fields) and only allow default methods without state.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Abstract class supports state and behavior, interface does not hold state [check]
Hint: State needs abstract class; interfaces can't hold instance variables [check]
Common Mistakes:
2. In designing a Command interface in Java, should it be an abstract class or an interface, and why? Consider that commands may need to store state for undo functionality.
easy
A. Abstract class, because it allows sharing common state and default undo logic among commands
B. Abstract class, because interfaces cannot declare methods
C. Interface, because Java interfaces can have default methods to share code and state
D. Interface, because commands only declare behavior and state should be external

Solution

  1. Step 1: Analyze state requirements for undo

    Commands often need to store state (e.g., previous values) to support undo, which requires fields.

  2. Step 2: Compare interface vs abstract class in Java

    Interfaces cannot hold instance fields, so abstract classes are better to share common state and default undo logic.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Abstract class supports shared state and behavior for undo [check]
Hint: Use abstract class for shared state in commands [check]
Common Mistakes:
3. In the Elevator System design, the ElevatorController class uses a private constructor and a static synchronized getInstance() method to provide a single global access point. Which design pattern is applied here and why is it the correct choice?
easy
A. Factory pattern, because it creates ElevatorController instances on demand.
B. Singleton pattern, to ensure only one ElevatorController manages all elevators centrally.
C. Builder pattern, to incrementally construct ElevatorController with complex configuration.
D. Prototype pattern, to clone ElevatorController for each elevator instance.

Solution

  1. Step 1: Identify Singleton usage

    The private constructor and static synchronized getInstance() method restrict instantiation to one object, ensuring a single ElevatorController.

  2. Step 2: Why Singleton fits ElevatorController

    ElevatorController coordinates multiple elevators and floor queues centrally, so multiple instances would cause inconsistent state and scheduling conflicts.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Singleton ensures one global ElevatorController instance [check]
Hint: Singleton restricts to one instance for centralized control [check]
Common Mistakes:
4. In the Meeting Scheduler, the RoomBookingManager class has a bookRoom() method that checks if a room is available and then marks it booked. Without synchronizing bookRoom(), which exact sequence of events between Thread 1 and Thread 2 causes a double-booking race condition?
medium
A. Thread 1 reads availability as false; Thread 2 reads availability as true; both proceed to book.
B. Thread 1 and Thread 2 both wait on a lock, causing deadlock and no booking.
C. Thread 1 books room; Thread 2 reads availability after booking and cancels its booking.
D. Thread 1 checks isAvailable() -> true, context switch before booking; Thread 2 checks isAvailable() -> true, both book simultaneously.

Solution

  1. Step 1: Identify check-then-act gap

    Without synchronization, Thread 1 reads availability as true but is preempted before booking; Thread 2 also reads true and proceeds.

  2. Step 2: Both threads book simultaneously causing double-booking

    Because the availability check and booking are not atomic, both threads can book the same room concurrently.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Unsynchronized check-then-act -> double-booking race [check]
Hint: Check-then-act without sync -> double-booking race [check]
Common Mistakes:
5. To add an ElectricPlayer who requires ChargingSpot in the Snake and Ladder game, what is the minimum change to the current design to maintain extensibility without modifying existing classes?
hard
A. Add ELECTRIC_PLAYER to PlayerType enum, add CHARGING to SpotType enum, create ElectricPlayer extends Player, update SpotCompatibility map.
B. Modify Player class to include charging logic and add ChargingSpot as a new field.
C. Create a new ElectricPlayer class and modify Board to handle ChargingSpots explicitly.
D. Add charging behavior directly inside Player class and update all existing player types.

Solution

  1. Step 1: Identify extensibility without modifying existing classes

    Adding new enum values and new subclass preserves existing class code unchanged.

  2. Step 2: Update compatibility map for new player and spot types

    SpotCompatibility map extension allows new rules without changing existing logic.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    New enums + subclass + compatibility map extension -> minimal existing code change [check]
Hint: New enums + subclass + map update = extensible addition [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