Design a hit counter which counts the number of hits received in the past 5 minutes.
Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.
It is possible that several hits arrive roughly at the same time.
Example:
HitCounter counter = new HitCounter(); // hit at timestamp 1.
counter.hit(1); // hit at timestamp 2.
counter.hit(2); // hit at timestamp 3.
counter.hit(3); // get hits at timestamp 4, should return 3.
counter.getHits(4); // hit at timestamp 300.
counter.hit(300); // get hits at timestamp 300, should return 4.
counter.getHits(300); // get hits at timestamp 301, should return 3.
counter.getHits(301);
Follow up:
What if the number of hits per second could be very large? Does your design scale?
设计一个点击计数器，能够返回五分钟内的点击数，提示了有可能同一时间内有多次点击。
解法：要求保证时间顺序，可以用一个queue将每次点击的timestamp放入queue中。getHits: 可以从queue的头开始看， 如果queue开头的时间在范围外，就poll掉。最后返回queue的size。
Java:
public class HitCounter {
private ArrayDeque<Integer> queue;
/** Initialize your data structure here. */
public HitCounter() {
queue = new ArrayDeque<Integer>();
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
queue.offer(timestamp);
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
int startTime = timestamp - 300;
while(!queue.isEmpty() && queue.peek() <= startTime) {
queue.poll();
}
return queue.size();
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
Java：
public class HitCounter {
private Hit start = new Hit(0);
private Hit tail = start;
private int count = 0;
/** Initialize your data structure here. */
public HitCounter() {
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
if (tail.timestamp == timestamp) {
tail.count ++;
count ++;
} else {
tail.next = new Hit(timestamp);
tail = tail.next;
count ++;
}
getHits(timestamp);
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
while (start.next != null && timestamp - start.next.timestamp >= 300) {
count -= start.next.count;
start.next = start.next.next;
}
if (start.next == null) tail = start;
return count;
}
}
class Hit {
int timestamp;
int count;
Hit next;
Hit(int timestamp) {
this.timestamp = timestamp;
this.count = 1;
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
Python:
# Time: O(1), amortized
# Space: O(k), k is the count of seconds. from collections import deque class HitCounter(object): def __init__(self):
"""
Initialize your data structure here.
"""
self.__k = 300
self.__dq = deque()
self.__count = 0 def hit(self, timestamp):
"""
Record a hit.
@param timestamp - The current timestamp (in seconds granularity).
:type timestamp: int
:rtype: void
"""
self.getHits(timestamp)
if self.__dq and self.__dq[-1][0] == timestamp:
self.__dq[-1][1] += 1
else:
self.__dq.append([timestamp, 1])
self.__count += 1 def getHits(self, timestamp):
"""
Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity).
:type timestamp: int
:rtype: int
"""
while self.__dq and self.__dq[0][0] <= timestamp - self.__k:
self.__count -= self.__dq.popleft()[1]
return self.__count # Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)
C++:
// Time: O(1), amortized
// Space: O(k), k is the count of seconds. class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() : count_(0) { } /** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
getHits(timestamp);
if (!dq_.empty() && dq_.back().first == timestamp) {
++dq_.back().second;
} else {
dq_.emplace_back(timestamp, 1);
}
++count_;
} /** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
while (!dq_.empty() && dq_.front().first <= timestamp - k_) {
count_ -= dq_.front().second;
dq_.pop_front();
}
return count_;
} private:
const int k_ = 300;
int count_;
deque<pair<int, int>> dq_;
}; /**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
C++:
class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() {}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
q.push(timestamp);
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
while (!q.empty() && timestamp - q.front() >= 300) {
q.pop();
}
return q.size();
}
private:
queue<int> q;
};
C++:
class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() {}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
v.push_back(timestamp);
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
int i, j;
for (i = 0; i < v.size(); ++i) {
if (v[i] > timestamp - 300) {
break;
}
}
return v.size() - i;
}
private:
vector<int> v;
};
C++:
class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() {
times.resize(300);
hits.resize(300);
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
int idx = timestamp % 300;
if (times[idx] != timestamp) {
times[idx] = timestamp;
hits[idx] = 1;
} else {
++hits[idx];
}
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
int res = 0;
for (int i = 0; i < 300; ++i) {
if (timestamp - times[i] < 300) {
res += hits[i];
}
}
return res;
}
private:
vector<int> times, hits;
};
类似题目：
[LeetCode] 359. Logger Rate Limiter 记录速率限制器