How do I implement LRU and LFU caching algorithms?

How do I implement LRU and LFU caching algorithms in Python?

To implement LRU (Least Recently Used) and LFU (Least Frequently Used) caching algorithms in Python, you can use data structures like dictionaries and linked lists. Would you like a code example?

Yes, please provide a code example for both algorithms.

Sure! Here's a simple implementation for LRU using collections.OrderedDict:

from collections import OrderedDict

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

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        else:
            self.cache.move_to_end(key)
            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

For LFU, you can use a combination of a dictionary and a min-heap. Would you like to see that as well?

Yes, that would be great!

Here's a basic LFU implementation:

import heapq
from collections import defaultdict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_heap = []
        self.freq_map = defaultdict(int)
        self.cache = {}

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.freq_map[key] += 1
        heapq.heappush(self.min_heap, (self.freq_map[key], key))
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.cache:
            self.cache[key] = value
            self.freq_map[key] += 1
        else:
            if len(self.cache) >= self.capacity:
                while True:
                    freq, lfu_key = heapq.heappop(self.min_heap)
                    if self.freq_map[lfu_key] == freq:
                        del self.cache[lfu_key]
                        del self.freq_map[lfu_key]
                        break
            self.cache[key] = value
            self.freq_map[key] = 1
        heapq.heappush(self.min_heap, (self.freq_map[key], key))

This should give you a good starting point!