Generalized approach (can solve follow-ups and 460. LFU Cache): doubly linked list of doubly linked list (Python, explained)


  • 0
    A

    Doubly linked list of doubly linked list with two corresponding hash tables:
    key:keyNode, count:countNode.

    Both keyNode and countNode inherit from DoublyListNode.

    To illustrate, consider case (key:count): 'a':4, 'b':2, 'c':2, 'd':1

    The doubly linked list of doubly linked list is visualized as:

    CountNode(1) - KeyNode('d')
          |
    CountNode(2) - KeyNode('b') - KeyNode('c')
          |
    CountNode(4) - KeyNode('a')
    

    We highlight that doubly linked list of doubly linked list is a generalized approach. It can deal with follow-ups: if there are multiple maxKeys or minKeys, return the most/least recently used key instead of any key.

    For example:

    1. LFU Cache https://leetcode.com/problems/lfu-cache/

    can be solved in a similar way.

    Create or delete keyNode, countNode and update dicts properly. Details are in the comments of the code.

    class DoublyListNode(object):
        def __init__(self, count):
            self.count = count
            self.prev = None
            self.next = None
            
    class KeyNode(DoublyListNode):
        def __init__(self, count, key):
            super(KeyNode, self).__init__(count)
            self.key = key
    
    class CountNode(DoublyListNode):
        def __init__(self, count):
            super(CountNode, self).__init__(count)
            self.fakeHead = KeyNode(0, '#')
            self.fakeTail = KeyNode(0, '#')
            self.fakeHead.next = self.fakeTail
            self.fakeTail.prev = self.fakeHead
    
    class AllOne(object):
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.fakeHead = CountNode(0)
            self.fakeTail = CountNode(0)
            self.fakeHead.next = self.fakeTail
            self.fakeTail.prev = self.fakeHead
            
            self.keyNode = dict()
            self.countNode = dict()
            
        def inc(self, key):
            """
            Inserts a new key <Key> with value 1. Or increments an existing key by 1.
            :type key: str
            :rtype: void
            """
            # Depending on whether key exists, we have different newCount and oldCountNode.
            keyNodeRemoved = False
            if key in self.keyNode:
                oldKeyNode = self.keyNode[key]
                newCount = oldKeyNode.count + 1
                oldCountNode = self.countNode[oldKeyNode.count]
                self.removeNode(oldKeyNode)
                keyNodeRemoved = True
            else:
                newCount = 1
                oldCountNode = self.fakeHead
            newKeyNode = KeyNode(newCount, key)
            self.keyNode[key] = newKeyNode
            
            if newCount in self.countNode:
                self.insertNode(self.countNode[newCount].fakeHead, newKeyNode)
            # If newCount does not have a countNode, create a new CountNode.
            else:
                newCountNode = CountNode(newCount)
                self.insertNode(oldCountNode, newCountNode)
                self.insertNode(newCountNode.fakeHead, newKeyNode)
                self.countNode[newCount] = newCountNode
            
            # If a keyNode is removed and this count corresponds to no key, remove this countNode. 
            if keyNodeRemoved and oldCountNode.fakeHead.next is oldCountNode.fakeTail:
                del self.countNode[oldCountNode.count]
                self.removeNode(oldCountNode)
    
    
        def dec(self, key):
            """
            Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
            :type key: str
            :rtype: void
            """
            if key not in self.keyNode:
                return
            
            # Get newCount and oldCountNode.
            oldKeyNode = self.keyNode[key]
            newCount = oldKeyNode.count - 1
            oldCountNode = self.countNode[oldKeyNode.count]
            self.removeNode(oldKeyNode)
    
            if newCount > 0:
                newKeyNode = KeyNode(newCount, key)
                self.keyNode[key] = newKeyNode
                if newCount in self.countNode:
                    self.insertNode(self.countNode[newCount].fakeHead, newKeyNode)
                # If newCount does not have a countNode, create a new CountNode.
                else:
                    newCountNode = CountNode(newCount)
                    self.insertNode(oldCountNode.prev, newCountNode)
                    self.insertNode(newCountNode.fakeHead, newKeyNode)
                    self.countNode[newCount] = newCountNode
            else:
                del self.keyNode[key]
            
            # If a keyNode is removed and this count corresponds to no key, remove this countNode. 
            if oldCountNode.fakeHead.next is oldCountNode.fakeTail:
                del self.countNode[oldCountNode.count]
                self.removeNode(oldCountNode)
            
    
        def getMaxKey(self):
            """
            Returns one of the keys with maximal value.
            :rtype: str
            """
            if self.fakeTail.prev is self.fakeHead:
                return ''
            else:
                return self.fakeTail.prev.fakeHead.next.key
            
    
        def getMinKey(self):
            """
            Returns one of the keys with Minimal value.
            :rtype: str
            """
            if self.fakeHead.next is self.fakeTail:
                return ''
            else:
                return self.fakeHead.next.fakeHead.next.key
            
    
        def removeNode(self, node):
            node.prev.next = node.next
            node.next.prev = node.prev
            
        def insertNode(self, prevNode, node):
            nextNode = prevNode.next
            node.prev = prevNode
            node.next = nextNode
            prevNode.next = node
            nextNode.prev = node
    

Log in to reply
 

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