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

[avva]

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

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

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

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

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

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

Comments

[avva.livejournal.com]

В этой задаче есть "изюминка": нужно догадаться, что следует хранить один элемент в качестве текущего кандидата, которого мы выдаем, если поток в сей момент кончился. Поняв это, разобраться с тем, как менять кандидатов, легче.

Я считаю, что на интервью задачи, для решения которых необходимо найти "изюминку", неправильно - потому что то, что кандидат не догадался, практически ничего не означает. Кому-то пришло в голову, кому-то не пришло. Это все равно, что оценивать знание математики по умению решать олимпиадные задачки. Гораздо лучше давать вопросы, в которых "изюминка" позволяет сделать что-то лучше и качественнее, но и без нее, просто грамотно используя свои знания и умения, можно придти к достойному ответу.

[plakhov.livejournal.com]

Вообще зависит от должности имхо. Во многих позициях умение искать "изюминки" очень важно.

Но в этой задаче, мне кажется, этого даже не требуется. "Догадаться, что следует хранить один элемент в качестве текущего кандидата, которого мы выдаем, если поток в сей момент кончился" очень просто. Я именно с конца ее и решил. Т.е. вот мы встретили EOF, значит, надо что-то выдать, но что? Значит, есть некий Element res. Инициализируем его первым значением (потому что больше просто нечем). И он должен по каким-то правилам меняться; по каким?

[vinopivets.livejournal.com]

Я бы не назвал прогрfммистом человека, для которого бывает неожиданный EOF :)

[0qwerty0.livejournal.com]

ну ладно - непредсказуемо

[khatul.livejournal.com]

"О как внезапно кончился STDIN!" (почти © Вишневский)

[vinopivets.livejournal.com]

Что-то в этом роде...

[airini.livejournal.com]

В этой задаче есть "изюминка": нужно догадаться, что следует хранить один элемент в качестве текущего кандидата, которого мы выдаем, если поток в сей момент кончился.

Но ведь фраза условия "Функция должна использовать фиксированное количество памяти (иными словами, O(1) памяти)." уже подразумевает под собой хранение одного элемента. До этого не нужно догадываться, это условие. А дальше нужно думать, как именно хранить его так, чтобы сохранять равную вероятность.

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

[reut.livejournal.com]

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

по-моему она подозревает конечное поличество эелементов, а не один. если я еще что-то помню из того, что учила. но от конечного до одного - один шаг.

[airini.livejournal.com]

Да, некоторого конечного количества "текущих кандидатов". Пусть то будет один, два, пять или десять, но только лишь прочитав условие, программист уже знает "изюминку задачи" - "памяти меньше, чем кандидатов. Всё не сохранишь, что же делать?".

[toyvo.livejournal.com]

Там не только элемент:) Там ещё индекс:) Т.е. log(N) + размер элемента:))) И размер памяти выходит не совсем фиксированным, ну да ладно, фиг с ними:)

[danwinter.livejournal.com]

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

я как раз из доступной памяти исходил

[freedom_of_sea.livejournal.com]

я подумал , держать некий массив чисел, время от времени его поплнять, а по приходу EOF выдавать случайный элемент из них.

Оказалось (в комментах) массив может быть мощностью 1 без ущерба для случайности...

[reut.livejournal.com]

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

[mivlad.livejournal.com]

Спасибо за задачку, кстати — сдаётся мне, эта «изюминка» пригодится мне в работе. Всё таки свобода в средствах порой развращает и приводит к неоптимальным решениям :-)

[faceted-jacinth.livejournal.com]

Сдаётся мне, что на практике её можно использовать только при наличии очень надёжного аппаратного генератора случайных чисел. Вероятность выбрать первый элемент равна P(1/2)* P(2/3) * P(3/4) * ... * P(N-1/N), где P(x) - реальная вероятность получить единицу от генератора, задав ему вероятность x. Если б P(x) было бы равно х, то всё, конечно, сократилось бы, а так ошибки округления накапливаются, да и внутренние свойства псевдослучайного генератора могут вылезти.

[alexcohn.livejournal.com]

Действительно, ошибки округления быстро испортят наш алгоритм. А есть ли более устойчивый способ? Улучшится ли результат если, например, хранить 10 кандидатов?

[mivlad.livejournal.com]

А так ли уж они там неизбежны? Можно ведь без делений обойтись, просто целыми числами.

Re: Reply to your comment...

[mivlad.livejournal.com]

Попроверял на Mersenne Twister. Вроде удовлетворительная точность выходит, уж мне точно сойдёт.

