LRUCache

LRU Cache

Problem Description

Design and implement a Least Recently Used (LRU) cache that supports get and put operations in O(1) time complexity.

What is an LRU Cache?

An LRU cache is a cache eviction policy that removes the least recently used item when the cache reaches its capacity. Items are ordered by their usage - most recently used items are kept, while least recently used items are evicted.

Characteristics

• Time Complexity: O(1) for both get and put operations
• Space Complexity: O(capacity)
• Key Operations: get, put
• Eviction Policy: Remove least recently used item when at capacity

How It Works

1. When an item is accessed (get or put), it becomes the most recently used
2. When cache is full and a new item is added:
   • Remove the least recently used item
   • Add the new item as most recently used
3. Maintain order of usage for efficient eviction

Core Operations

1. get(key):

   • Return value if key exists (and mark as recently used)
   • Return -1 if key doesn't exist

2. put(key, value):

   • If key exists: update value and mark as recently used
   • If key doesn't exist:
     • If at capacity: remove LRU item
     • Add new key-value pair as most recently used

Your Task

Implement the following in LRUCache.java:

1. LRUCache(int capacity) - Constructor
2. get(int key) - Get value and update usage
3. put(int key, int value) - Put value and handle eviction
4. Helper methods for managing doubly linked list

Data Structure Design

Recommended Approach: HashMap + Doubly Linked List

• HashMap: O(1) access to nodes by key
• Doubly Linked List: O(1) removal and insertion
  • Head: Most recently used
  • Tail: Least recently used

Test Cases to Consider

• Basic put and get operations
• Eviction when at capacity
• Updating existing keys
• Access order (get makes item recent)
• Put on existing key updates it
• Edge case: capacity = 1
• Multiple evictions

Hints

• Use a HashMap to store key -> Node mapping
• Use a doubly linked list to maintain usage order
• Head of list = most recently used
• Tail of list = least recently used
• When accessing: move node to head
• When evicting: remove node from tail

Implementation Strategy

Node structure:
- key
- value  
- prev pointer
- next pointer

Main structure:
- HashMap<Integer, Node>
- head pointer (most recent)
- tail pointer (least recent)
- capacity

Common Operations Pattern

Move to front:

1. Remove node from current position
2. Add node at head

Remove from tail:

1. Get tail node
2. Remove from HashMap
3. Update tail pointer

Applications

• Web browser cache
• Database query cache
• Operating system page replacement
• CDN caching
• API rate limiting

Follow-up Questions

1. How would you implement an LFU (Least Frequently Used) cache?
2. How would you add a time-to-live (TTL) feature?
3. How would you make this thread-safe?
4. How would you implement this with only a HashMap (without doubly linked list)?

Common Pitfalls

• Forgetting to update usage order on get
• Not handling capacity = 1 edge case
• Memory leaks (not removing from HashMap when evicting)
• Incorrect pointer updates in doubly linked list
• Not checking if key exists before evicting

Variants

• LFU Cache: Evict least frequently used
• FIFO Cache: Evict first inserted
• TTL Cache: Items expire after time
• 2Q Cache: Two queues with different policies

Related Problems

• Design a cache with expiration
• Implement HashMap
• Design a file system cache
• Implement browser history

Complexity Analysis

Operation	Time	Space
get()	O(1)	-
put()	O(1)	-
Overall	-	O(capacity)