Clean C++ solution


  • 0
    J

    Overview
    A simple solution for this problem is to use a hash table. In the solution below (C++) we use a std::unordered_map<std::string, int> as a private member variable. This lets us query when we last printed a message - an easy mistake to make on this problem is to update the hash table every time a message comes in, but reading the question carefully indicates that we only care about the time since we last returned true.

    C++ solution

    class Logger {
    public:
        /** Initialize your data structure here. */
        Logger() {
            
        }
        
        /** 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. */
        bool shouldPrintMessage(int timestamp, string message) {
    
            if(last_seen.count(message) != 0){
                if ((timestamp - last_seen[message]) < timeout){
                    return false;
                }
            }
            
            last_seen[message] = timestamp;
    
            return true;
        }
    private:
        std::unordered_map<string, int> last_seen;
        int timeout = 10;
    };
    

    We check our hashtable to see if an incoming message has already been seen before. Remember to use built-in functions where possible - you can use the count() method to check if an element exists in the map. You could also use find(), but the performance will be similar and count() is arguably more readable.

    There are three options:

    1. This message is new, so return true and insert the value into the map
    2. This message is old and we haven't printed it within 10 seconds, so return true and insert the value
    3. Otherwise we've seen this message before, but we printed it less than 10 seconds ago so we return false

    Complexity
    Space complexity: O(n) for n log messages.
    Time complexity: O(1) as insert/retrieve from the hash table is ammortised constant.

    Notes
    This code handles all edge cases that are present in the tests provided, but an extension could consider e.g. negative timestamps, empty messages. A further extension could use a smarter cache scheme to remove infrequently seen messages.


Log in to reply
 

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