How to Solve LRU Cache

This problem requires designing a Least Recently Used (LRU) cache supporting O(1) get and put operations. Use a hash table for fast key access and a doubly-linked list to track usage order. Correct pointer manipulation in the linked list ensures proper eviction of the least recently used items when capacity is exceeded, making it critical to manage head and tail updates precisely.

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with a constructor taking a capacity, and two functions get(key) and put(key, value) that retrieve and insert key-value pairs, respectively, while maintaining usage order.

The get and put functions must run in O(1) average time complexity. When the cache reaches its capacity, inserting a new item must evict the least recently used entry. You must combine a hash table for direct access and a doubly-linked list for tracking usage to maintain the LRU property efficiently.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

Solution Approach

Hash Table for Fast Key Access

Use a hash table to map keys directly to nodes in the linked list. This ensures that get(key) can locate nodes in O(1) time without traversing the list, which is critical for maintaining constant-time access in the LRU cache.

Doubly-Linked List for Usage Order

Maintain a doubly-linked list where the most recently used node is moved to the head and the least recently used node is at the tail. Properly update the previous and next pointers when nodes are accessed or inserted, as incorrect pointer manipulation can break the LRU order.

Eviction on Capacity Limit

When adding a new key exceeds the cache capacity, remove the tail node from the doubly-linked list and delete its key from the hash table. This eviction step must precisely handle pointer updates to prevent dangling references and preserve list integrity.

Complexity Analysis

Time complexity is O(1) for get and put due to hash table access and constant-time list pointer updates. Space complexity is O(capacity) for storing nodes in both hash table and linked list.

What Interviewers Usually Probe

• Emphasizing O(1) get and put is key to assess understanding of combined hash table and linked list design.
• Watch for candidates managing head/tail pointers carefully; mismanagement indicates misunderstanding of doubly-linked list operations.
• Check for clear handling of eviction when capacity is reached, as failure here often causes subtle bugs.

Common Pitfalls or Variants

Common pitfalls

• Forgetting to update both previous and next pointers when moving nodes leads to broken list connections.
• Neglecting to remove evicted nodes from the hash table causes memory leaks or incorrect retrievals.
• Assuming a singly-linked list is sufficient; LRU eviction requires doubly-linked list for O(1) removals.

Follow-up variants

• Implement LRU Cache using only a singly-linked list and analyze the trade-offs in time complexity.
• Design a Most Recently Used (MRU) Cache by reversing insertion/removal logic in the linked list.
• Extend LRU Cache to support a getMostRecentKey() operation in O(1) time without affecting existing operations.

How GhostInterview Helps

• GhostInterview provides a guided explanation of linked-list pointer manipulation in LRU Cache, reducing pointer errors.
• It highlights the trade-offs of hash table and doubly-linked list usage to maintain O(1) operations.
• GhostInterview shows step-by-step eviction handling and list updates to prevent common mismanagement mistakes.

Topic Pages

• Hash Table
• Linked List
• Design
• Doubly-Linked List

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the best approach for implementing LRU Cache with O(1) operations?

Combine a hash table for direct key access with a doubly-linked list to maintain usage order and handle eviction efficiently.

Why does LRU Cache require a doubly-linked list instead of singly-linked?

A doubly-linked list allows O(1) removal of arbitrary nodes and easy movement to the head, which is essential for maintaining the correct LRU order.

How do you handle eviction when the cache exceeds capacity?

Remove the tail node from the doubly-linked list and delete its key from the hash table, ensuring all pointers are correctly updated.

Can the get and put operations ever exceed O(1) time in LRU Cache?

No, if implemented correctly with a hash table and doubly-linked list, all operations run in O(1) average time regardless of cache size.

What are common mistakes when manipulating pointers in LRU Cache linked list?

Typical mistakes include failing to update previous/next pointers when moving nodes, not updating head/tail correctly, and leaving evicted nodes in the hash table.