You are designing a leaderboard feature that processes a continuous stream of millions of player scores in real time. The system only needs to display the top 100 highest scores at any given moment and must operate with strictly minimal memory usage ($O(k)$ auxiliary space where $k = 100$). Which data structure and strategy best satisfies these constraints?

Question

Accepted Answer

Sử dụng Min-Heap kích thước k = 100 là lựa chọn tối ưu vì phần tử ở gốc luôn là giá trị nhỏ nhất trong top 100, cho phép kiểm tra và loại bỏ phần tử nhỏ hơn trong O(log k) thời gian và O(k) bộ nhớ. Max-Heap (lựa chọn B) không hiệu quả vì phần tử ở gốc là lớn nhất nên không thể biết ngay phần tử nhỏ nhất trong top 100 để loại bỏ. Lựa chọn C vi phạm ràng buộc bộ nhớ O(k) do phải lưu toàn bộ N phần tử, còn lựa chọn D sai vì danh sách liên kết đơn không hỗ trợ tìm kiếm nhị phân ngẫu nhiên hiệu quả.

Câu hỏi hôm nay