Есть некий поток элементов. Вызывая снова и снова функцию getnext(), вы получаете каждый раз следующий элемент из потока, и так до тех пор, пока функция не вернет EOF, что означает, что поток закончился. Гарантировано, что все элементы, полученные таким образом, будут отличаться друг от друга. Вернуться к началу потока, или получать элементы в каком-то другом порядке, кроме как один за другим с помощью getnext(), невозможно.

Известно, что поток когда-нибудь кончается, но заранее про количество элементов ничего не известно.

Требуется: написать функцию, которая, когда ее вызывают (а вызывают ее один раз), возвращает выбранный случайным образом один из элементов потока, притом у каждого из элементов потока одинаковая вероятность быть возвращенным этой функцией.

Функция должна использовать фиксированное количество памяти (иными словами, O(1) памяти).

Решение:
Перебираем весь поток по одному, параллельно храним кандидата (значение, которое мы собираемся вернуть) в переменной $result.

Каждый новый претендент может побить кандидата с вероятностью 1/m, где m - количество претендентов, уже прочитанных из потока.

Схема-код решения (на php):

function getrandom()
{
$m = 0; //thread counter
$result = null; //candidate to return
while ($current = getnext())
    {
    $m++;
    if ( 1/$m > random() ) //check if pretendent wins candidate
        $result = $current; 
    }
return $result;
}

N.B. random() — несуществующая в php функция, возвращающая случайное действительное число из интервала [0,1]