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:
Follow up:
What if the number of hits per second could be very large? Does your design scale?
Credits:
這道題讓我們設計一個點選計數器，能夠傳回五分鐘内的點選數，提示了有可能同一時間内有多次點選。由于操作都是按時間順序的，下一次的時間戳都會大于等于本次的時間戳，那麼最直接的方法就是用一個隊列queue，每次點選時都将目前時間戳加入queue中，然後在需要擷取點選數時，我們從隊列開頭開始看，如果開頭的時間戳在5分鐘以外了，就删掉，直到開頭的時間戳在5分鐘以内停止，然後傳回queue的元素個數即為所求的點選數，參見代碼如下：
解法一：
下面這種方法和上面的方法很像，用了一個數組儲存所有的時間戳，然後要傳回點選數時，隻需要從開頭找到第一個在5分鐘的時間戳的坐标，然後用數組總長度減去這個坐标即可，和上面的方法不同的是，這個方法不删掉之前的時間戳，缺點是會很占空間，而且越到後面效率越低，參見代碼如下：
解法二：
由于Follow up中說每秒中會有很多點選，下面這種方法就比較巧妙了，定義了兩個大小為300的一維數組times和hits，分别用來儲存時間戳和點選數，在點選函數中，将時間戳對300取餘，然後看此位置中之前儲存的時間戳和目前的時間戳是否一樣，一樣說明是同一個時間戳，那麼對應的點選數自增1，如果不一樣，說明已經過了五分鐘了，那麼将對應的點選數重置為1。那麼在傳回點選數時，我們需要周遊times數組，找出所有在5分中内的位置，然後把hits中對應位置的點選數都加起來即可，參見代碼如下：
解法三：