Giới hạn tốc độ bằng token bucket
Cổng API của hệ thống AI nào cũng phải chặn các luồng request dồn dập để bảo vệ mô hình
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: python-basics, loops-conditionals.
Nội dung đề bài
Mô tả bài toán
Cổng API của hệ thống AI nào cũng phải chặn các luồng request dồn dập để bảo vệ mô hình phía sau. Thuật toán token bucket mô hình hoá điều đó: một xô có sức chứa hữu hạn, được nạp thêm token theo thời gian, và mỗi request tiêu tốn đúng một token.
Yêu cầu
Viết hàm token_bucket_allow(capacity, refill_rate, timestamps) trả về số request được phục vụ. Xô bắt đầu đầy với capacity token tại thời điểm 0. Sau mỗi khoảng thời gian dt giây, xô nhận thêm dt * refill_rate token nhưng không vượt quá capacity. Mỗi request ở thời điểm t chỉ được phục vụ khi xô còn ít nhất 1 token, và khi đó bị trừ đi đúng một token.
Quy ước nộp bài
Nộp hàm token_bucket_allow trong solution.py. Hệ thống gọi hàm trực tiếp và so giá trị với sai số 1e-6; không đọc stdin và không in ra stdout.
Input
- capacity: sức chứa tối đa của xô, số nguyên không âm.
- refill_rate: số token nạp thêm mỗi giây, số thực không âm.
- timestamps: danh sách thời điểm request theo giây, không giảm dần.
Output
Một số nguyên: số request được phục vụ.
Ràng buộc
- Thời điểm request không được giảm dần; nếu vi phạm thì ném ValueError.
- Nạp thêm token luôn bị chặn trần ở capacity.
- Có tối đa 20 request; mọi giá trị là số hữu tỉ nhỏ nên tính bằng số thực là đủ.
Ví dụ 1
Input
token_bucket_allow(capacity=3, refill_rate=1.0, timestamps=[0, 0.5, 1, 1, 1, 2, 3])
Output
6
Ví dụ 2
Input
token_bucket_allow(capacity=2, refill_rate=0.0, timestamps=[1, 2, 3])
Output
2
Giải thích
Với capacity = 2, refill_rate = 1.0 và timestamps = [0, 0, 0], xô đầy 2 token; hai request đầu tiêu hết token, request thứ ba bị từ chối nên kết quả là 2.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
