Mini-challenge — top-K phần tử trên stream

Hệ thống streaming của một nền tảng video cần báo cáo top-10 video được xem nhiều nhất trên stream. (Muốn giới hạn trong giờ vừa qua, xoay vòng nhiều CMS theo bucket thời gian, ví dụ 60 sketch mỗi phút, và cộng các sketch khi truy vấn; CMS không tự hết hạn.) Stream đầu vào là hàng chục triệu sự kiện (videoId, timestamp) mỗi giờ, không vừa RAM nếu đếm chính xác toàn bộ. Bài toán xuất hiện ở nhiều dạng thực tế:

• Network monitoring — top-K IP gửi traffic nhiều nhất trong 1 phút (phát hiện DDoS).
• Search engine — top-K query được gõ nhiều nhất trong ngày (autocomplete ranking).
• E-commerce — top-K sản phẩm được click nhiều nhất trong giờ cao điểm (homepage widget).

Khác với HyperLogLog (chỉ trả lời "có bao nhiêu phần tử khác nhau"), bài này hỏi "phần tử nào xuất hiện nhiều nhất", nên công cụ đúng là Count-Min Sketch. Dành 20–25 phút tự implement trước khi xem gợi ý.

Đề bài

Đọc đề kỹ trước khi gõ code: gạch chân đầu vào, đầu ra và ràng buộc bộ nhớ (O(d×w + K), không lưu cả stream). Nếu bước này còn vội, ôn lại ở Đọc đề bài.

Viết ba hàm/cấu trúc:

Cấu trúc CountMinSketch(d, w)

• Input: d hàng (số hàm hash), w cột (độ rộng mỗi hàng).
• Bất biến: với mọi phần tử x, estimate(x) luôn lớn hơn hoặc bằng tần suất thực của x.

Hàm update(cms, x)

• Tăng counter của x trong tất cả d hàng của CMS.

Hàm topK(stream, K, d, w)

• Input: stream các phần tử (đọc tuần tự một lần), số nguyên K, kích thước CMS (d, w).
• Output: danh sách K phần tử có tần suất ước lượng cao nhất, theo thứ tự giảm dần.
• Ràng buộc bộ nhớ: O(d×w + K), không được lưu toàn bộ stream vào mảng.

Ví dụ: stream = [A, B, A, C, A, B, D, A, B], K = 2 → output [(A, 4), (B, 3)].