Яндекс Лабс в Palo Alto набирает С++ developers

[Леонид Ильич Брежнев]

А я вот в себе не уверен, между бумагой и жестокой реальностью большая разница

Крипто, давайте что бы не выдавать "своих", Вы просто примете, как факт, что ПАРТИЯ этот вопрос знает лучше Вас.
Так вот, Вы, в группе таких же как Вы (никто вас на необитаемый остров выкидывать не будет) вполне справитесь.

[dotcom]

Можно хотя бы узнать, где конкретно данные то лежат? На одном диске или на многих?

Традиционно, логи подобного плана лежат либо на самом хосте, либо если он уже log harvested, то уже на специальном dedicated server, созданном специально для хранения логов в течении какого-то времени (30 - 90 дней)

Условия задачи не говорят, если логи аггрегировали, сортировали и.т.п. Т.е. они физически могут лежать рядом с веб серверами. Nobody knows.

[crypto5]

А я вот в себе не уверен, между бумагой и жестокой реальностью большая разница

Крипто, давайте что бы не выдавать "своих", Вы просто примете, как факт, что ПАРТИЯ этот вопрос знает лучше Вас.
Так вот, Вы, в группе таких же как Вы (никто вас на необитаемый остров выкидывать не будет) вполне справитесь.

С такими фактами спорить конечно тяжело

[Леонид Ильич Брежнев]

Можно хотя бы узнать, где конкретно данные то лежат? На одном диске или на многих?

Традиционно, логи подобного плана лежат либо на самом хосте, либо если он уже log harvested, то уже на специальном dedicated server, созданном специально для хранения логов в течении какого-то времени (30 - 90 дней)

Условия задачи не говорят, если логи аггрегировали, сортировали и.т.п. Т.е. они физически могут лежать рядом с веб серверами. Nobody knows.

Я ничего не говорил про сортировку. Все что я имел в виду, это что
a) изначально лог лежал на хосте, как access.log,
б) потом через час он "рестартанулся" в новый файл access.log, и старый стал access-2014-02-14-16.log
в) а когда его "утянули" на центральное хранилище к группе таких же файлов, то в директории
.../НашСервис/2014/02/14/16/
наш файл стал лежать со своими друзьями в виде
access-<hostname>-2014-02-14-16.log

[Сабина]

A что если завтра встанет такой вопрос, ответа на который просто нету, yet.

Именно! А такие вопросы встают постоянно.

И вы думаете что люди которые не в курсе про существование НоСкл, или не могущие приткнуть его когда это нужно более эфективно разрулят такие вопросы?

А я считаю что главное соoбражает человек или нет, инструментарий вторично. Вы думаете до/без nosql такие задачи никогда не решали ?
Вы меня совсем не убедили что без знаний nosql specialist - ноль без палочки в алгоритмах поиска и не умеет работать с большими обьемами данных. B частности данный товарищ 3 года назад написал с нуля одну приблуду используемую с ad campaign bidding с использовался nearest neighborhood. Работала с real time internet траффиком, в частности одним из пользователей был Google adWords, Southern airlines, Walmart, еше дофига уже не помню.
Про не знает как пользоваться Гуглом вообше не смешно. Человек будучи Джавистом за 2 месяца освоил .NET в 2006-м, а потом Objective C в 2011 за то же время. Про всякую фигню вроде Hibernate и очередное nosql db я вообше молчу

[crypto5]

A что если завтра встанет такой вопрос, ответа на который просто нету, yet.

Именно! А такие вопросы встают постоянно.

И вы думаете что люди которые не в курсе про существование НоСкл, или не могущие приткнуть его когда это нужно более эфективно разрулят такие вопросы?

А я считаю что главное соoбражает человек или нет, инструментарий вторично. Вы думаете до/без nosql такие задачи никогда не решали ?
Вы меня совсем не убедили что без знаний nosql specialist - ноль без палочки в алгоритмах поиска и не умеет работать с большими обьемами данных. B частности данный товарищ 3 года назад написал с нуля одну приблуду используемую с ad campaign bidding с использовался nearest neighborhood. Работала с реальными масштабами, в частности одним из пользователей был Google adWords.
Про не знает как пользоваться Гуглом вообше не смешно. Человек будучи Джавистом за 2 месяца освоил .NET в 2006-м, а потом Objective C в 2011 за то же время. Про всякую фигню вроде Hibernate и очередное nosql db я вообше молчу

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

[Сабина]

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

Возможно, просто выбрал рассказать свое понимание а не просто сказать "идите к кассандре". Вот мне и интересно как это воспринимается теми кто проводит interview, на самом деле ваша реакция она в каком то смысле показательная

[crypto5]

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

Возможно, просто выбрал рассказать свое понимание а не просто сказать "идите к кассандре". Вот мне и интересно как это воспринимается теми кто проводит interview, на самом деле ваша реакция она в каком то смысле показательная

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

[Сабина]

Просто вы ведь написали "а если человек не знает что такое кассандра".

Did I ? Ну то есть имелось в виду he did not bring it up, сказал тока то что я процитировала.

[dotcom]

Я ничего не говорил про сортировку. Все что я имел в виду, это что

Это все понятно. Непонятны исходные условия. Где логи, в каком виде, структура, какой у нас есть к ним доступ.

[Леонид Ильич Брежнев]

Я ничего не говорил про сортировку. Все что я имел в виду, это что

Это все понятно. Непонятны исходные условия. Где логи, в каком виде, структура, какой у нас есть к ним доступ.

Зачем Вам все это ? Достаточно знать, что к файлам есть обычный read only access.

[crypto5]

Я ничего не говорил про сортировку. Все что я имел в виду, это что

Это все понятно. Непонятны исходные условия. Где логи, в каком виде, структура, какой у нас есть к ним доступ.

