Fixed Window Counter cơ bản

Một API giới hạn tối đa N request trong một cửa sổ thời gian. Cho danh sách timestamp (giây) của các request đến trong cùng một cửa sổ, hãy xác định mỗi request được chấp nhận (ALLOW) hay bị chặn (DENY).

Thuật toán

Duyệt request theo thứ tự đến. Đếm số request đã ALLOW. Nếu số đã chấp nhận < N thì request này ALLOW và tăng bộ đếm; ngược lại DENY.

Ví dụ

Với N=3 và 5 request: 3 cái đầu ALLOW, 2 cái sau DENY.

Định dạng đầu vào:
Dòng 1: số nguyên N (giới hạn). Dòng 2: số nguyên Q (số request). Q dòng tiếp theo: mỗi dòng 1 timestamp (giây).
Ràng buộc đầu vào:
1 ≤ N ≤ 1000; 1 ≤ Q ≤ 1000; 0 ≤ timestamp ≤ 1e9.
Định dạng đầu ra:
Q dòng, mỗi dòng in ALLOW hoặc DENY tương ứng từng request.

solution

Đề bài: [Lập trình Web & Backend] Fixed Window: Đếm request trong 1 cửa sổ

Fixed Window Counter cơ bản

Thuật toán

Ví dụ