Design Hit Counter - Thiết kế bộ đếm lượt truy cập 5 phút

Thiết kế bộ đếm lượt truy cập (hit counter) đếm số hit trong 5 phút (300 giây) qua. Hàm hit(timestamp) ghi nhận hit, getHits(timestamp) trả về số hit trong 300 giây gần nhất. Timestamp đơn vị giây, tăng dần.

Giải thuật (Circular Buffer / Mảng vòng)

Sử dụng 2 mảng kích thước 300: time[] lưu timestamp, hits[] lưu số lượng hit tại bucket đó. Index = timestamp % 300. Khi ghi hit, nếu timestamp khác bucket cũ thì reset count = 1, ngược lại cộng dồn. Khi truy vấn, duyệt 300 bucket, cộng các bucket có timestamp - time[i] < 300.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class HitCounter {
public:
    vector<int> time;
    vector<int> hits;

    HitCounter() {
        time = vector<int>(300);
        hits = vector<int>(300);
    }

    void hit(int timestamp) {
        int idx = timestamp % 300;
        if (time[idx] != timestamp) {
            time[idx] = timestamp;
            hits[idx] = 1;
        } else {
            hits[idx]++;
        }
    }

    int getHits(int timestamp) {
        int ret = 0;
        for (int i = 0; i < 300; i++)
            if (timestamp - time[i] < 300)
                ret += hits[i];
        return ret;
    }
};

int main() {
    HitCounter ob;
    ob.hit(1); ob.hit(2); ob.hit(3);
    cout << ob.getHits(4) << endl;   // 3
    ob.hit(300);
    cout << ob.getHits(300) << endl; // 4
    cout << ob.getHits(301);         // 3
    return 0;
}

Đầu vào

ob.hit(1); ob.hit(2); ob.hit(3); ob.getHits(4); ob.hit(300); ob.getHits(300); ob.getHits(301);

Đầu ra

3 4 3