O(1) per query solution, keeps part of messages, no blocking, linkedList + WeakValueDictionary


  • 1
    T

    I noticed folks are using heap or deque to achieve "storing only part of the message". But when doing priorityQueue.pop() or deque.popleft(), the pop itself blocks the handling of new incoming logs, and there could be a lot older logs to pop(). For data stream caching in the real world, it became a bottleneck of the design.

    It becomes a system design optimization for data caching, check here for detailed idea of the design, The two flashlights paradox and taking advantage of Python's GC when doing data stream caching

    And below are the AC solution using doubly LL + Weak-ref hashmap solution that achieves O(1) time complexity per query, while keeping only recent logs in memory.

    Note that code below is still a prototype version of the use of weakref, in real production, you should override the methods that read/write the weakref dictionary (or weakref hashmap in Java) to ensure the behaviors.

    import weakref
    
    class DoublyLLNode(object):
        def __init__(self, timestamp, message):
            self._timeStamp = timestamp
            self._message = message
            self.nxt = None
            self.prev = None
    
    class Logger(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self._cache = weakref.WeakValueDictionary()
            self.HEAD = DoublyLLNode(0, "HEAD")
            self.TAIL = DoublyLLNode(0, "TAIL")
            self.HEAD.nxt = self.TAIL
            self.TAIL.prev = self.HEAD
    
        def shouldPrintMessage(self, timestamp, message):
            """
            Returns true if the message should be printed in the given timestamp, otherwise returns false.
            If this method returns false, the message will not be printed.
            The timestamp is in seconds granularity.
            :type timestamp: int
            :type message: str
            :rtype: bool
            """
            
            if message in self._cache:
                    tempNode = self._cache[message]
                    if timestamp - tempNode._timeStamp >= 10:
                        self._resetHead(tempNode)
                        node = DoublyLLNode(timestamp, message)
                        self._addNodeToTail(node)
                        return True
                    else:
                        return False                                    
            else:
                node = DoublyLLNode(timestamp, message)
                self._addNodeToTail(node)
                return True
            
        def _resetHead(self, node):
            """
            : method that sets new head of the doubly ll to node.nxt of input node.
            : type node: DoublyLLNode
            : rtype    : void
            """
            self.HEAD.nxt = node.nxt
            node.nxt.prev = self.HEAD
        
        def _addNodeToTail(self, node):
            """
            : method that add input node to the end of the doubly ll.
            : type node: DoublyLLNode
            : rtype    : void
            """
            self.TAIL.prev.nxt = node
            node.prev = self.TAIL.prev
            self.TAIL.prev = node
            node.nxt = self.TAIL
            self._cache[node._message] = node
            
    
    # Your Logger object will be instantiated and called as such:
    # obj = Logger()
    # param_1 = obj.shouldPrintMessage(timestamp,message)
    

Log in to reply
 

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