PYTHON
Implement a Basic LRU Cache in Python
Create a simple Least Recently Used (LRU) cache using `collections.OrderedDict` to manage cached data efficiently based on access patterns.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: str) -> int:
if key not in self.cache:
return -1 # Key not found
# Move the accessed item to the end (most recently used)
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: str, value: int) -> None:
if key in self.cache:
# If key exists, update value and move to end
self.cache.move_to_end(key)
self.cache[key] = value
# If cache exceeds capacity, remove the first item (least recently used)
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
# Example usage:
lru_cache = LRUCache(2)
lru_cache.put('a', 1)
lru_cache.put('b', 2)
print(f"Cache after 'a':1, 'b':2 -> {list(lru_cache.cache.items())}")
print(f"Get 'a': {lru_cache.get('a')}") # 'a' becomes MRU
print(f"Cache state -> {list(lru_cache.cache.items())}")
lru_cache.put('c', 3) # 'b' is LRU and evicted
print(f"Cache after 'c':3 -> {list(lru_cache.cache.items())}")
print(f"Get 'b': {lru_cache.get('b')}") # returns -1
How it works: This snippet provides a basic implementation of a Least Recently Used (LRU) cache. An LRU cache stores a fixed number of items and evicts the least recently used item when the cache reaches its capacity and a new item is added. This implementation leverages Python's `collections.OrderedDict`, which remembers the order in which items were inserted. The `move_to_end()` method efficiently updates an item's recency, while `popitem(last=False)` removes the oldest (LRU) item.