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
40 min · medium
medium

Implement an LRU Cache that supports get(key) and put(key, value) operations in O(1) time complexity. The cache should evict the least recently used entry when capacity is exceeded. Use Java-specific concurrency mechanisms to ensure thread safety.

Given Info
  • Cache capacity is fixed and provided at construction time.
  • get(key) returns the value if present, else -1.
  • put(key, value) inserts or updates the value and marks the key as most recently used.
  • Eviction removes the least recently used entry when capacity is exceeded.
  • Operations must be thread-safe for concurrent access.
  • Use HashMap for O(1) key lookup and Doubly Linked List for maintaining usage order.
📋
Guided Steps
1/5
Step 1
Define the Node class for Doubly Linked List
Design a Node class to represent entries in the doubly linked list that stores cache entries. What fields and methods should it have?
💡 Hint
Node must hold key and value fields to support eviction and updates. Use strong typing with generics if possible.
Key Decision
Use a private static nested class Node<K,V> with fields K key, V value, Node<K,V> prev, next - static nested class to avoid implicit reference to outer class and reduce memory overhead.
Interviewer Expectation
Mid: Defines Node with key, value, prev, next fields. Senior: Explains why static nested class avoids memory leaks by not holding implicit outer instance reference.
⚠️Common Wrong Answer
Using a non-static inner class Node causes implicit reference to outer LRUCache instance, increasing memory footprint and risking memory leaks.
Step 2
Choose data structures for O(1) operations
Which data structures will you use to achieve O(1) get and put operations, and how will they interact?
💡 Hint
HashMap provides O(1) key lookup; Doubly Linked List maintains usage order for eviction.
Key Decision
Use HashMap<K, Node<K,V>> for O(1) lookup and a custom Doubly Linked List of Node<K,V> for O(1) insertion and removal; maintain head and tail pointers for quick access to MRU and LRU nodes.
Interviewer Expectation
Mid: Names HashMap and Doubly Linked List for O(1) operations. Senior: Explains how HashMap stores references to nodes, enabling O(1) removal from linked list without traversal.
⚠️Common Wrong Answer
Using a singly linked list for usage order causes O(n) removal of arbitrary nodes, violating O(1) requirement.
Step 3
Implement thread-safe get and put methods
How will you ensure thread safety for concurrent get and put operations in Java?
💡 Hint
Use synchronized methods or blocks to atomically update HashMap and linked list pointers.
Key Decision
Declare public synchronized V get(K key) and public synchronized void put(K key, V value) to atomically check and update cache state, preventing race conditions on shared mutable state.
Interviewer Expectation
Mid: Uses synchronized keyword on get and put. Senior: Traces race condition where Thread 1 reads map, context switch, Thread 2 modifies map and list, Thread 1 proceeds with stale data causing inconsistency.
⚠️Common Wrong Answer
Not synchronizing get and put leads to race conditions where concurrent modifications corrupt linked list pointers or HashMap entries, causing data loss or infinite loops.
Step 4
Design eviction logic for capacity management
How will you implement eviction of the least recently used entry when capacity is exceeded?
💡 Hint
Remove the tail node from the doubly linked list and delete its key from the HashMap.
Key Decision
Eviction removes tail Node<K,V> from doubly linked list and calls map.remove(tail.key) inside synchronized put method to maintain atomicity and consistency.
Interviewer Expectation
Mid: Removes tail node on capacity breach. Senior: Explains why eviction must be inside synchronized block to prevent concurrent evictions causing inconsistent state or NullPointerException.
⚠️Common Wrong Answer
Evicting outside synchronized context causes race conditions where multiple threads evict simultaneously, corrupting linked list or map.
Step 5
Separate concerns with helper methods for linked list operations
How will you modularize linked list operations to improve code maintainability and extensibility?
💡 Hint
Create private helper methods for adding, removing, and moving nodes to head.
Key Decision
Implement private synchronized void addNodeToHead(Node<K,V> node), removeNode(Node<K,V> node), and moveToHead(Node<K,V> node) methods to encapsulate linked list manipulation and reuse synchronization.
Interviewer Expectation
Mid: Creates helper methods for linked list operations. Senior: Explains how synchronized helper methods prevent partial updates and maintain list integrity under concurrency.
⚠️Common Wrong Answer
Inlined linked list code in get/put leads to duplicated code and higher risk of bugs; lack of synchronization in helpers causes inconsistent list state.
🔌
API Design Challenge
Design a clean and intuitive API for the LRU Cache that supports get and put operations with thread safety and eviction policy.
Hints
  • Consider method signatures that clearly indicate thread safety, e.g., synchronized methods.
  • Think about how to expose cache capacity and current size safely.
  • Design for extensibility, allowing future enhancements without breaking existing clients.
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Node as private static nested class with key, value, prev, next fields
  • HashMap<K, Node<K,V>> for O(1) lookup
  • Doubly linked list with head and tail pointers for usage order
  • Synchronized get and put methods for thread safety
  • Eviction logic inside synchronized put method
