PYTHON
Implement a Basic LRU Cache
Optimize web application performance by implementing a basic Least Recently Used (LRU) cache using Python dictionaries and lists to store and retrieve data efficiently.
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.order = [] # Stores keys in order of usage: LRU at front, MRU at back
def get(self, key: int) -> int:
if key not in self.cache:
return -1
# Move the accessed key to the end (Most Recently Used)
self.order.remove(key) # O(N)
self.order.append(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.order.remove(key) # O(N)
elif len(self.cache) >= self.capacity:
# Remove the Least Recently Used item
lru_key = self.order.pop(0) # O(N)
del self.cache[lru_key]
self.cache[key] = value
self.order.append(key) # O(1)
# Example Usage:
lru = LRUCache(2)
lru.put(1, 1) # cache is {1: 1}
lru.put(2, 2) # cache is {1: 1, 2: 2}
print(f"Get 1: {lru.get(1)}") # returns 1; cache is {2: 2, 1: 1} (1 is now MRU)
lru.put(3, 3) # LRU key 2 is removed, 3 is added; cache is {1: 1, 3: 3}
print(f"Get 2: {lru.get(2)}") # returns -1 (not found)
lru.put(4, 4) # LRU key 1 is removed, 4 is added; cache is {3: 3, 4: 4}
print(f"Get 1: {lru.get(1)}") # returns -1 (not found)
print(f"Get 3: {lru.get(3)}") # returns 3; cache is {4: 4, 3: 3}
print(f"Get 4: {lru.get(4)}") # returns 4; cache is {3: 3, 4: 4}
How it works: This code implements a basic Least Recently Used (LRU) cache, a common caching strategy in web applications to limit memory usage and improve performance by storing frequently accessed data. It uses a dictionary (`self.cache`) for O(1) average time complexity lookups and a list (`self.order`) to maintain the usage order of keys. When an item is accessed (`get`) or added (`put`), its key is moved to the end of the `self.order` list (marking it as 'most recently used'). If the cache exceeds its capacity, the key at the beginning of `self.order` (the 'least recently used' item) is removed from both the list and the cache. This basic implementation demonstrates the core LRU concept.