LoggerRateLimiter [source code]

public class LoggerRateLimiter {
    public Map<String, Integer> map;


    /** Initialize your data structure here. */
    public LoggerRateLimiter() {
        map = new HashMap<String, Integer>();
    }

    /** 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) {
        Integer lastTime = map.get(message);
        if (lastTime == null) {
            map.put(message, timestamp);
            return true;
        }
        if (timestamp - lastTime < 10) return false;
        map.put(message, timestamp);
        return true;
    }
}

/**
 * Your LoggerRateLimiter object will be instantiated and called as such:
 * LoggerRateLimiter obj = new LoggerRateLimiter();
 * boolean param_1 = obj.shouldPrintMessage(timestamp,message);
 */

这个问题总体来说还是很简单的, 秒杀级别的题目, 速度是160ms, 75%;

这个题目可以看到的一个趋势是, hashmap 一个很常见的是用法就是用来保存历史信息, 就好像在2sum 里面的一样, 也是这样;

类似于我们之前常说的 stream 算法的角度来看, 很多时候就要用类似 hashmap 这样的技术来完成一个历史信息的保存和支出, 来保证stream 在进行到后面某一个位置的时候也始终可以 access以前的信息;

最优算法是140ms, 不过代码其实也差不多, 不折腾了.

Problem Description

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:

LoggerRateLimiter logger = new LoggerRateLimiter();  

// logging string "foo" at timestamp 1  
logger.shouldPrintMessage(1, "foo"); returns true;   

// logging string "bar" at timestamp 2  
logger.shouldPrintMessage(2,"bar"); returns true;  

// logging string "foo" at timestamp 3  
logger.shouldPrintMessage(3,"foo"); returns false;  

// logging string "bar" at timestamp 8  
logger.shouldPrintMessage(8,"bar"); returns false;  

// logging string "foo" at timestamp 10  
logger.shouldPrintMessage(10,"foo"); returns false;  

// logging string "foo" at timestamp 11  
logger.shouldPrintMessage(11,"foo"); returns true;

Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.

Hide Company Tags Google
Hide Tags Hash Table Design
Hide Similar Problems (M) Design Hit Counter