Где купить качественную мужскую одежду 
Как я вызывала дух Карамзина 
Сносить поквартально 
Оружие Возмездия 
моторный голод как он есть 
Как организовать хранение на кухне 
Про душу.... 
Заявки на выход 
5 апреля 1794 года, ровно 230 лет назад, в Париже были казнены вожди якобинцев
15.04.2017 —
Собака Баскервиллей
Медиана
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
Нетривиальный алгоритм, при этом "доказательство" его работы эвристическое; я не уверен, что он "лучший" - даже не понятно в каком смысле он м.б. лучший (можно придумать уродскую последовательность, сбивающую его). Вероятно, он "лучший" для потоков, которые обычно встречаются в приложениях.
Положительный момент, что начинаешь по-новому ценить среднее арифметическое...
Отрицательный - зачем давать такие задачи на интервью? Неужели есть люди, которые могут налету придумать подобные алгоритмы? На статьях, которые я нашел, небольшое цитирование; непохоже, что такие алгоритмы широко известны специалистам.
Странные они там люди в этой Силиконовой долине...
Сохранено
|
|
</> |
Оставить комментарий
Популярные посты:
Предыдущие записи блогера :
Архив записей в блогах:
В эти дни 99 лет назад Россия заключила мир с Германией и вышла из 1-й Мировой войны. Спустя несколько месяцев, когда пала Германская империя, Брестский мир был денонсирован Советским правительством. О нем до сих пор спорят, ломают копья. Очевидно, что этот мир был необходимым условием ...
Что тут сказать? Я морально устарел для адекватного восприятия ТАКИХ условий для оператора наведения. Мне просто интересно, что происходит со всей этой электроникой и экранами, когда в современный танк попадает снаряд, срабатывает динамическая защита и все системы с экипажем остаются невре ...
Случилось страшное, нас внезапно пригласили на свадьбу! Вернее, конечно, не совсем внезапно, разговор был еще месяц назад, но только разговор, потом как то тишина и тут хоппа, о нас вспомнили и все таки позвонили напомнили, что ждут. Так вот, проблема в подарке. Что подарить? Вариант "ден ...
Мальчик детсадовского возраста ерзает на лавке в электричке и отчаянно болтает ногами. Все выдает его крайне возбужденное негодование: и сжатые маленькие кулачки, и распахнутые для слез большие глаза, и нетерпеливые короткие реплики, которыми он прерывает свою старшую спутницу. Молодая ...
Узнал удивительную вещь про Исландию: оказывается здесь на протяжении большей части XX века действовал сухой закон! Все слышали про знаменитый запрет на продажу спиртного в США - он дал нам чикагских гангстеров, таких как Аль Капоне, неофициальные наливайки "speakeasy", и много чего ещё. ...
