witfame

• Problem: Implement an LRU (Least Recently Used) cache. An LRU cache is a data structure that stores a limited number of items. When the cache is full, the least recently used item is evicted to make room for a new item.
• Requirements:
  • Implement the LRU cache as a class with get(key) and put(key, value) methods.
  • get(key): Returns the value associated with the key if it exists in the cache, otherwise returns -1.
  • put(key, value): Updates the value of the key if the key exists, otherwise adds the key-value pair to the cache. If the cache is full, evicts the least recently used item before adding the new item.
  • The cache should have a fixed capacity.
  • Optimize for both get and put operations (ideally O(1) average time complexity).
• Solution (using collections.OrderedDict):

Python

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        value = self.cache.pop(key)  # Move key to end (most recently used)
        self.cache[key] = value
        return value

    def put(self, key, value):
        if key in self.cache:
            self.cache.pop(key)  # Update and move to end
        elif len(self.cache) == self.capacity:
            self.cache.popitem(last=False)  # Evict LRU (first item)
        self.cache[key] = value

# Example usage:
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))   # Output: 1
cache.put(3, 3)       # Evicts key 2
print(cache.get(2))   # Output: -1
cache.put(1, 4)       # Updates key 1
print(cache.get(1))   # Output: 4

• Explanation: OrderedDict maintains the order of insertion, making it easy to track the least recently used item. pop(key) removes the item and returns the value, and then we re-insert it to make it the most recently used. popitem(last=False) removes and returns the first item (LRU).