First submission, accepted python code using double-linked-list and OrderedDict

  • 0

    This is my first submission, please bare with me for any problem. Having learned a lot from the discussion and decide, maybe as a new year resolution, I should contribute if I can. Didn't find python solution in the discussion, so I'd like to share mine. The idea is similar to many existing solutions that use a double linked list to track the frequencies of each item and put all items that have the same frequency into one node. Inside that node, use collections.OrderedDict to track the ordering of items be added (so we know which item to be popped out if need to remove).

    Defined a move_forward() helper function for either adding new item or setting and getting existing items from the cache, as all these operations will adds 1 frequency of an item.

    Please let me know if you have any question and suggestion. Thanks.

    class LFUNode(object):
        def __init__(self, frequency):
            self.frequency = frequency
            # use ordered dict for removing the first item added
            self.od = collections.OrderedDict()
            self.pre, = None, None
    class LFUCache(object):
        def __init__(self, capacity):
            :type capacity: int
            self.cap = capacity
            self.size = 0
   = {}
            self.head = LFUNode(0)
            self.tail = LFUNode(0)
   = self.tail
            self.tail.pre = self.head
        def get(self, key):
            :type key: int
            :rtype: int
            if key not in
                return -1
            node =[key]
            res = node.od[key]
            self.move_forward(node, key, res)
            return res
        def pop_item(self):
            node = self.tail
            while len(node.pre.od) == 0:
                # remove the pre node that has no item saved on that
                node.pre = node.pre.pre
       = node
            (k, v) = node.pre.od.popitem(last = False)
        def move_forward(self, node, key, value):
            # Add new item 
            if node.pre == self.head or node.pre.frequency != node.frequency + 1:
                pre_node = LFUNode(node.frequency + 1)
                pre_node.pre = node.pre
                node.pre = pre_node
       = pre_node
       = node
                pre_node = node.pre
            pre_node.od[key] = value
  [key] = pre_node
        def set(self, key, value):
            :type key: int
            :type value: int
            :rtype: void
            if self.cap == 0:
            if key in
                node =[key]
                self.move_forward(node, key, value)
                if self.size == self.cap:
                    self.size += 1
                self.move_forward(self.tail, key, value)

Log in to reply

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