Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

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

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

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

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

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

Subscribe

  • мимоходом

    "...Во-первых, один и тот же фрагмент зачастую вполне годился для двух и более разделов. Так, «Смерть пионерки» Багрицкого можно было поместить и в…

  • вопрос о медицине (израильское)

    Друзья, этот вопрос для израильтян, он про израильскую медицину. Спрашиваю не для себя, для близко знакомого хорошего человека, буду очень благодарен…

  • выдох перед сном

    Я часто укладываю спать нашего А. (год и три месяца), особенно днем. Заметил, что практически всегда, когда он засыпает, он делает один громкий…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 100 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →

  • мимоходом

    "...Во-первых, один и тот же фрагмент зачастую вполне годился для двух и более разделов. Так, «Смерть пионерки» Багрицкого можно было поместить и в…

  • вопрос о медицине (израильское)

    Друзья, этот вопрос для израильтян, он про израильскую медицину. Спрашиваю не для себя, для близко знакомого хорошего человека, буду очень благодарен…

  • выдох перед сном

    Я часто укладываю спать нашего А. (год и три месяца), особенно днем. Заметил, что практически всегда, когда он засыпает, он делает один громкий…