Как меня не позвали в Яндекс на собеседование

В конце прошлого года один из сотрудников Яндекса нашел меня в “Моём Круге” (а где же ещё им искать сотрудников?) и, так как у меня указано в специализации “Perl-программист”, предложил рассмотреть вакансию Perl-разработчика в Яндексе. Со времен заполнения профиля в “Моём Круге” прошло достаточно много времени, я уже давно пересел на PHP и программировал на Perl’е достаточно редко и в специфичных задачах. Однако, давняя мечта работать в Яндексе в тот момент все ещё витала (и витает до сих пор) в моей голове, поэтому я решил попробовать свои силы. Но с другой стороны, туманная перспектива переезжать в Москву и увольняться с текущей работы совершенно не радовала. Не люблю я Москву. Работа у меня в моем городе очень хорошая. Нужно будет программировать на Perl. Родственники опять же, друзья. Зарплата примерно такая же (если вычесть аренду жилья).

“Поехали!” – сказал я Денису (назовем его так) и отправил ему свой E-mail. Ждать пришлось недолго.

Денис 14.11.2011

Антон, добрый день!

Мы хотим предложить вам решить следующую задачу.

Реализовать специализированный crawler, сохраняющий “фавиконки” (http://ru.wikipedia.org/wiki/Favicon) сайтов.

Входом для программы является текстовый файл, содержащий домены для обхода (по одному на строке), и название директории для сохранения результатов.

Требуется определить правильную иконку для каждого из файлов, с учетом де-факто стандартов (/favicon.ico, указание ссылки в теле документа), скачать ее, если она доступна, конвертировать в общий для всех формат (PNG, при необходимости – с альфа-каналом), и сохранить в указанной директории, под названием типа www.example.com.png.

Дополнительно: на всех этапах общения с сайтами нужно поддерживать ограничения, налагаемые их robots.txt; желательно эффективно использовать ресурсы многопроцессорного сервера.

Сделать нужно на Perl, можно использовать любые готовые общедоступные модули.

Ух! Это же то, чем я чаще всего занимаюсь на Perl – что-нибудь тащу, ворую, парсю и складываю.

Антон Терехов 14.11.2011

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

Провозился почти всё воскресенье, заставил работать, затем красиво оформил и частично переписал. Виталий предложил хорошую идею – переписать скрипт на неблокирующих сокетах, но я, немного повозившись с ними, решил плюнуть и показать Денису то, что получилось.

Антон Терехов 21.11.2011

Добрый день, Денис!

Задача была достаточно интересная, моя реализация в аттаче. Была идея переписать на неблокирующих сокетах, но не успел.
Для работы скрипта необходимо наличие модулей:
LWP::Simple – как правило, входит в дистрибутив
WWW::RobotRules – как правило, входит в дистрибутив
Imager – скорее всего, придется устанавливать. При установке необходимо обратить внимание, корректно ли установятся модули Imager::File::PNG и Imager::File::PNGWriter

Денис 21.11.2011

Антон,

мы бы хотели предложить вам еще одно задание.

Есть несколько серверов (допустим 10) на которых распределенно хранится какое-то большое множество чисел, 1Tb (на каждом своя часть). Есть еще один сервер, мастер, который может давать им задания посчитать что-нибудь про свою часть множества, и вернуть ему ответ. Канал между мастером и слейвами очень узкий, обмениваться можно только небольшими порциями данных, 1Kb. Нужно посчитать медиану всего общего множества.

Код, который можно запускать распределённо, писать не требуется. Просто описание алгоритма, и прототип на перле, который всё делает локально. Можно даже без отдельных процессов, просто в одном процессе разбить все данные на 10 частей, и обрабатывать их по отдельности.

Ух! А вот это уже сложнее. Да тут вообще, считай, почти одна математика. А математику я благополучно забыл сразу после того, как сдал её на втором курсе.

Антон Терехов 21.11.2011

Денис, хотелось бы уточнить пару моментов.
1) Нужно точное значение медианы или достаточно приближения?
2) Как предполагаю, массивы не отсортированы?

