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

[avva]

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

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

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

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

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

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

Comments

next , собственно, не будет достаточно случайным? ;)

[filpp.livejournal.com]

.

[ob-ivan.livejournal.com]

экспоненциальное распределение?

[jerom.livejournal.com]

напрашивается ответ: хранить 1 элемент и заменять его новым с вероятность 1/N, где N - номер шага, но в тервере всегда очевидные ответы оказываются неверными, я потом подсчитаю вероятности точнее :-)

Классика

[(Anonymous)]

http://www.unix.org.ua/orelly/perl/cookbook/ch08_07.htm

[danwinter.livejournal.com]

очевидно, сохранить первое значение, а потом после каждого n-го getnext() заменять его на текущее с вероятностью 1/n. разве нет?

[unbe.livejournal.com]

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

[plakhov.livejournal.com]

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

Element ret = getnext();
assert( ret != EOF );
Element cur = ret;
int n = 1;
while ( cur != EOF )
{
if ( MakeRandomNumber(n) == 0 )
ret = cur;
cur = getnext();
++n;
}
return ret;

Re: Классика

[avva.livejournal.com]

Хихи :) спасибо.

[avva.livejournal.com]

Все верно.

[avva.livejournal.com]

Правильный ответ, да.

Re: next , собственно, не будет достаточно случайным? ;)

[avva.livejournal.com]

Перечитайте условие задачи, вы ее неправильно поняли.

[avva.livejournal.com]

Да, действительно.

[jerom.livejournal.com]

Ага, а меня испугала очевидность.

Последствия тервера в университете, где интуитивная оценка вероятности слишком часто оказывалась неверной :-)

[spartach.livejournal.com]

Изначально выбрать первый элемент. При получении n-го элемента выбираем его с вероятностью p = 1/n, иначе оставляем выбранный ранее.

[stranger-p-a.livejournal.com]

Например:

1. Пишем вспомогательную функцию ВЫБОР типа ЭЛЕМЕНТ, аргументы: c1, c2 типа ЭЛЕМНТ, n - целое
Возвращает элемент c1 с вероятностью (n - 1) / n или c2 с вероятностью 1 / n (скажем, генерит случайной число от 1 до n, если выпало n - возвращает c2, иначе - c1; если n = 1 - возвращает с2)

2. В основной функции:
d1, d2 типа элемент; n типа целое
n = 1
ПОЛУЧИТЬ ИЗ ПОТОКА В d2
d1 := d2
ПОКА НЕ EOF ДЕЛАТЬ
d1 := ВЫБОР (d1, d2, n)
ПОЛУЧИТЬ ИЗ ПОТОКА В d2
КОНЕЦ ДЕЛАТЬ

ВЕРНУТЬ d1


Обоснование:
На втором шаге у нас первый элемент с вероятностью 1/2, второй - с вероятностью 1/2
На n шаге:
Первый элемент с вероятностью 1 * (1/2) * (2/3) * ... * ((n-1)/n) = 1 / n
Второй элнмент с вероятностью (1/2) * (2/3) * ... * ((n-1)/n) = 1 / n
Третий элемент с вероятностью (1/3) * (3/4) * (4/5) * (5/6) * ... * ((n-1)/n) = 1/n
...
k-й элемент с вероятностью (1/k) * (k/(k+1)) * ((k+1)/(k+2)) * ... * ((n-1)/n) = 1/n
...
n-й элемент с вероятностью 1/n


Вопрос:
1) Куда интервьюировали ? На какую должность ?
2) Знакомый решил ?

[avva.livejournal.com]

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

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

[airini.livejournal.com]

+1. Додумалась до этого минут за 5. :)

2avva: А почему по вашему она не подходит для интервью? Мне кажется - как раз на проверку "работающей соображалки" и знаний элементарной математики, именно то, что и должны на интервью проверять...

[avva.livejournal.com]

См. ниже ответ plakhov'у.

[plakhov.livejournal.com]

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

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

[airini.livejournal.com]

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

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

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

[reut.livejournal.com]

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

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

[danwinter.livejournal.com]

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

[reut.livejournal.com]

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

[mivlad.livejournal.com]

Если интуитивно, без расчётов подходить — прочитать все элементы, откладывая каждый вместо предыдущего отложенного с вероятностью 1/n, где n — натуральный номер элемента.

Впрочем, чего тут считать… Обратная индукция на пальцах [действительно на пальцах, причём :-)] подтверждает.

не глядя в комменты

[yorool-gui.livejournal.com]

1. для потока из одного элемента - вероятность выбора этого элемента 1. Выбираем его.
2. для потока из двух элементов - выбираем второй элемент с вероятностью 1/2, а с вероятностью 1/2 оставляем первый элемент
3. для потока из 3-х - выберем третий элемент с вероятностью 1/3, а с вероятностью 2/3 - один из первых двух, полученный на шаге 2
Таким образом вероятность выбора 1-го элемента - 2/3 * 1/2 = 1/3 и то же самое для 2-го
4. из 4-х - последний - 1/4, три первых - 3/4. Из них каждый выбирается с вероятностью 1/3 как следует из шага 3. Значит вероятность выбора каждого из них - 3/4 * 1/3 = 1/4
и так далее - т.е. надо выбирать N-ный элемент с вероятностью 1/N и возвращать последний выбранный элемент при приходе EOF

А почему для интервью не подходит. Хорошая и простая задачка IMHO