LFU Cache

Driver Code

obj = LFUCache(capacity)
param_1 = obj.get(key)
obj.put(key,value)

Solution

Both solutions below take constant time.

Complexity

time: $O(1)$ (all operations)
space: $O(n)$

Cheating w/ Built-in OrderDict

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.dct = {}
        self.frequencies = defaultdict(OrderedDict)
        self.minf = 0
        self.cap = capacity

    def insert(self, key, freq, value):
        self.dct[key] = (freq, value)
        self.frequencies[freq][key] = value

    def get(self, key: int) -> int:
        if key not in self.dct:
            return -1
        freq, value = self.dct[key]
        # remove key from current freq group
        del self.frequencies[freq][key]
        # clean up if od is empty after removal
        if not self.frequencies[freq]:
            del self.frequencies[freq]
            # least frequency in the cache has now increased
            if freq == self.minf:
                self.minf += 1
        # key has been accessed one more time
        self.insert(key, freq + 1, value)
        return value

    def put(self, key: int, value: int) -> None:
        if key in self.dct:
            freq = self.dct[key][0]
            self.dct[key] = (freq, value)
            # update the freq and reorder the key
            self.get(key)
            return
        # full capacity, del lfu
        if self.cap == len(self.dct):
            # remove the lru from lfu group
            lfu_key, freq = self.frequencies[self.minf].popitem(last=False)
            del self.dct[lfu_key]
        self.minf = 1
        self.insert(key, 1, value)

HashMap & Doubly Linked List

REDO!!!

class ListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.freq = 1
        self.prev = None
        self.next = None


class LinkedList:
    def __init__(self):
        self.sentinel = ListNode(0, 0)
        self.sentinel.next = self.sentinel.prev = self.sentinel 
        self.size = 0

    def __len__(self):
        return self.size

    def append(self, node):
        node.next = self.sentinel.next
        node.prev = self.sentinel
        node.next.prev = node
        self.sentinel.next = node
        self.size += 1

    def pop(self, node = None):
        if self.size == 0:
            return
        if not node:
            node = self.sentinel.prev
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node


class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
        self.freq = defaultdict(LinkedList)
        self.min_freq = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        freq = node.freq
        self.freq[freq].pop(node)
        if len(self.freq[freq]) == 0:
            del self.freq[freq]
            if freq == self.min_freq:
                self.min_freq += 1
        node.freq += 1       
        self.freq[node.freq].append(node)
        self.cache[key] = node
        return node.val

    def put(self, key: int, value: int) -> None:
        if self.cap == 0:
            return
        if key in self.cache:
            self.cache[key].val = value
            self.get(key)
            return 
        if self.cap == len(self.cache):
            deleted = self.freq[self.min_freq].pop()
            del self.cache[deleted.key]
        node = ListNode(key, value)
        self.cache[key] = node
        self.freq[1].append(node)
        self.min_freq = 1