персонажи из потока

Question

этот вопрос был задан в интервью ..

предположим, что ваш компьютер читает символы один за другим из потока (вы не знаете длину потока до его окончания). Обратите внимание, что у вас есть только один символ дискового пространства (поэтому вы не можете сохранить прочитанные символы в что-то вроде сильного). Когда вы закончите чтение, вы должны вернуть символ из потока с равной вероятностью.

как подойти к этой проблеме ?? любая идея ??

есть ли способ решить это ??

Answer 1

Это один из тех приемов, которые вы либо знаете, либо не знаете:

Возьмите первый символ, с вероятностью 1/2 возьмите следующий, в противном случае оставьте первый, с вероятностью 1/3 возьмите следующий, в противном случае сохраните и т. Д.

Это работает, потому что каждый раз, когда вы выбираете n th символ с вероятностью 1 / n , или сохраняете предыдущий (который имел вероятность 1 / (n- 1) , чтобы быть там) с вероятностью (1-n) / n , и 1-n s отменить.