Медиана

shkrobius — 23.04.2017 Знакомая искала работу. Она биоинформатик, живет в Силиконовой долине. На интервью ей дали задачи: придумать стратегию решения. Одна по специальности (она ее быстро решила), вторую она не решила, хотя звучит задача очень просто - и ее не взяли на работу.

Есть поток целых чисел (очень большой), надо динамически определять их медиану (или перцентили). Как это сделать?

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

http://www.cs.wustl.edu/~jain/papers/ftp/psqr.pdf
http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf
http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf

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

Положительный момент, что начинаешь по-новому ценить среднее арифметическое...

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

Странные они там люди в этой Силиконовой долине...

Оставить комментарий

Популярные посты:

• Ранее
• Архив