Java O(1) time O(1) space solution


  • 0
    X

    Follow up question during real interview: Can you implement it with constant space?
    Solution: Maintain a constant window using two queues and a set, where the size of these queues and set is total number of message received in the last 10 seconds. Messages older than 10 seconds are discarded.

    On average, everything incoming message requires one oldest message to be removed, assuming only one message is received per second. Thus, the average time is O(1) and space is 10 elements in each queue and set.

    class Logger {
        Set<String> set;
        Queue<String> msgQueue;
        Queue<Integer> timeQueue;
        /** Initialize your data structure here. */
        public Logger() {
            set = new HashSet<>();
            msgQueue = new LinkedList<>();
            timeQueue = new LinkedList<>();
        }
        
        /** 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. */
        public boolean shouldPrintMessage(int timestamp, String message) {
            while (!timeQueue.isEmpty() && timeQueue.peek() <= timestamp - 10)
            {
                String msg = msgQueue.poll();
                timeQueue.poll();
                set.remove(msg);
            }
            
            if (!set.contains(message))
            {
                set.add(message);
                timeQueue.offer(timestamp);
                msgQueue.offer(message);
                return true;
            }
            else
            {
                return false;
            }
        }
    }
    

Log in to reply
 

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