February 21st, 2007

moose, transparent

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

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

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

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

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

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

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

moose, transparent

мимоходом

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

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