这更像是一个设计问题,但我只是想知道是否有人对这个问题有任何想法。
在一次面试中,我被要求设计 2 个方法。
hit();
getNumHits();
hit()
每次用户向服务器发出请求时调用,getNumHits()
返回最后一分钟的点击次数。
有什么想法吗?
更新:
我知道这是一个副本
Implementation of a "hits in last [second/minute/hour]" data structure
但我在理解 C++ 代码时遇到了一些困难,想知道我们是否可以获得 Java 版本的答案!
最佳答案
您要寻找的核心是保留最后一分钟内所有匹配项的列表。使用 LinkedList
可以实现快速的 removeFirst()
。
class HitCounter {
// My most recent list - only the last minute is retained.
LinkedList<Long> hitList = new LinkedList<>();
private static final long OneMinute = 1000L * 60L;
public void hit() {
// Track the hit.
hitList.add(System.currentTimeMillis());
// Always clean up.
cleanup();
}
public int hitCount() {
// Make sure we are clean.
cleanup();
return hitList.size();
}
private void cleanup() {
// Eat all stale hits.
while (hitList.getFirst() < System.currentTimeMillis() - OneMinute) {
hitList.removeFirst();
}
}
}
但是,如果您的命中非常快,并且您怀疑保留所有命中的所有时间是否有效,您可以使用桶系统进行量化。在这里,我每一秒都在计数。很明显,你可能会在一秒钟内被击中多少次。
class HitCounter {
// One bucket - keeps track of how many hits since the start time.
private class Bucket {
// Probably should use an atomic.
int count;
// The time this bucket was started.
long started = System.currentTimeMillis();
}
// My most recent list - only the last minute is retained.
LinkedList<Bucket> hitList = new LinkedList<>();
private static final long OneSecond = 1000L;
private static final long OneMinute = OneSecond * 60L;
public void hit() {
// Grab the hit time.
long now = System.currentTimeMillis();
// Normally goes in the last bucket.
Bucket bucket = hitList.size() > 0 ? hitList.getLast() : null;
// Time for new bucket?
if (bucket == null || now > bucket.started + OneSecond) {
// Yup!
hitList.add(bucket = new Bucket());
}
// Track the hit.
bucket.count++;
// Always clean up.
cleanup();
}
public int hitCount() {
// Make sure we are clean.
cleanup();
// Add up all the bucket counts.
int total = 0;
for (Bucket bucket : hitList) {
total += bucket.count;
}
return total;
}
private void cleanup() {
// Eat all stale hits.
while (hitList.size() > 0 && hitList.getFirst().started < System.currentTimeMillis() - OneMinute - OneSecond) {
hitList.removeFirst();
}
}
}
public void test() throws InterruptedException {
HitCounter hitList = new HitCounter();
for (int i = 0; i < 90; i++) {
hitList.hit();
System.out.println(i + " - " + hitList.hitCount());
Thread.sleep(1000);
}
}
关于Java:在最后一分钟实现 Hit() 和 getNumHits(),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35319150/