05 August 2008
设计一个接收消息流及其时间戳的记录器系统。每条唯一消息最多只能每 10 秒打印一次（即在时间戳 t 打印的消息将阻止其他相同的消息在时间戳 t + 10 之前打印）。
所有消息将按时间顺序出现。多条消息可能会以相同的时间戳到达。
实现 Logger 类：
Logger() 初始化记录器对象。
bool shouldPrintMessage(int timestamp, string message) 如果消息应该在给定的时间戳中打印，则返回 true，否则返回 false。
Linked HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Logger {
public Map<String, Integer> map;
int lastSecond = 0;
/** Initialize your data structure here. */
public Logger() {
map = new java.util.LinkedHashMap<String, Integer>(100, 0.6f, true) {
protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
return lastSecond - eldest.getValue() > 10;
}
};
}
/** 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) {
lastSecond = timestamp;
if(!map.containsKey(message)||timestamp - map.get(message) >= 10){
map.put(message,timestamp);
return true;
}
return false;
}
}
Cicular buffer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Logger {
private int[] buckets;
private Set[] sets;
/** Initialize your data structure here. */
public Logger() {
buckets = new int[10];
sets = new Set[10];
for (int i = 0; i < sets.length; ++i) {
sets[i] = new HashSet<String>();
}
}
/** 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) {
int idx = timestamp % 10;
if (timestamp != buckets[idx]) {
sets[idx].clear();
buckets[idx] = timestamp;
}
for (int i = 0; i < buckets.length; ++i) {
if (timestamp - buckets[i] < 10) {
if (sets[i].contains(message)) {
return false;
}
}
}
sets[idx].add(message);
return true;
}
}