PYTHON
Implement an LRU Cache with OrderedDict
Create a simple Least Recently Used (LRU) cache in Python using `collections.OrderedDict` for efficient data retrieval and memory management in web applications.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: str) -> any:
if key not in self.cache:
return -1 # Or raise KeyError
self.cache.move_to_end(key) # Mark as recently used
return self.cache[key]
def put(self, key: str, value: any) -> None:
if key in self.cache:
self.cache.move_to_end(key) # Mark as recently used
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # Remove LRU item (first item)
# Example Usage:
lru_cache = LRUCache(3)
lru_cache.put("a", 1)
lru_cache.put("b", 2)
lru_cache.put("c", 3)
# Cache: {'a': 1, 'b': 2, 'c': 3}
lru_cache.get("b") # Access 'b', it moves to end
# Cache: {'a': 1, 'c': 3, 'b': 2}
lru_cache.put("d", 4) # Add 'd', 'a' is least recently used and removed
# Cache: {'c': 3, 'b': 2, 'd': 4}
How it works: This LRU (Least Recently Used) cache implementation uses Python's `collections.OrderedDict` to maintain insertion order while also providing efficient key lookups. When an item is accessed (`get`), it's moved to the end to mark it as most recently used. When a new item is added (`put`) and the cache exceeds its capacity, the item at the beginning (least recently used) is removed. This pattern is crucial for optimizing performance in web applications by storing frequently accessed data in memory and intelligently managing its eviction.