PYTHON
Implement Basic LRU Cache
Build a simple Least Recently Used (LRU) cache in Python using collections.OrderedDict to efficiently manage a fixed-size cache of frequently accessed items.
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 # Not found
# Move the accessed item to the end (most recently used)
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key: str, value: any) -> None:
if key in self.cache:
self.cache.pop(key) # Remove to update position
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # Remove LRU item
self.cache[key] = value # Add or update as MRU
# Example Usage
lru_cache = LRUCache(capacity=2)
lru_cache.put('k1', 'v1')
lru_cache.put('k2', 'v2')
print(f"Cache after k1, k2: {lru_cache.cache}") # OrderedDict([('k1', 'v1'), ('k2', 'v2')])
print(f"Get k1: {lru_cache.get('k1')}") # k1 becomes MRU
print(f"Cache after get k1: {lru_cache.cache}") # OrderedDict([('k2', 'v2'), ('k1', 'v1')])
lru_cache.put('k3', 'v3') # k2 is now LRU, should be removed
print(f"Cache after put k3: {lru_cache.cache}") # OrderedDict([('k1', 'v1'), ('k3', 'v3')])
print(f"Get k2: {lru_cache.get('k2')}") # -1
How it works: An LRU (Least Recently Used) cache evicts the item that has not been used for the longest time when the cache reaches its capacity. Python's `collections.OrderedDict` is perfect for this, as it remembers the order in which items were inserted. By moving accessed or newly added items to the end (most recently used) and removing items from the beginning (least recently used) when the cache is full, we efficiently implement the LRU policy.