Денис 21.11.2011

1) Давайте будем считать, что все числа разные и их нечетное количество. И значение медианы нужно точное.
2) Это неважно, всегда можно послать слейвам команду “отсортируйте”.

Уже интереснее.

Антон Терехов 21.11.2011

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

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

Антон Терехов 28.11.2011

Добрый день, Денис!

Опять получилось присесть только в воскресенье.
Задание выполнил, во вложении архив с 2 скриптами. Один из них генерирует массивы чисел в файлы, другой находит из них медиану.

Сделал отступление от обговоренных условий – количество элементов в прототипе может быть как нечетным, так и четным.

Алгоритм следующий:
0) Предположим, на старте у нас начало исследуемого отрезка 0, конец 1000000.
1) Делим исследуемый отрезок на 10 равных частей. Мастер посылает команду слейвам построить гистограммы по диапазонам. Т.е. вопрос следующий: “Сколько значений лежит в диапазоне 0-1000000, 1000000-200000, …, 9000000-1000000”.
2) Слейвы сортируют значения, высчитывают и посылают гистограмму мастеру.
3) Мастер гистограммы суммирует, и определяет, в каком отрезке лежит медиана и считает её положение в этом отрезке.
4) Рекурсивно возвращаемся к пункту 1, исследуя найденный отрезок (к примеру, 4000000-5000000), пока не будет найден отрезок, в котором лежит только одна медиана.
5) Посылаем слейвам команду прислать по 2 значения, лежащих в или выше последнего найденного отрезка (т.е. наиболее близкие с большей стороны)
6) Если количество элементов нечетное, то медиана – наименьшее значение, если четное – то среднее арифметическое между наименьшими.

В конце делаю проверку самим мастером – открываю все файлы с данными, сортирую их и нахожу медиану в одном массиве.

Спустя день ожидания получил от Дениса следующее сообщение:

Денис 29.11.2011

Антон, добрый день!

Спасибо за интерес к нашим вакансиям. Мы внимательно изучили Ваши решения.
Несмотря на то, что Вы, несомненно, обладаете некоторым интересующим
нас опытом, в настоящий момент мы не готовы предложить Вам
должность Разработчик Perl.
Тем не менее, Ваша анкета будет сохранена в нашей базе данных,
и, если Вы не возражаете, мы будем рады вернуться к рассмотрению
Вашей кандидатуры на вакансии, которые могут открыться
в нашей компании в будущем.

Комментарии по решениям:
* неэффективная и “хрупкая” реализация IPC через файлы;
* время работы зависит (хоть и логарифмично) от значений в выборке, а не от количества данных;
* отсутствие обработки ошибок;
* отсутствие use strict.

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

Скачать исходники можно здесь: favicon и mediana.

С одной стороны, было немного обидно, что не позвали на собеседование. К удивлению, совсем немного.
С другой – я почувствовал радость. Даже облегчение. Что не надо никуда ехать и краснеть за свои знания )) Вакансия была ориентирована, как я понял, на Яндекс.Метрику, тогда наверняка нужны неплохие математические данные. Да и в Perl у меня, думаю, без проблем нашли бы пробелы. А уж как я был рад, что не нужно увольняться с текущей работы!
Но в любом случае я выполнил не совсем простые задачки. Может быть, на троечку с минусом, но выполнил. А это опыт. А он бесценен. И ещё одно. Даже два. Два раза я почувствовал необычайное удовлетворение после решения этих задач ))

VkWatch – обновление

В новой версии VkWatch можно смотреть статистику за всё время, помогает нам в этом волшебный календарик:

calendar

Принцип действия можно посмотреть, например, вот тут. Календарик сделан с помощью плагина jQuery UI DatePicker. Статистика тянется c помощью Ajax’а. Читать далее

Отчёт о Дне Программиста

