PYTHON
Implement a Simple LRU Cache with OrderedDict
Build an efficient Least Recently Used (LRU) cache in Python using `collections.OrderedDict` to manage item access and ensure proper eviction of old entries when capacity is reached.
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
# Move the accessed item to the end to mark it as 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 existing entry to update and move
elif len(self.cache) >= self.capacity:
# Pop the least recently used item (first item)
self.cache.popitem(last=False)
self.cache[key] = value # Add new item or re-add updated item at the end
# Example Usage:
cache = LRUCache(2)
cache.put("k1", 1)
cache.put("k2", 2)
print(f"Cache after k1, k2: {list(cache.cache.items())}") # [('k1', 1), ('k2', 2)]
print(f"Get k1: {cache.get('k1')}") # k1 becomes MRU
print(f"Cache after get k1: {list(cache.cache.items())}") # [('k2', 2), ('k1', 1)]
cache.put("k3", 3) # k2 is now LRU, should be evicted
print(f"Cache after k3: {list(cache.cache.items())}") # [('k1', 1), ('k3', 3)]
print(f"Get k2: {cache.get('k2')}") # Should be -1 (not found)
How it works: An LRU (Least Recently Used) cache is a cache replacement algorithm that discards the least recently used items first when the cache reaches its limit. Python's `collections.OrderedDict` is perfectly suited for implementing an LRU cache because it remembers the order in which items were inserted. When an item is accessed (`get`), we remove it and re-insert it at the end to mark it as most recently used. When a new item is added (`put`) and the cache is full, we use `popitem(last=False)` to remove the item that was added first (the least recently used), before adding the new item to the end.