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

  • 1

    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:
                        node = DoublyLLNode(timestamp, message)
                        return True
                        return False                                    
                node = DoublyLLNode(timestamp, message)
                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.