Немного времени спустя пишу о Дне Программиста. Событий за время моего отсутствия на блоге прошло достаточно много, эмоции улеглись, но пишу то, что запомнилось.

P5310028 Читать далее

Вконтакт, группы, Google Chart

Готовлю к финалу 3 своих новых скрипта. Сегодня закончил черновую версию последнего.

perl

Читать далее

Автоматическое обновление статуса ВКонтакте

Опубликовал сначала на Хабре, теперь здесь.
Написал небольшой скрипт для автоматического обновления статуса в социальной сети ВКонтакте. Скрипт написан за полчаса, ничего сложного в нем нет. Толчком для написания стало желание побаловаться, в процессе возникла еще пара интересных идей, которые я осуществлять не планирую, может кого-то наведу на мысль и буду рад. Не будем голословничать, приступаем к делу.
Читать далее

DLE -> WP

Раз собрался переходить на WP, то придется писать конвертер базы. Появилась идея сделать его не для единичного пользования, а для широких масс, быть может кому и пригодится?

По теме нашел пока только прикладную софтину DLE2WP, которая удаленно коннектиться к MySQL-базе DLE и сохраняет все посты в XML-файл. Работоспособность еще не проверял, к тому же еще необходимо разрешить внешние соединения для MySQL. Читать далее

Двигаемся

Ура! У меня будет новый паспорт! 🙂

Закончил квест по сдаче документов, получил в какой-то управляющей конторе справку о том, где я был прописан на момент 6 февраля 1992 года (ну что за ебанизм, какие придурки только такие хуйни выдумывают), сходил в РОВД, там четверг неприемный день. Пошел в ЖЭУ, там добрая тетечка (большое спасибо ей) приняла все документы и завтра их отнесет сама в РОВД. Как иногда заебывает бюрократия!

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

Был сегодня на субботнике во дворе, надо же когда-то убирать срач, правда? В очередной раз убедился в поговорке “чисто не там, где убирают, а там, где не сорят”.

Ещё убедился, что связка Flash + Perl + MySQL является крайне мощной и эффективной. Жаль, что я не знаю Flash, но есть повод начать учить. У меня когда-то был небольшой опыт, поработал с Shape/Motion, со Scene, чуть-чуть с AS и на этом закончил. Надо учить, надо. Поработав с Михаилом из TimeZero, понял, насколько удобно и приятно работать с профессионалами и людьми, которые тебя понимают.
Читать далее

Как бороться с русским языком

Появилась необходимость выводить число баллов вместе с русским словом “балл”.
Нюанс в том, что:
0 – баллов
1 – балл
2 – балла
3 – балла

5 баллов

10 – баллов
11 – баллов

21 – балл
22 – балла

121 – балл

Придумал решение:


$word = &ball($rating);

sub ball {

my $number = shift;

$res1 = substr($number,length($number)-1,1);
$res2 = substr($number,length($number)-2,1);
if (($res1 eq 1) && ($res2 ne 1)) {$res1 = “балл”;}
elsif (($res1>=2) && ($res1<=4) && ($res2 ne 1)) {$res1 = “балла”;} #>
else {$res1 = “баллов”;}

return $res1;

}


Читать далее

Перенаправление на www

Вчера занимался оптимизацией и передо мной встала следующая задача: при запросе URL сайта без префикса WWW необходимо делать переадресацию с ответом сервера HTTP/1.1 301/302 Moved Permanently/New location на соответствующий URL с префиксом WWW.
Решение оказалось простым, банальным, но изящным )


$host = $ENV{‘SERVER_NAME’};
$vHOST = “http://www.$host”;

# Перенаправляем на WWW
if ($ENV{‘HTTP_HOST’}=~/www./) {
# Всё ок, дядя!
} else {
$toloc = $vHOST.$ENV{‘REQUEST_URI’};
print <<EOF;
Content-type: text/plain
Status: 302 New location
Location: $toloc
EOF
#>
exit;
}