PYTHON
Implement a Basic LRU Cache with `OrderedDict`
Create a simple Least Recently Used (LRU) cache in Python using `collections.OrderedDict` to manage memory and improve performance by storing and retrieving frequently accessed data.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
# Move the accessed item to the end to mark as recently used
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
# If key exists, update value and move to end
self.cache[key] = value
self.cache.move_to_end(key)
else:
# If cache is full, remove the least recently used item (first item)
if len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # Remove FIFO (least recently used)
self.cache[key] = value
self.cache.move_to_end(key) # Add new item to end (most recently used)
# Example Usage:
lru_cache = LRUCache(3)
lru_cache.put(1, 10) # Cache: {1: 10}
lru_cache.put(2, 20) # Cache: {1: 10, 2: 20}
lru_cache.put(3, 30) # Cache: {1: 10, 2: 20, 3: 30}
print(f"Cache after 3 puts: {list(lru_cache.cache.items())}")
print(f"Get 2: {lru_cache.get(2)}") # Cache: {1: 10, 3: 30, 2: 20} (2 is now MRU)
print(f"Cache after get 2: {list(lru_cache.cache.items())}")
lru_cache.put(4, 40) # Cache is full, 1 is LRU, remove 1. Cache: {3: 30, 2: 20, 4: 40}
print(f"Cache after put 4 (eviction): {list(lru_cache.cache.items())}")
print(f"Get 1: {lru_cache.get(1)}") # Expected: -1 (1 was evicted)
print(f"Cache after get 1: {list(lru_cache.cache.items())}")
How it works: A Least Recently Used (LRU) cache discards the least recently used items first when the cache reaches its capacity. Python's `collections.OrderedDict` is ideal for implementing an LRU cache because it remembers the order in which items were inserted. When an item is accessed (`get`), `move_to_end(key)` repositions it to the end (most recently used). When a new item is added (`put`) and the cache is full, `popitem(last=False)` removes the item at the beginning (least recently used), maintaining the LRU policy.