задачка для программистов

Знакомый рассказал, ему на интервью задали. Красивая задачка, но совсем не подходящая для интервью, по-моему.

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

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

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

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

Update: учтите, что в комментариях уже есть правильные ответы.

пацан сказал, пацан сделал

Из интервью Рамзана Кадырова: "я пехотинец Путина и защитник России, и что касается вверенного нам региона – Чечни, – в 2008 году это будет самый спокойный и самый стабильный регион России."

(по ссылке отсюда)

мимоходом

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

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

комикс (англоязычное)

Роза говорит, что это я, и она права:

из френдленты

Азбука невротика.

(фрустрированного, добавлю я)