unreasonably effective

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

class LinkedList:
    def __init__(self):
        self.head, self.tail = None, None

    def appendleft(self, node):
        if not self.head:
            self.head = node
            self.tail = node
            return
        
        node.next = self.head
        self.head.prev = node
        self.head = node

    def pop(self):
        node = self.tail
        if not self.tail.prev:
            # tail is the only node
            self.tail = None
            self.head = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None

        node.prev, node.next = None, None
        return node

    def remove(self, node):
        prev_node, next_node = node.prev, node.next
        if not prev_node:
            # node is head
            self.head = self.head.next
            if self.head:
                self.head.prev = None
            else:
                self.tail = None
            node.prev, node.next = None, None
            return
        
        if not next_node:
            # node is tail
            self.tail = self.tail.prev
            self.tail.next = None
            node.prev, node.next = None, None
            return

        prev_node.next = next_node
        next_node.prev = prev_node
        node.prev, node.next = None, None

    def __bool__(self):
        return self.head is not None


class LFUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.freq_map = {}
        self.lru_map = {}
        self.min_freq = 0

    def __update_key(self, node):        
        self.lru_map[node.freq].remove(node)
        if not self.lru_map[node.freq]:
            del self.lru_map[node.freq]
            if node.freq == self.min_freq:
                self.min_freq += 1

        node.freq += 1
        if node.freq not in self.lru_map:
            self.lru_map[node.freq] = LinkedList()
        self.lru_map[node.freq].appendleft(node)

    def get(self, key: int) -> int:
        if key not in self.freq_map:
            return -1
        
        node = self.freq_map[key]
        self.__update_key(node)
        return node.val

    def __evict(self):
        node = self.lru_map[self.min_freq].pop()
        if not self.lru_map[self.min_freq]:
            del self.lru_map[self.min_freq]
            self.min_freq += 1
        del self.freq_map[node.key]

    def put(self, key: int, value: int) -> None:
        if key in self.freq_map:
            node = self.freq_map[key]
            node.val = value
            self.__update_key(node)
            return node.val
        
        if len(self.freq_map) == self.cap:
            self.__evict()
        
        self.min_freq = 1
        node = ListNode(key, value, 1)
        self.freq_map[key] = node
        if 1 not in self.lru_map:
            self.lru_map[1] = LinkedList()
        self.lru_map[1].appendleft(node)


# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)