Clean Python Solution O(1)

  • 0

    It took me a while to wipe out all the bugs. List operation was learned from Linux kernel list operation MACROs which have a dummy node acting as both head and tail and have no if-else condition when inserting, deleting and appending.

    class List(object):
        def delete(elem):
   = elem.prev
   = elem.prev = None
            return elem
        def move(elem, newPrev, newNext):
            elem.prev = newPrev
   = newNext
   = elem
            newNext.prev = elem
        def append(head, elem):
            List.move(elem, head.prev, head)
        def insertAfter(head, elem):
            List.move(elem, head,
        def isEmpty(head):
            return == head.prev == head
        def initHead(head):
            head.prev = = head
    class FreqNode(object):
        def __init__(self, freq):
            self.prev = = None
            self.freq = freq
            self.head = Cache(-1, -1, self)
        def popCache(self):
            head = self.head
            ret = List.delete(
            if List.isEmpty(head):
            return ret
    class Cache(object):
        def __init__(self, key, val, freqNode):
            self.prev = = None
            self.freqNode = freqNode
            self.val = val
            self.key = key
        def increaseFreq(self):
            freqNode = self.freqNode
            newFreqNode = None
            if List.isEmpty(freqNode) or != freqNode.freq + 1:
                newFreqNode = FreqNode(self.freqNode.freq + 1)
                List.insertAfter(freqNode, newFreqNode)
                newFreqNode =
            self.freqNode = newFreqNode
            List.append(newFreqNode.head, self)
            if List.isEmpty(freqNode.head):
    class LFUCache(object):
        def __init__(self, capacity):
            self.d = {}
            self.cap = capacity
            self.head = FreqNode(-1)
        def get(self, key):
            if key not in self.d:
                return -1
            cacheNode = self.d[key]
            return cacheNode.val
        def set(self, key, value):
            if self.cap == 0:
            if key in self.d:
                cacheNode = self.d[key]
                cacheNode.val = value
                if len(self.d) >= self.cap:
                    del self.d[]
                newFreqNode = FreqNode(0)
                newCacheNode = Cache(key, value, newFreqNode)
                List.append(newFreqNode.head, newCacheNode)
                List.insertAfter(self.head, newFreqNode)
                self.d[key] = newCacheNode

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.