Как меня не позвали в Яндекс на собеседование
В конце прошлого года один из сотрудников Яндекса нашел меня в “Моём Круге” (а где же ещё им искать сотрудников?) и, так как у меня указано в специализации “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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 |
#!/usr/bin/perl
# Сколько у нас будет детишек?
$children = 30;
# Формат изображения на выход
$imageformat = "png";
#$imageformat = "bmp";
# Подключаем необходимые модули
use LWP::Simple qw(get);
use Imager;
require WWW::RobotRules;
# Открываем файл со списком доменов и путем к каталогу
open (FILE, "domains.txt");
@domains = <FILE>;
close (FILE);
# Отделяем муху от котлет
$path = shift(@domains);
$path =~ s/[\r\n]//isg;
# Плодим детей
$pcount = $children;
$childPID = 0;
while ($pcount > 0) {
$childPID = fork();
if ($childPID != 0) {
print "[MASTER] New child forked with PID: $childPID\n";
$pcount--;
next;
} else {
last;
}
}
if (!$pcount) {
# Прибираемся
deletegarbage();
# Что будет делать папочка?
daddy();
# Ждем всех детишек
while (($w = wait()) > -1) {
print "[MASTER] Child $w terminated!\n";
}
# И выходим
print "[MASTER] My children did everything!\n";
exit(0);
}
# Что у нас будут делать детишки?
print "[CHILD] Hello, i'm child!\n";
# Ждать, пока батя уберет мусор
sleep(2);
# Сигнализировать о готовности и делать работу. Детский труд сам дешевый.
child();
# Если заданий больше нет - значит ложаться спать
print "[CHILD] Work is done, bye!\n";
exit(0);
sub daddy {
print "[MASTER] Start creating jobs \n";
print "[MASTER] Searching for the free workers \n";
my $dir = 'job';
# Входим в бесконечный цикл
until (0) {
opendir(DIR, $dir) or warn $!;
while (my $file = readdir(DIR)) {
next unless (-f "$dir/$file");
next unless ($file =~ m/\!(\d+)$/);
# Ух, нашли свободного воркера
# Если ещё есть работа
if (@domains) {
#print "[MASTER] Found worker! - $file \n";
$domain = shift(@domains);
print "[MASTER] Create job for domain - $domain";
$jobfile = "$dir/job$1";
open (FILE, ">$dir/job$1");
print FILE $domain;
close (FILE);
unlink $dir."/".$file or warn "Could not unlink $file: $!";
$c = 0;
# Раздача закончена
} else {
print "[MASTER] I have no more tasks \n";
last;
}
}
closedir(DIR);
sleep 1;
$c++;
# Ждём уже долго, выходим из цикла
if ($c eq 10) {
print "[MASTER] No free workers \n";
last;
}
}
}
sub child {
my $domain = shift;
my $robotsrules = new WWW::RobotRules 'icoSpider';
$r1 = int(rand(1000));
$r2 = int(rand(1000));
my $dir = 'job';
&imready($r1,$r2);
until (0) {
opendir(DIR, "job") or die $!;
while (my $file = readdir(DIR)) {
next unless (-f "$dir/$file");
next unless ($file =~ m/\job$r1$r2$/);
print "[CHILD] Found job! - $file \n";
# Узнаем, что за работка
open(FILE, "$dir/$file");
$domain = <FILE>;
close(FILE);
print "Get domain from file - $domain \n";
# Удаляем файл с заданием
unlink $dir."/".$file or warn "Could not unlink $file: $!";
# Выполняем работу
dojob($domain);
&imready($r1,$r2);
$c = 0;
}
closedir(DIR);
sleep 1;
$c++;
# Ждём уже долго
if ($c eq 10) {
exit;
}
}
}
sub imready {
# Создаем файлик, сигнализирующий о том, что воркер свободен
($r1, $r2) = @_;
open (FILE, ">job/!$r1$r2");
close (FILE);
print "I'm ready - $r1$r2 \n";
}
sub dojob {
my $domain = shift;
my $robotsrules = new WWW::RobotRules 'icoSpider';
my $url;
my $html;
my $favicon;
my $favicon_url;
my $filename;
$domain =~ s/[\r\n]//isg;
# Достаем robots.txt и анализируем его
$url = qq~http://$domain/robots.txt~;
my $robots_txt = get $url;
if ($robots_txt) {
print "Found robots.txt for $domain \n";
} else {
print "Not found robots.txt for $domain \n";
}
$robotsrules->parse($url, $robots_txt);
# Готовимся грузить главную
$url = "http://$domain/";
# Проверяем, а можно ли нам её грузить
if ($robotsrules->allowed($url)) {
print "Main page for $domain is allowed! \n";
$html = get $url;
# Пытаемся найти иконку в коде
if (($html =~ /<link .*?shortcut icon.*?href=[\"'](.+?)[\"'].*?>/) || ($html =~ /<link .*?href=[\"'](.+?)[\"'].*?[\"']shortcut icon[\"'].*?>/)) {
print "FOUND favicon link in code for $domain \n";
$favicon_url = $1;
if ($favicon_url =~ "^\/\/") {
$favicon_url = qq~http:~ . $favicon_url;
} elsif ($favicon_url =~ "^\/") {
$favicon_url = qq~http://$domain~ . $favicon_url;
} elsif (!($favicon_url =~ "^http:\/\/")) {
$favicon_url = qq~http://$domain/$favicon_url~;
}
# Не нашли иконку в коде
} else {
print "NOT FOUND favicon link in code for $domain \n";
}
# Нельзя грузить главную
} else {
print "Main page for $domain is NOT allowed! \n";
}
# Получили ли линк на иконку?
if (!$favicon_url) {
print "Try to find favicon for $domain \n";
$favicon_url = $url . "favicon.ico";
} else {
# Проверим, на том же домене находиться иконка или нет
if ($favicon_url =~ /^http:\/\/(.+?)\//) {
# Да, на том же
if ($domain eq $1) {
print "Favicon on same domain name - $domain \n";
# Нет, не на том же
} else {
print "Favicon is not on same domain name - $domain \n";
# Проверим, можно ли нам туда ломиться
$url = qq~http://$1/robots.txt~;
$robots_txt = get $url;
if ($robots_txt) {
print "Found robots.txt for $1 \n";
} else {
print "Not found robots.txt for $1 \n";
}
$robotsrules->parse($url, $robots_txt);
}
} else {
print "Favicon domain check error - $domain \n";
}
}
# Если разрешено, то пытаемся загрузить
if ($robotsrules->allowed($favicon_url)) {
print "Favicon is allowed for $domain \n";
print "Trying to download favicon for $domain - $favicon_url \n";
$favicon = get $favicon_url;
# Сохраняем
if ($favicon) {
print "Successfully downloaded favicon for $domain \n";
$filename = $path."/".$domain.".ico";
open (FILE, ">$filename");
binmode(FILE);
print FILE $favicon;
close (FILE);
# Конвертируем
$img = Imager->new;
$img->read(file=>$filename, type=>"ico")
or warn "IMAGER SAYS: Cannot read $filename. Error: ", $img->errstr;
$filename =~ s/.ico$//isg;
$img->write(file => "$filename.$imageformat")
or warn "IMAGER SAYS: Cannot write $filename.$imageformat. Error: ",$img->errstr;
} else {
print "Can't get favicon for $domain \n";
}
} else {
print "Favicon is NOT allowed for $domain \n";
}
undef $favicon_url;
}
sub deletegarbage {
# Удаляем мусор с прошлых запусков
$dir = 'job';
opendir(DIR, $dir) or warn $!;
while (my $file = readdir(DIR)) {
next unless (-f "$dir/$file");
print "Delete garbage - $dir/$file \n";
unlink("$dir/$file");
}
closedir(DIR);
} |
Денис 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) Если количество элементов нечетное, то медиана – наименьшее значение, если четное – то среднее арифметическое между наименьшими.В конце делаю проверку самим мастером – открываю все файлы с данными, сортирую их и нахожу медиану в одном массиве.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 |
#!/usr/bin/perl
print "Start!";
# Стартовый диапазон
$start = 0;
$end = 10000000000;
my @values;
$stage = "";
# Главный цикл
while (1) {
print "\n ------------------------------- \n NEW START = $start, END = $end \n";
# Количество файлов
$files = 10;
$chfiles = $files;
while ($files > 0) {
# Если ещё не перешли к последнему этапу
if ($stage ne "laststage") {
# Получаем гистограммы
%r = find($files, $start, $end, $stage);
# Суммируем
while (($key, $value) = each(%r)){
$sum{$key} = $sum{$key} + $value;
#print $key.", ".$value." \n";
}
# Последний этап
} else {
# Получим самые близкие к медиане значения
push(@values, find($files, $start, $end, $stage));
}
$files--;
}
# Последний этап
if ($stage eq "laststage") {
# Сортируем самые близкие к медиане значения
@values = sort {$a <=> $b} @values;
print "More closer values: \n";
print @values;
print "\n";
# В зависимости от четности получаем медиану
if ($twomedians eq "yes") {
$median = ($values[0] + $values[1]) / 2;
} else {
$median = $values[0];
# Наводим красоту
$median =~ s/[\r\n]//isg;
}
# Выводим найденное значение
print "MEDIAN = $median \n";
# Делаем проверку и выходим
check($chfiles);
exit;
}
# Счетчик элементов в суммарной гистограмме
$allcount = 0;
# Считаем общее количество элементов
while (($key, $value) = each(%sum)){
$allcount += $value;
#print $key.", ".$value." \n";
}
# Если это - первая итерация, высчитываем положение медианы и проверяем четность
if (!$maincount) {
$medianpos = $allcount / 2;
if ($medianpos ne int($medianpos)) {
# Придётся брать среднее арифметическое
$twomedians = "yes";
$medianpos = int($medianpos);
}
}
# Выводим промежуточную информацию
print "Total : $allcount \n";
print "Median position: $medianpos \n";
# Счетчики
$msum = 0;
$misum = 0;
$i = 0;
# Начало и шаг
$vk = $start;
$step = ($end - $start) / 10;
# Находим, в каком промежутке лежит медиана
while ($i < 10) {
# С чем сравниваем
$vk += $step;
$vv = $sum{"$vk"};
print "< $vk - $vv \n";
$msum += $vv;
# Ура! Подощли к последнему этапу
if (($medianpos == $msum) && ($vv eq 1) && ($medianpos eq 1)) {
print "Found position of median!";
# Новая нижняя граница
$start = $vk - $step;
# Ставим флажок
$stage = "laststage";
# Выходим из этого цикла
last;
# Нашли отрезок, в котором лежит медиана
} elsif ($medianpos <= $msum) {
print "Stop! Sum = $msum";
# Новая нижняя граница
$start = $vk - $step;
# Новая верхняя граница
$end = $vk;
# Положение медианы в этом отрезке
$medianpos = $medianpos - $misum;
# Выходим из этого цикла
last;
}
$misum += $vv;
$i++;
}
undef $allcount;
undef %sum;
undef %r;
$maincount++;
}
sub find {
my %gist;
my @last;
# Кушаем параметры
($file, $start, $end, $mode) = @_;
# Открываем файл
open (FILE, "data/$file.txt");
@mfile = <FILE>;
close (FILE);
# Сортируем числа
@mfile = sort {$a <=> $b} @mfile;
# Необходимые счетчики
$m = 1;
$pos = 0;
$count = $#mfile + 1;
# Начало и шаг
$s = $start;
$step = ($end - $start) / 10;
# Последний этап
if ($mode eq "laststage") {
print "\n\n ------------------------------------- \n LAST STAGE \n";
$i = 0;
$found = 0;
# Выбираем 2 значения, наиболее близких к медиане
while (($found < 2) && ($i < $count)) {
if ($mfile[$i] > $start) {
print "$file|$mfile[$i]";
push (@last, $mfile[$i]);
$found++;
}
$i++;
}
print "\n";
return @last;
}
# Делим отрезок на 10 частей
while ($m <= 10) {
$s += $step;
$so = 0;
#print "Start from $pos to $count, higher is $s ($m iteration) \n";
# Начинаем цикл с того места, где остановились в прошлой итерации
for ($i = $pos; $i < $count; $i++) {
$value = int($mfile[$pos]);
# Проверяем принадлежность промежутку
if ($value <= $s) {
if ($value >= $start) {
$so++;
$prev = $value;
}
} else {
# Уже вышли из промежутка, выходим из цикла
last;
}
$pos++;
}
#print "Found: $so, last in this case - $prev \n";
# Добавляем значение к гистограмме
$gist{"$s"} = "$so";
undef $prev;
$m++;
}
return %gist;
}
sub check {
# Количество файлов
$files = shift;
# Получаем данные из файлов и запихиваем в один массив
while ($files > 0) {
# Открываем файлы
open (FILE, "data/$files.txt");
@mfile = <FILE>;
close (FILE);
push(@check, @mfile);
$files--;
}
# Сортируем
@check = sort {$a <=> $b} @check;
$checkcount = $#check + 1;
$halfcheckcount = $checkcount / 2;
# Выводим количество элементов
print "CHECK COUNT: $checkcount \n";
# В зависимости от четности, высчитываем и выводим значение медианы
if ($halfcheckcount eq int($halfcheckcount)) {
$checkmedian = @check[$halfcheckcount - 1];
} else {
$checkmedian = (@check[$halfcheckcount - 1] + @check[($halfcheckcount)]) / 2;
}
print "CHECK MEDIAN: $checkmedian \n";
} |
Спустя день ожидания получил от Дениса следующее сообщение:
Денис 29.11.2011
Антон, добрый день!
Спасибо за интерес к нашим вакансиям. Мы внимательно изучили Ваши решения.
Несмотря на то, что Вы, несомненно, обладаете некоторым интересующим
нас опытом, в настоящий момент мы не готовы предложить Вам
должность Разработчик Perl.
Тем не менее, Ваша анкета будет сохранена в нашей базе данных,
и, если Вы не возражаете, мы будем рады вернуться к рассмотрению
Вашей кандидатуры на вакансии, которые могут открыться
в нашей компании в будущем.Комментарии по решениям:
* неэффективная и “хрупкая” реализация IPC через файлы;
* время работы зависит (хоть и логарифмично) от значений в выборке, а не от количества данных;
* отсутствие обработки ошибок;
* отсутствие use strict.
Комментарии вполне справедливые. Написать решения, которые я представил на рассмотрение в Яндекс, мне было достаточно тяжело, но от этого не менее интересно. На решения потрачено порядка 2 дней кодинга и много свободного времени для обдумывания (намного больше, конечно же, на вторую задачу).
Скачать исходники можно здесь: favicon и mediana.
С одной стороны, было немного обидно, что не позвали на собеседование. К удивлению, совсем немного.
С другой – я почувствовал радость. Даже облегчение. Что не надо никуда ехать и краснеть за свои знания )) Вакансия была ориентирована, как я понял, на Яндекс.Метрику, тогда наверняка нужны неплохие математические данные. Да и в Perl у меня, думаю, без проблем нашли бы пробелы. А уж как я был рад, что не нужно увольняться с текущей работы!
Но в любом случае я выполнил не совсем простые задачки. Может быть, на троечку с минусом, но выполнил. А это опыт. А он бесценен. И ещё одно. Даже два. Два раза я почувствовал необычайное удовлетворение после решения этих задач ))
