Дипломный проект

В сентябре 2011 года я восстановился в университет из академического отпуска и буквально на днях защитил свой дипломный проект. Надо сказать, сама программа была написана ещё в августе 2011 года, а диплом по ней я написал уже в мае 2012 года. Но, хочу заметить, что дипломный проект и действующая программа имеют между собой достаточно мало общего. Вообще, глядя на весь процесс дипломного проектирования, хочу сказать (по крайней мере, про мой университет) следующее: написание диплома очень походит на написание сказок.

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

Дипломный проект “Разработка системы прослушивания телефонных переговоров для цифровой автоматической телефонной станции”. Пояснительная записка и презентация доступны по этой ссылке.

Диплом кроме меня и рецензента никто не читал. На защите смотрели картинки с презентации и вопросы задавали именно по ним. Текст выступления написал в ночь перед защитой, волнения практически не было. Посидел на защите у 5 первых дипломников (моих одногруппников, лол, которых я практически не знаю) и стало немного тревожно – им задавали много вопросов. Особенно, учитывая то, что мой диплом не так уж и сильно пересекается с моей специальностью. Однако, когда очередь дошла до меня (выступал я под номером 13), презентация прошла настолько быстро, что я даже не успел опомниться. Точнее, мне сказали: “Молодой человек! Время!” После чего пришлось очень быстро перелистывать оставшиеся слайды и переходить к заключению. Вопросов задали всего 3 (у тех одногруппников, у которых я присутствовал, было от 5 до 15 вопросов), все были для меня очень простые. После выступления в оценке не сомневался, поставили “отлично”. Такие дела.

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

В конце прошлого года один из сотрудников Яндекса нашел меня в “Моём Круге” (а где же ещё им искать сотрудников?) и, так как у меня указано в специализации “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 у меня, думаю, без проблем нашли бы пробелы. А уж как я был рад, что не нужно увольняться с текущей работы!
Но в любом случае я выполнил не совсем простые задачки. Может быть, на троечку с минусом, но выполнил. А это опыт. А он бесценен. И ещё одно. Даже два. Два раза я почувствовал необычайное удовлетворение после решения этих задач ))

День программиста

В этом году в России второй раз официально отмечается профессиональный праздник программистов. Коллеги, с праздником!

 

Не забываем душить коллег мышками, разбивать об головы клавиатуры и кричать “ПИ-АШ-ПИ!!!”
C утра наблюдается поисковая активность:

 

Около 10:40 по московскому времени упала статистика лирушечки. Видимо, там уже отмечают.

 

Неофициальный гимн программистов:

Мы двигаем технологии вперед, мы воплощаем идеи в рабочие проекты, мы меняем жизни людей. Мы – люди Х борцы с единицами и нулями, которым на нелегком пути помогают наши верные друзья компиляторы и интерпретаторы. За нас!

Комментируйте ненужные фичи!

Забыл отключить одну тестовую фичу и при каждой авторизации на рабочем сайте на вконтакт добавлялся балл к рейтингу. Заметил поздновато.

WordPress 3.0

Вчера анонсировали первый стабильный релиз WordPress 3.0.

Обновил свой, вроде бы работает (что, кстати, неудивительно). Хвала, слава и почёт 200+ разработчикам, которые трудились полгода, чтобы это событие произошло. В новых фичах ещё не копался, обновлю лучше блог камикадзе, пусть он расскажет о впечатлениях.

Горячая вакансия

Уже обкидал все “вштаты” и “моикруги”, но результата до сих пор нет.
Мало ли он пробежит тут? Кто должен пробежать и увидеть это объявление?
PHP-программист. Работа в офисе в Рязани, зарплата достойная, обсуждается на собеседовании. Интересные задачи, дружный коллектив.

О жизни программистов

Обладатель весьма распространённой в сети картинки на заднем стекле авто награждается бесплатной ссылкой с моего говноблога – ivlev.biz

В оффлайне часто можно встретить вот такой вариант:

majka-pro

Гороскопы

Написал скрипт, который будет показывать гороскопы. Пока что выложен на моём домене. Встречаем, гороскопы на tereh.ru

Знаки зодиака

Обновляться это безобразие должно ежедневно в 00:20, посмотрим на результат уже завтра, правильно ли я всё настроил. Позже появятся гороскопы на месяц, на год и прочая лунная поебистика. Читать далее

Жёлтые страницы

На днях закончил парсинг рязанских “Жёлтых страниц” – 062.ru
Вся информация, которая есть на этом перегруженном “по самое не могу” рекламой “сайтом”, теперь есть в моей БД. Около 14500 организаций, дамп БД весит 8 мб в несжатом виде.

b3e33d7b53ea

Если интересно – пишите, продам недорого всю БД.
Напоминаю – пишу парсеры! Самые пиздатые парсеры в Рязани пишутся мной, качество охуенное, цена совсем не невъебенная! Читать далее