Pick Random Number in A Big File / Infinite Stream

Cho một file chứa rất lớn số lượng số tự nhiên. Yêu cầu bạn chỉ được đọc qua file 1 lần (sequential read) và phải chọn được một số ngẫu nhiên trong đó sao cho xác suất mỗi phần tử được chọn là bằng nhau, và bằng 1/N, với N là số lượng phần tử trong file.

Lưu ý:

  • Chỉ được scan qua file 1 lần
  • Không được lưu lại mảng (vì dữ liệu rất rất lớn) vào bộ nhớ (memory lẫn external)
  • Bạn không biết trước N
  • Bạn được dùng hàm random(k) của hệ thống (trả về 1 số ngẫu nhiên trong [0, k-1]

P/s: Một cách hiểu khác là bạn được cho 1 stream of numbers, và khi stream kết thúc thì bạn phải in ra 1 số ngẫu nhiên trong các số đã nhận được.

P/s 2: Nếu cho bạn một mảng N phần tử với N biết trước, và kêu chọn một phần tử ngẫu nhiên bất kì trong N phần tử đó, thì chỉ cần gọi A[random(N)], thì xác suất mỗi phần tử được chọn sẽ bằng nhau và = 1/N - cái khó bài này là bạn không có mảng A trong bộ nhớ, và cũng không được scan file 2 lần.

Examples

stream.in
1
2
3
4
5
6
// Your File
std::ifstream infile("stream.in");
int n = 0, k;

while (infile >> k)
  n++;
  // YOUR CODE
end

// print a random number based on the list of numbers read here