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


  • 0
    Z

    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, self.next = None, None
    
    class LFUCache(object):
    
        def __init__(self, capacity):
            """
            
            :type capacity: int
            """
            self.cap = capacity
            self.size = 0
            self.map = {}
            self.head = LFUNode(0)
            self.tail = LFUNode(0)
            self.head.next = self.tail
            self.tail.pre = self.head
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            if key not in self.map:
                return -1
            node = self.map[key]
            res = node.od[key]
            node.od.pop(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.pre.next = node
            (k, v) = node.pre.od.popitem(last = False)
            self.map.pop(k)
    
        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.pre.next = pre_node
                pre_node.next = node
            else:
                pre_node = node.pre
    
            pre_node.od[key] = value
            self.map[key] = pre_node
        
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            if self.cap == 0:
                return
    
            if key in self.map:
                node = self.map[key]
                node.od.pop(key)
                self.move_forward(node, key, value)
            else:
                if self.size == self.cap:
                    self.pop_item()
                else:
                    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.