PYTHON
Implement a Least Recently Used (LRU) Cache
Optimize web application performance by implementing an efficient LRU cache using Python's OrderedDict to store and manage frequently accessed data.
import collections
class LRUCache:
def __init__(self, capacity: int):
self.cache = collections.OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
value = self.cache.pop(key)
self.cache[key] = value # Move to end (MRU)
return value
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.pop(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # Remove LRU item
# Example Usage:
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # returns 1
cache.put(3, 3) # LRU key 2 is evicted
print(cache.get(2)) # returns -1 (not found)
cache.put(4, 4) # LRU key 1 is evicted
print(cache.get(1)) # returns -1 (not found)
print(cache.get(3)) # returns 3
print(cache.get(4)) # returns 4
How it works: This snippet demonstrates how to implement a Least Recently Used (LRU) cache using Python's `collections.OrderedDict`. An LRU cache stores a fixed number of items and discards the least recently used item when the cache reaches its capacity. The `OrderedDict` maintains insertion order, making it efficient to move items to the end (most recently used) or remove items from the beginning (least recently used).