LRU Cache Design - aloalgo
aloalgo logoaloalgo
Beta
Problems
Login

LRU Cache Design

Medium

Your task is to design and implement a data structure for a Least Recently Used (LRU) cache. The cache should support the following operations:

  • get(key): Retrieve the value of the key if it exists in the cache, otherwise return -1.
  • put(key, value): Insert or update the value of the key. If the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

In this context, used means any access or modification of a key. The least recently used (LRU) item is the key that has not been accessed or updated for the longest time. When the cache is full, this item is removed to make space for new entries.

Example 1

Input
l = LRUCache(1)
l.put(1, 1)
l.put(1, 2)
l.get(1)
Output
[2]
Explanation:
  1. Initialize cache with capacity 2.
  2. put(1, 1) -> Cache: {1:1}
  3. put(1, 2) -> Cache: {1:2}
  4. get(1) -> Returns 2.

Example 2

Input
l = LRUCache(2)
l.put(1, 1)
l.put(2, 2)
l.get(2)
l.get(1)
l.put(3, 3)
l.get(2)
Output
[2, 1, -1]
Explanation:
  1. Initialize cache with capacity 2.
  2. put(1, 1) -> Cache: {1:1}
  3. put(2, 2) -> Cache: {1:1, 2:2}
  4. get(2) -> Returns 2
  5. get(1) -> Returns 1
  6. put(3, 3) -> Capacity is 2. LRU key 2 is evicted. Cache: {1:1, 3:3}
  7. get(2) -> Returns -1 (not found)
Loading...
Case 1Case 2
Input
l = LRUCache(1)
l.put(1, 1)
l.put(1, 2)
l.get(1)
Output
[2]
🤖

Hello! I am your ✨ AI assistant. I can provide you hints, explanations, give feedback on your code, and more. Just ask me anything related to the problem you're working on!