Reservoir sampling: один равномерный элемент из потока
Опишите алгоритм reservoir sampling для одного элемента из потока и объясните, почему каждый увиденный элемент выбирается с одинаковой вероятностью.
Ответьте как на собеседовании
Ответьте вслух или запишите короткие тезисы. Поле необязательно — разбор откроется после попытки.