TIC
The Interns Company

LRU Cache

MediumAcceptance: 39.8%
Hash TableLinked ListDesign

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with get and put operations.

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls will be made to get and put

Input Format:

  • LRUCache constructor takes an integer capacity
  • get(key) - Get the value of the key if it exists, otherwise return -1
  • put(key, value) - Set or insert key-value pair. When the cache reaches capacity, evict the least recently used key

Output Format:

  • Return values according to the method calls

Examples:

Example 1:

Input:

cache = new LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1); cache.put(3, 3); cache.get(2); cache.put(4, 4); cache.get(1); cache.get(3); cache.get(4);

Output:

[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation:

LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); lRUCache.put(2, 2); lRUCache.get(1); // return 1; lRUCache.put(3, 3); // evicts key 2; lRUCache.get(2); // returns -1 (not found); lRUCache.put(4, 4); // evicts key 1; lRUCache.get(1); // return -1 (not found); lRUCache.get(3); // return 3; lRUCache.get(4); // return 4

Solutions

Hash Map + Doubly Linked List

Time: O(1) for both get and put operations
Space: O(capacity)

Combine a hash map with a doubly linked list for O(1) operations.

Algorithm Walkthrough

Example input:

Step-by-step execution:

  1. capacity=2, cache={}, head<->tail
  2. put(1,1): cache={1: node1}, head<->node1<->tail
  3. put(2,2): cache={1: node1, 2: node2}, head<->node2<->node1<->tail
  4. get(1): move node1 to front, head<->node1<->node2<->tail, return 1
  5. put(3,3): cache full, remove tail.prev (node2), cache={1: node1, 3: node3}, head<->node3<->node1<->tail
  6. get(2): not in cache, return -1
  7. put(4,4): cache full, remove tail.prev (node1), cache={3: node3, 4: node4}, head<->node4<->node3<->tail
  8. get(1): not in cache, return -1
  9. get(3): move node3 to front, head<->node3<->node4<->tail, return 3
  10. get(4): move node4 to front, head<->node4<->node3<->tail, return 4

Hints

Hint 1
Use a hash map for O(1) lookup and a doubly linked list for O(1) removal and insertion.
Hint 2
Move a node to the front of the list when it's accessed.
Hint 3
Remove the node at the end of the list when the cache is full.

Video Tutorial

LRU Cache Implementation

YouTube•Learn the LRU Cache solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the doubly linked list operations as items are accessed and updated.

Key visualization elements:

  • current node
  • head
  • tail
  • cache updates

Asked By

AmazonMicrosoftFacebookGoogleAppleUber

Implementation Notes

This problem tests understanding of both data structures (hash maps and linked lists) and algorithm design. Efficiently implementing an LRU cache requires a combination of O(1) lookup and O(1) update operations.