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

[crypto5]

Почему в угадайку? Вполне логичный ответ.

Ну и другие вопросы из той же серии примерно. Кто соберется - имейте ввиду.

Вполне логичный, только например если в датасете окажется скажем 20 запросов с разбросом в 50%, но их общая share будет меньше скажем 0.1%, такой подход уже будет работать с большой погрешностью, и он не выдаст именно 10 самых частых запросов.

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

Помоему вполне вероятен в плане запросов к яндексу. Я даже думаю где то так и есть.

Не поясните более детально?

У меня нету никаких данных, чисто интуиция. Но вы можете поиграться с данными: http://jeffhuang.com/search_query_logs.html ))

[Berlaga]

У меня нету никаких данных, чисто интуиция.

Я где-то так и думал, спасибо.

[crypto5]

Ну а ваши какие мысли по этому поводу? Почему вы думаете что мой вариант неправилен, если так действительно думаете?

[Berlaga]

Кстати, только сейчас заметил, что они перебрались в ПА. Я еще в Burlingame ездил, они там тогда были.

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

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

1) Распараллелить на N процессов - обычно речь идет о часовых лог файлах на тысячах серверов, которые
а) можно обрабатывать прямо "с" сервера (пока данный часовой лог файл не "украл" log harverster
b) если уже украл, то тогда "с" log harversting serverа.
При этом клиентов с разных клиентских машин может быть до фига (в нашем случае N)

2) Для каждого из процессов: пропарсить методом external sorting, так что бы на выходе был мап, где ключем был запрос, значением количество появлений
2а) Возможно (!) предварительно пропарсить файлы, так что бы убрать лишние данные

Результатом этого шага будет некоторое количество дайтасетов с уникальными данными в каждом из которых будет мап {url, num)

3) произвести "склейку" со всех клиентских машин / процессов занятых в обработке, так что бы получить "склеенный" хаш, в котором количество попаданий одинакового URL сложится с разных клиентов. Возможно так же сделать методом экстернал сортинга.

Почему нельзя отобрать из предыдущих дайтасетов топ 10 записей и склеивать только их. Мы может оказаться с ситуации, когда на 11 позиции будте запрос "z" количеством 1, ноз ато везде. таким образом мы отберем запрос "а" количеством 100, но упустим "z". Но "а" есть только в одном месте, а "z" везде. Таким образом прийдется склеивать все.

На выходе будет какое-то количество уникалных мапов {url, num}

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

[Berlaga]

Ну а ваши какие мысли по этому поводу? Почему вы думаете что мой вариант неправилен, если так действительно думаете?

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

[crypto5]

Ну а ваши какие мысли по этому поводу? Почему вы думаете что мой вариант неправилен, если так действительно думаете?

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

Всмысле, это как раз предложенное мной решение выдает абсолютно точный и достоверный результат, а ваше зависит от множества параметров.

[Интеррапт]

кошелек у меня тоже толстый

Буржуй.

[Berlaga]

Ну а ваши какие мысли по этому поводу? Почему вы думаете что мой вариант неправилен, если так действительно думаете?

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

Всмысле, это как раз предложенное мной решение выдает абсолютно точный и достоверный результат, а ваше зависит от множества параметров.

Пардон, я не о решении, а о вашем предположении "если в датасете окажется скажем 20 запросов с разбросом в 50%, но их общая share будет меньше скажем 0.1%, такой подход уже будет работать с большой погрешностью, и он не выдаст именно 10 самых частых запросов." Мне такой расклад не кажется сколько нибудь вероятным на реальных данных.

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

Добавил небольшие лингвестические добавки и пояснения выше.

[Boriskin]

Задача не очень точно поставлена...

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

+1. Имхо, решается с помощью оптимизированных так или иначе префиксных деревьев (что Стенкинг выдал), причем в реале, я так понимаю, конторы типа гугла/яндекса/бинга скорее всего формируют и апдейтят это дерево в реальном времени с каким то отсечением по времени.

Хорошая задача, в биоинформатике при анализе последовательностей ДНК во всю используется.

ЗЫ Я бы сходу не написал, смог бы только рассказать обшие принципы.

[mr boombastic]

Народ кому не влом сходите - расскажите. Интересно интервью на русском можно будет проходить?

Я там был 3 года назад, интервью на русском. Провалил. Жалею до сих пор.

Жалете о чем? Что провалили или что пошли туда?

Что провалил, конечно! Мне у них очень понравилось.

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

MRU cache.

[mr boombastic]

neuzheli nikto ne znal???

[Boriskin]

При чем тут MRU? Нужно не последние, а наиболее популярные...

[Сабина]

Народ кому не влом сходите - расскажите. Интересно интервью на русском можно будет проходить?

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

Руки вчера не дошли уточнить sorry

Полный пост такой

Набираем С++ девелоперов в Yandex Labs (Palo Alto, CA), развивать поисковые технологии компании Яндекс . Если интересно - напишите мне сообщение. Спасибо.

Писать ему.

[crypto5]

При чем тут MRU? Нужно не последние, а наиболее популярные...

Но MFU кеш нормальное решение - лучше семплингов и кластеризаций

[Boriskin]

MFU эт не MRU, хотя если опечатка - тогда другое дело.

Опять же, если сие использовать для request completion/suggestions - то кэш не лечит.

[mr boombastic]

da vsegda putausj v etih abbreviations. lru, mru, mfu.

linked list + hash table koroche.

[crypto5]

da vsegda putausj v etih abbreviations. lru, mru, mfu.

linked list + hash table koroche.

Список и таблица это LRU обычно. Не совсем понятно как так можно MFU запрограммировать.

[oshibka_residenta]

da vsegda putausj v etih abbreviations. lru, mru, mfu.

linked list + hash table koroche.

Проблема в том, что записей миллиард. Охренеет ваша hash table.

[crypto5]

da vsegda putausj v etih abbreviations. lru, mru, mfu.

linked list + hash table koroche.

Проблема в том, что записей миллиард. Охренеет ваша hash table.

Ну суть кеша ведь не в том что бы в нем абсолютно все записи держать.

[stenking]

Все мимо, связка ключей у меня большая - квартира два ключа, спортзал местный, велосипед, машина, телефон тоже большой нексус5, кошелек у меня тоже толстый, поэтому что бы не забивать карманы барахлом я с сумкой через плечо все время хожу, где это все и держу ))
А в кармане держу бейдж иногда ))

Всё равно логика на моей стороне. Только женатые люди могут себе позволить мen's рurse а учитывая что вы работаете в гугле то логично было предположить что вы неженатый гик

[mr boombastic]

da vsegda putausj v etih abbreviations. lru, mru, mfu.

linked list + hash table koroche.

Проблема в том, что записей миллиард. Охренеет ваша hash table.

Ну суть кеша ведь не в том что бы в нем абсолютно все записи держать.

max capacity = 10. a elementy dvigat'/udalyat' po opredelennym pravilam

[dotcom]

Писать ему.

Крут мужик. Что он в Яндексе делает после академии Playboy'я?

[dotcom]

+1. Имхо, решается с помощью оптимизированных так или иначе префиксных деревьев (что Стенкинг выдал), причем в реале, я так понимаю, конторы типа гугла/яндекса/бинга скорее всего формируют и апдейтят это дерево в реальном времени с каким то отсечением по времени.

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