[kot-ivanovich.livejournal.com]

Даже для примитивного мультипликативного генератора, который встроен в clib, свойство P(rand(n) == 0) == 1/(n-1) точное (если только не вдаваться в очень старую дискуссию Может ли мальчик дружить с девочкой? В каком смысле случайны псевдослучайные числа?). Поскольку умножения вероятностей производит Бог, а не компьютер, то опасаться ошибок округления тоже нечего. А вот с аппаратным генератором как раз могут быть проблемы: они не аккуратностью распределения славны...

Что может здесь подпортить жизнь – это имеющиеся у некоторых генераторов корреляции между i-ым и i+N-ым обращениями при каком-нибудь неожиданном N. Ну, значит, генератор должен быть хороший....

[faceted-jacinth.livejournal.com]

Вы libc имели в виду? Тогда могу всё же поспорить: там, если я правильно помню, 32битное состояние генератора, причём состояния проходятся все (и типа попадаются в выводе с равной вероятностью). Проблема в том, что при вычислении rand(3) мы никак не можем получить ровно треть состояний, дающих 0, ибо 2^32 на три не делится. Запитывание сида от таймера и многократное повторение никак не помогают. P(1/4) опять точное, а P(1/5) снова неточное.

Можно для смеху попытаться оценить эту погрешность сверху, полагая что rand(n) = rand() % n (так он и работает наверняка), где random() равновероятно выдаёт числа от 0 до 2^32 - 1. У меня получилось
P(rand(n) = 0) = (floor((N - 1)/n) + 1)/N = 1/n + (1 - 1/n - frac((N-1)/n))/N.
Вот эта правая часть (абсолютная погрешность) колеблется вокруг 0.5/N. То есть 2^-33.
Правда, я что-то не пойму, как правильно перевести абсолютную погрешность в относительную, потому что если просто оценить её сверху как 1 - (1 - 2^-33)^1000 (для тысячи элементов), то число очень маленькое получается, даже неожиданно как-то =) И для миллиона маленькое.

[kot-ivanovich.livejournal.com]

Вы libc имели в виду?

Ага. Вечно я все сокращения путаю...

полагая что rand(n) = rand() % n (так он и работает наверняка)

Ну, это надо уж очень плохо об авторах библиотеки думать.... На самом деле, с libc просто нет входа int rand(int), есть только int rand(void). (http://www.opengroup.org/onlinepubs/009695399/functions/rand.html) В тех библиотеках, где она есть, я надеюсь, что она реализована типа (псевдокод)

U32 rand(U32 limit)
{
return (rand32() * limit) >> 32;
}

[faceted-jacinth.livejournal.com]

Ыыы что это вы такое написали?
Даже если ваш компилятор зачем-то решит перемножить и int32 и uint32 как int64, так что ваша функция будет выдавать ещё что-нибудь, кроме нулей, природу-то всё равно не обманешь -- rand32 выдаёт 2^32 разных равновероятных чисел, rand(3) - три. 2^32 на три не делится. Тут разве что можно поставить проверку, что если ранд нам выдал число из последней группы остатков, то нужно скипнуть (I mean, something like

uint32 tmp;
do
{
tmp = rand();
while ((uint32)(tmp + limit) < limit)

Но как-то это к очень нетривиальной работе рандома может привести.

[kot-ivanovich.livejournal.com]

Ыыы что это вы такое написали?

Ыыы, кажется, и написал... ;)

int32 и uint32 как int64

Ну я же сказал, что это псевдокод...

природу-то всё равно не обманешь

Виноват, сонный был....

Но как-то это к очень нетривиальной работе рандома может привести

Да нет, ничего нетривиального, метод фон-Неймана называется, в любом учебнике по Монте-Карло не дальше пятой страницы...

В GSL, собственно, так и сделано:

unsigned long int
gsl_rng_uniform_int (const gsl_rng * r, unsigned long int n)
{
unsigned long int offset = r->type->min;
unsigned long int range = r->type->max - offset;
unsigned long int scale;
unsigned long int k;

if (n > range || n == 0)
{
GSL_ERROR_VAL ("invalid n, either 0 or exceeds maximum value of generator",
GSL_EINVAL, 0) ;
}

scale = range / n;

do
{
k = (((r->type->get) (r->state)) - offset) / scale;
}
while (k >= n);

return k;
}

[http://users.livejournal.com/d_m_/]

Лично я предпочитаю собеседования, где проверяют моё умение решать задачки "с изюминкой", чем знание так называемых "паттернов", всяких модных аббревиатур или библиотек.