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

[avva]

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

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

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

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

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

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

Comments

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

[filpp.livejournal.com]

.

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

[avva.livejournal.com]

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

[ob-ivan.livejournal.com]

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

[jerom.livejournal.com]

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

[avva.livejournal.com]

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

Классика

[(Anonymous)]

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

Re: Классика

[avva.livejournal.com]

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

[danwinter.livejournal.com]

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

[avva.livejournal.com]

Все верно.

[unbe.livejournal.com]

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

[avva.livejournal.com]

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

[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;

[avva.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) Знакомый решил ?

[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

[vitus_wagner]

По-моему вполне для собеседования задачка. Знание правильного ответа свидетельствует о том, что человек читал хотя бы одну классическую книжку по программированию (например, в "The Unix Programming Environment" Кернигана и Пайка этот алгоритм разбирается) и может при необходимости вспомнить прочитанное.

[avva.livejournal.com]

Ну вот я читал Кернигана и Пайка, но этот алгоритм оттуда совершенно не помнил. Правда, решил сам, когда мне знакомый рассказал ее. Но тем не менее.

[0qwerty0.livejournal.com]

int size = 1;
Element result = getnext();
if(result == EOF) throw "hey you! no cheating!";

for(Element next = result; next != EOF; next = getnext()) {
size++;
if(random()<1/size)
result = next;
}

return result;

// assuming random() returns evenly distributed random number 0..1
// btw - if we change 1/size to 1/2, it's half a gaussian. I think so...

[alaev.livejournal.com]

Тут можно занудливо заметить, что если N заранее неограничено, то O(1) памяти всё равно не хватит даже для хранения этого N. Если же оно чем-то ограничено, то задача вырождается.

Возможно, имело бы смысл условие, что длина памяти ограничена O(N), если мы знаем, что элемент потока на шаге N тоже имеет длину не больше N.

[toyvo.livejournal.com]

ага, ага я тоже подмал:) log(N) при условии что размер элемента O(log(N))

[slobin.livejournal.com]

Я эту задачку узнал из perl cookbook.

... Наша профессия не для дураков ...

[toyvo.livejournal.com]

Аааааа!!!!!!!!!!!!!!!! :)))))))))))))))))))))))))))))))))))))))))))
Клёво!:)

[toyvo.livejournal.com]

А зачем это условие: "Гарантировано, что все элементы, полученные таким образом, будут отличаться друг от друга." ?

[avva.livejournal.com]

Чтоб не надо было думать о вероятностях повторяющихся элементов.

[nikto.livejournal.com]

Полностью согласен, что задача не очень подходит для интервью (хотя, смотря на какую позицию...). Она ведь не на технологию, а на теорию вероятности. Я попытался ее решить (не смог) - а когда заглянул в комментарии, стало понятно почему. Что надо выбирать значения и хранить их в каком-то конечном буфере - это очевидно, а вот для того, чтобы сделать следующий шаг - догадаться заменять значение новым с вероятностью 1/N - для этого обязательно надо знать и помнить теорию.

[airini.livejournal.com]

Полностью согласен, что задача не очень подходит для интервью (хотя, смотря на какую позицию...). Она ведь не на технологию, а на теорию вероятности.

Технологии меняются, а теория вероятности остаётся. :)

[ilyabo.livejournal.com]

пусть поток выдает буквы ABCDE и т.д.
1. получаем A
2. получаем B, выбираем из A и B одну букву с вероятностью 1/2. Пусть это B.
3. получаем C, выбираем из B и C, причем, берем B с вероятностью 2/3, а C - 1/3. Пусть это B.
4. получаем D, выбираем из B и D, причем, берем B с вероятностью 3/4, а D - 1/4
и т.д

[kot-ivanovich.livejournal.com]

Красивая задачка, но совсем не подходящая для интервью, по-моему.
Задачка простая для того, кто хоть когда-нибудь такими вещами занимался. А подходит или нет для интервью – вопрос того, на какую позицию человека интервьюировали...

[---des---.livejournal.com]

(честно до чтения комментов) - а разве "бросание монетки" (50/50) для каждого элемента не подойдет?

[---des---.livejournal.com]

упс. Очевидно, не понял я задачи - конкретно, не понял, что функция должна возвращать только один элемент из всего потока.

[angerona.livejournal.com]

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

[ygam.livejournal.com]

Кажется, мне ее в 1999 году задали на интервью.

[egorfine.livejournal.com]

Это слишком просто. :)

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

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

Задача теоретическая и теоретически же правильный ответ существует, но интересно то, как к нему приходят или не приходят кандидаты. :)

А еще прекрасный вопрос для программистов: "зачем придумали подоконник". Удивительно небольшое количество людей отвечает правильно.

[avva.livejournal.com]

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

А второе... гм, я бы сказал, что подоконник первоначально никто не придумывал, а просто стены были намного толще, чем окна, которые в них вставлялись. Не так?

[pingva.livejournal.com]

с вероятностью 1/k назначать k-ый элемент кандидатом на возвращение, и так до конца файла.

Равновероятность элементов легко показывается рекурсивно, начиная с конца, т.е.: у последнего элемента вероятность быть выбраным -- 1/N. Соответственно, у остальных N-1 элементов она 1/(N-1), и их равновероятность ясна из ...(тут следует рекурсия)