Зачем Вам все это ? Достаточно знать, что к файлам есть обычный read only access.

Зная формат и где лежат можно подобрать более удобный алгоритм

[Леонид Ильич Брежнев]

Зная формат и где лежат можно подобрать более удобный алгоритм

Ребята, не там вы имхо копаете. Ну обычный тексотовый формат access.log, построчно, начиная от даты/времени и заканчивая http кодом и лайтенси, space сепарайтед. Сам файл, уже когда harvested скорее всеге gzipped.
Лежат с разумнoй скоропстью доступа (никто разумеется не будет тянуть файлы через полмира на обработку, обработают на месте).

[dotcom]

Я ничего не говорил про сортировку. Все что я имел в виду, это что

Это все понятно. Непонятны исходные условия. Где логи, в каком виде, структура, какой у нас есть к ним доступ.

Зачем Вам все это ? Достаточно знать, что к файлам есть обычный read only access.

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

[dotcom]

Зная формат и где лежат можно подобрать более удобный алгоритм

Ребята, не там вы имхо копаете. Ну обычный тексотовый формат access.log, построчно, начиная от даты/времени и заканчивая http кодом и лайтенси, space сепарайтед. Сам файл, уже когда harvested скорее всеге gzipped.
Лежат с разумнoй скоропстью доступа (никто разумеется не будет тянуть файлы через полмира на обработку, обработают на месте).

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

[Леонид Ильич Брежнев]

Зная формат и где лежат можно подобрать более удобный алгоритм

Ребята, не там вы имхо копаете. Ну обычный тексотовый формат access.log, построчно, начиная от даты/времени и заканчивая http кодом и лайтенси, space сепарайтед. Сам файл, уже когда harvested скорее всеге gzipped.
Лежат с разумнoй скоропстью доступа (никто разумеется не будет тянуть файлы через полмира на обработку, обработают на месте).

Тогда условие задачи так и должно быть, что лог хранится в текстовом формате на HDD на одном компьютере. Просто и ясно.

А какая разница? Это что самая существенная задача? Ну можно ее обговорить.

Теперь бы узнать, сколько компьютеров могут поиметь доступ к этому файлу.

Какое-то разумное количество будут иметь удобоваримый доступ на чтение.

Могу сказать, что мне приходилось видеть приблуды, которые сидели на хостах, обрабатывая access.log в реальном времени и обмениваясь с демонстратором данными, демонстратор их склеивал и показывал прямо в консоле. Но это были довольно простые данные, типа количества 200/503, различные latency percentiles, и так далее. Но это уже было цельное решение, а не задачка на интервью (хотя основы вполне закрывались банальным интервью вопросом)

[Ljolja]

If the number of unique queries is too large to keep track of on a single machine, then the map implementation from the example above could be changed to store its entries across multiple machines (nodes). Each of the nodes will be responsible for a subset of map entries. For example, with 10 nodes setup, node #1 will hold entries with hashcode ending with 1, node #2 will hold entries with hashcode ending with 2 and so on. Of course this solution will have to carry a burden of network communications etc.

Проще взять БД кассандра, которая делает именно это ))

То есть если человек этого не будет знать он типа отстал от жизни или как ?

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

[GoncharS]

Случайно наткунлся на ветку, задача показалась интнересной – видимо давненько не тренировал голову). Я прочитал по диагонали предыдущие посты, и вроде как не увидел хорошего решения.
Я бы попробовал решать задачу следующим образом.
Полагаем что все таки ответ хочется точный (неточный можно получить модификацией точного алгоритма, но имхо – спрашивается таки точный).
Проблема – похоже что сортировка, деревья хэши и другие решения стандартными алгоримами совсем “в лоб” видимо не работают из за огромного числа записей. Чтобы это дело побороть хорошо как то ”предобработать” данные (на первом этапе, потом стратегии уже разные).
Основная идея – разбить все множество записей на группы,(посчитав кол-во записей в каждой группе), в группе содержаться неуникальные записи, но с одним хэшем, затем пробуем найти 10 записей в наиболее перспективных группах (с большим кол-вом записей), и исключить большую (надеемся) часть оставшихся групп записей из дальнейшего рассмотрения. Т.е. если мы вдруг(опять надеемся и верим что так и случится на наших данных – место для матана) найдем запись повторяющуюся N раз, то все группы записей с кол-вом записей меньшим чем N уже рассматривать не надо.
Т.е. по сути это хэш таблица, только хэш не должен стараться (в отличии от обычного(99%) подхода) получить уникальный хэш для каждой записи. А вот какай коэффициент неодинаковости записей с одним хэш-ем нам будет оптимален – опять матан.
А теперь простейший пример что приходит в голову как это на практике.
Строим структуру для хранения каунтов групп.
Массив каунтов для записей разных длин 1-255. (но это скорее пред-шаг)
Дальше – считаем хэши нескольких уровней. Т.е. в каждом элементе массива – опять массив из M элементов. М – зависит как мы хеш считаем. Т.к. как нам надо хэш считать быстро – можно брать 3-4 символа – начало, конец, середина записи. (для 3 символов из 30 – получается 30*30*30, т.е. не запредельно).
Пробегаем по записям – и заполняем этот массив – находим хэши с большим каунтом.
Дальше похоже чтоб не занимать память прийдется опять перебирать все чтоб уже записи с этим хэшем выбирать и их дальше проверять. И искать среди них наши 10 лидеров. Причем этот шаг – можно делать точно так же как предыдущий – хэш второго уровня сделать и т.д.
Я вижу что тут много за и против, есть куда улучшать – но есть ощущение что может подход стрелять при правильно расставленных костылях, причем скейлап вроде возможен.

[Mavericks2k]

Субж

А что они в америке забыли?