Good to Have - 30%
  • Private synchronized helper methods for linked list operations
  • Use of generics for type safety
  • Immutable capacity field
  • Encapsulation of internal data structures
Bonus - 10%
  • Explanation of static nested class benefits
  • Detailed concurrency scenario tracing race conditions
Anti-patterns to Avoid
Using non-static inner Node class causing memory leaks due to implicit outer class reference increases memory footprint and risks leaks.
Using singly linked list causing O(n) removal violates O(1) requirement, leading to performance degradation.
Not synchronizing get and put causes race conditions and data corruption, risking infinite loops or lost updates.
Evicting outside synchronized context causes concurrent eviction bugs, corrupting linked list or map state.
Inlined linked list manipulation code causes duplication and concurrency bugs due to inconsistent list state.
✅
Model Answer
▼ Reveal

The LRU Cache is implemented using a HashMap for O(1) key lookup and a doubly linked list to maintain usage order. The cache supports thread-safe get and put operations with eviction of the least recently used entry when capacity is exceeded.

Key Decisions
  • Use of static nested Node class to avoid implicit outer class reference and reduce memory overhead.
  • HashMap stores references to nodes enabling O(1) removal from doubly linked list without traversal.
  • Synchronized get and put methods prevent race conditions by atomic updates of map and linked list.
  • Eviction logic placed inside synchronized put method to maintain consistency and avoid concurrent eviction issues.
  • Helper methods for linked list operations encapsulate logic and maintain thread safety with synchronized keyword.
  • Capacity is final and immutable to prevent inconsistent cache size during concurrent operations.
  • Generics <K,V> used for type safety and reusability.
  • Internal data structures are encapsulated and not exposed to clients to prevent external modification.
  • Node class as private static nested class with key, value, prev, next fields to hold cache entries and pointers.
  • HashMap<K, Node<K,V>> for O(1) key lookup storing references to nodes in doubly linked list.
  • Doubly linked list with head and tail pointers to maintain usage order; head is most recently used, tail is least recently used.
  • Synchronized get(K key) and put(K key, V value) methods to ensure atomicity and prevent race conditions on shared mutable state.
  • Eviction logic inside synchronized put method removes tail node and deletes corresponding map entry atomically.
  • Private synchronized helper methods addNodeToHead, removeNode, and moveToHead encapsulate linked list operations and maintain thread safety.
  • Use of static nested class Node avoids implicit outer class reference, reducing memory overhead and preventing memory leaks.
  • Capacity is final and immutable after construction to prevent inconsistent cache size during concurrent operations.
  • Use of generics <K,V> for type safety and reusability of cache implementation.
  • Avoid exposing internal data structures to clients to maintain encapsulation and prevent external modification.

Practice

(1/5)
1. In the auction system, should the Bid entity be designed as an abstract class or an interface? Consider that bids have state (amount, bidder) and behavior (validate, notify). Which is the best choice and why?
easy
A. Interface, because it allows multiple inheritance and enforces method signatures without state.
B. Interface, because bids only define behavior and state is stored externally in a database.
C. Abstract class, because it can hold common bid state and provide default behavior implementations.
D. Abstract class, because it forces all subclasses to implement all methods explicitly without defaults.

Solution

  1. Step 1: Analyze state and behavior needs

    Bids have shared state (amount, bidder) and common behavior (validation, notification), which benefit from code reuse and encapsulation.

  2. Step 2: Compare abstract class vs interface

    Abstract classes can hold state and provide default method implementations; interfaces cannot hold state and only define method signatures.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful entity with shared behavior -> abstract class [check]
