Description

Editorial

Design an LRU Cache

Intermediate

Design a Least Recently Used (LRU) Cache that supports O(1) get and put operations using a HashMap and a Doubly Linked List.

When the cache exceeds its fixed capacity, the least recently used entry is automatically evicted. Both get() and put() should mark the accessed key as most recently used. The design should cleanly separate the data structure from the eviction policy for extensibility to LFU, FIFO, etc.

Core Use Cases

Get a value by key

Return the value for a key in O(1) and mark it as most recently used; return -1 if not present

Put a key-value pair

Insert a new entry or update an existing one in O(1); if capacity is exceeded, evict the LRU entry

Evict least recently used

When the cache is full, automatically remove the entry that was accessed longest ago

Delete a key explicitly

Remove a specific key from the cache on demand

Clear the cache

Remove all entries at once

Query cache size

Return the current number of entries

Constraints

Both get and put must run in O(1) average time
The cache has a fixed, positive capacity set at construction time
When capacity is exceeded, the least recently used entry is evicted automatically
get() marks the entry as most recently used
put() on an existing key updates the value and marks it as most recently used

Assumptions

Keys and values are integers (generalise with generics as a follow-up)
Single-threaded access (thread-safety is a follow-up)
No TTL / expiration on entries (follow-up topic)

In Scope

HashMap + Doubly Linked List data structure design
O(1) get, put, and delete operations
LRU eviction policy
Sentinel nodes for clean edge-case handling
EvictionPolicy abstraction for extensibility

Out of Scope

Thread-safe / concurrent cache
TTL-based expiration
Distributed caching (Redis-like)
Cache statistics (hit rate, miss rate)
Persistence / write-through / write-back

Approach Guide(Click to expand each section)

Before diving into code, clarify the use cases and edge cases. Understanding the problem deeply leads to better class design.

List Core Use Cases

Identify the primary actions users will perform. For a parking lot: park vehicle, exit vehicle, check availability. Each becomes a method.

Identify Actors

Who interacts with the system? Customers, admins, automated systems? Each actor type may need different interfaces.

Clarify Constraints

What are the limits? Max vehicles, supported vehicle types, payment methods. Constraints drive your data structures.

Ask About Edge Cases

What happens on overflow? Concurrent access? Payment failures? Thinking about edge cases reveals hidden complexity.

Follow-up Questions(Questions an interviewer might ask)

UML

Code

Submissions

Solutions

💡 Draw UML class diagrams, sequence diagrams, or any design visualizations. Submit from the Code tab.

Loading canvas...

Loading LLD design...

Description

Editorial

Design an LRU Cache

Intermediate

Design a Least Recently Used (LRU) Cache that supports O(1) get and put operations using a HashMap and a Doubly Linked List.

Core Use Cases

Get a value by key

Return the value for a key in O(1) and mark it as most recently used; return -1 if not present

Put a key-value pair

Insert a new entry or update an existing one in O(1); if capacity is exceeded, evict the LRU entry

Evict least recently used

When the cache is full, automatically remove the entry that was accessed longest ago

Delete a key explicitly

Remove a specific key from the cache on demand

Clear the cache

Remove all entries at once

Query cache size

Return the current number of entries

Constraints

Both get and put must run in O(1) average time
The cache has a fixed, positive capacity set at construction time
When capacity is exceeded, the least recently used entry is evicted automatically
get() marks the entry as most recently used
put() on an existing key updates the value and marks it as most recently used

Assumptions

Keys and values are integers (generalise with generics as a follow-up)
Single-threaded access (thread-safety is a follow-up)
No TTL / expiration on entries (follow-up topic)

In Scope

HashMap + Doubly Linked List data structure design
O(1) get, put, and delete operations
LRU eviction policy
Sentinel nodes for clean edge-case handling
EvictionPolicy abstraction for extensibility

Out of Scope

Thread-safe / concurrent cache
TTL-based expiration
Distributed caching (Redis-like)
Cache statistics (hit rate, miss rate)
Persistence / write-through / write-back

Approach Guide(Click to expand each section)

Before diving into code, clarify the use cases and edge cases. Understanding the problem deeply leads to better class design.

List Core Use Cases

Identify the primary actions users will perform. For a parking lot: park vehicle, exit vehicle, check availability. Each becomes a method.

Identify Actors

Who interacts with the system? Customers, admins, automated systems? Each actor type may need different interfaces.

Clarify Constraints

What are the limits? Max vehicles, supported vehicle types, payment methods. Constraints drive your data structures.

Ask About Edge Cases

What happens on overflow? Concurrent access? Payment failures? Thinking about edge cases reveals hidden complexity.

Follow-up Questions(Questions an interviewer might ask)

UML

Code

Submissions

Solutions

💡 Draw UML class diagrams, sequence diagrams, or any design visualizations. Submit from the Code tab.

Loading canvas...

Design an LRU Cache

Core Use Cases

Constraints

Assumptions

In Scope

Out of Scope

Approach Guide(Click to expand each section)

Gather Requirements~3 min

Identify Classes & Entities~4 min

Define Relationships~3 min

Apply Design Patterns~4 min

Apply SOLID Principles~3 min

Code Organization~2 min

Follow-up Questions(Questions an interviewer might ask)

1How would you make the cache thread-safe?

2How would you add TTL-based expiration to each entry?

3How would you implement an LFU (Least Frequently Used) cache instead?

4How would you make the cache generic (support any key/value types)?

5How would you add cache hit/miss statistics?

Key Topics

Asked At

Design an LRU Cache

Core Use Cases

Constraints

Assumptions

In Scope

Out of Scope

Approach Guide(Click to expand each section)

Gather Requirements~3 min

Identify Classes & Entities~4 min

Define Relationships~3 min

Apply Design Patterns~4 min

Apply SOLID Principles~3 min

Code Organization~2 min

Follow-up Questions(Questions an interviewer might ask)

1How would you make the cache thread-safe?

2How would you add TTL-based expiration to each entry?

3How would you implement an LFU (Least Frequently Used) cache instead?

4How would you make the cache generic (support any key/value types)?

5How would you add cache hit/miss statistics?

Key Topics

Asked At