Hint: State + behavior reuse -> abstract class, not interface [check]
Common Mistakes:
2. A class has a private constructor and a clone() method that returns a copy of itself. Which design pattern is applied here and why is this the correct use case?
easy
A. Builder pattern, because it separates object construction from representation
B. Singleton pattern, because it restricts instantiation to one object
C. Factory pattern, because it creates objects through a factory method
D. Prototype pattern, because cloning avoids expensive object construction

Solution

  1. Step 1: Identify the pattern from constructor and clone()

    The private constructor prevents direct instantiation, and the presence of a clone() method indicates object copying rather than new creation.

  2. Step 2: Match pattern intent to scenario

    The Prototype pattern is used to clone objects when construction is expensive, which fits the scenario. Singleton restricts to one instance, Factory creates new instances, and Builder separates construction steps.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Private constructor + clone() -> Prototype pattern [check]
Hint: Private constructor + clone() means Prototype pattern [check]
Common Mistakes:
3. You want to add a WeekendRetryPolicy to the Job Scheduler without modifying existing classes. Which SOLID principle guides the minimum change, and what is the correct approach?
medium
A. Open/Closed Principle: create a new class WeekendRetryPolicy implementing RetryPolicy interface without changing existing code.
B. Single Responsibility Principle: modify RetryPolicy to handle weekends explicitly.
C. Dependency Inversion Principle: inject WeekendRetryPolicy into Job class by modifying Job constructor.
D. Liskov Substitution Principle: override existing RetryPolicy methods to add weekend logic.

Solution

  1. Step 1: Identify the SOLID principle for extensibility

    Open/Closed Principle (OCP) states software entities should be open for extension but closed for modification.

  2. Step 2: Apply OCP to add WeekendRetryPolicy

    Create a new class implementing RetryPolicy interface to add weekend-specific logic without modifying existing RetryPolicy or Job classes.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    New class implements interface -> no existing code changed [check]
Hint: OCP: extend by new class, don't modify existing [check]
Common Mistakes:
4. In a Singleton class without synchronized on getInstance(), what EXACT sequence of Thread 1 and Thread 2 calls can cause two instances to be created?
medium
A. Thread 1 checks instance == null -> true, context switch before creation; Thread 2 checks instance == null -> true, both create separate instances.
B. Thread 1 calls getInstance(), completes instance creation; Thread 2 calls getInstance() and returns same instance.
C. Thread 1 calls getInstance() twice in a row; Thread 2 waits until Thread 1 finishes.
D. Thread 1 and Thread 2 both call getInstance() after instance is created, returning the same instance.

Solution

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

    Without synchronization, both threads can see instance == null before either creates it.

  2. Step 2: Trace thread interleaving

    Thread 1 checks instance == null -> true, context switch before creating instance. Thread 2 also checks instance == null -> true, proceeds to create a second instance, causing double instantiation.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Unsynchronized lazy init -> check-then-act race causes two instances [check]
Hint: Check-then-act without sync -> double instance creation [check]
Common Mistakes:
5. ElectricCar needs to be added to the product catalog with ChargingSpots. What is the minimum change to support this without modifying existing classes?
hard
A. Create a new ElectricCar class and a new ChargingSpot class, modifying Vehicle and Spot base classes to support them
B. Add ELECTRIC_CAR to VehicleType enum and CHARGING to SpotType enum, create ElectricCar extends Vehicle, update SpotCompatibility.COMPATIBILITY_MAP accordingly
C. Modify Vehicle class to add isElectric flag and add charging logic inside existing ParkingSpot classes
D. Add charging logic inside Vehicle class and extend SpotType enum with charging spots, modifying existing compatibility logic

Solution

  1. Step 1: Identify extensibility without modifying existing classes

    Adding new enum values and new classes for ElectricCar and ChargingSpot allows extension without changing existing class code, preserving OCP.

  2. Step 2: Why updating compatibility map is needed

    SpotCompatibility.COMPATIBILITY_MAP controls which vehicles fit which spots; updating it ensures ElectricCar and ChargingSpot compatibility without modifying base classes.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    New enums + classes + compatibility map update -> minimal existing class changes [check]
Hint: Add enums + classes + map, no base class changes [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