Открытые вакансии на должность разработчика в Яндексе есть всегда. Компания развивается, и хороших программистов не хватает постоянно. И претендентов на эти должности тоже хоть отбавляй. Главная сложность – отобрать действительно подходящих кандидатов. И в этом плане Яндекс мало чем отличается от большинства крупных IT-компаний. Так что базовые принципы, описываемые в этой статье, могут быть применимы не только к Яндексу.

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

Если вам понадобится алгоритм сортировки массива, который:

• Работал бы гарантированно за O(N*log(N)) операций (обменов и сравнений);
• Требовал бы O(1) дополнительной памяти;
• Был бы устойчивым (то есть, не менял порядок элементов с одинаковыми ключами)

то вам, скорее всего, предложат ограничиться любыми двумя из этих трёх пунктов. И, в зависимости от вашего выбора, вы получите, например, либо сортировку слиянием (требует O(N) дополнительной памяти), либо пирамидальную сортировку (неустойчив), либо сортировку пузырьком (работает за O(N²)). Если вы ослабите требование на память до O(log(N)) («на рекурсию»), то для вас найдётся алгоритм со сложностью O(N*(log(N)²) — довольно малоизвестный, хотя именно его версия используется в реализации метода std::stable_sort().

На вопрос, можно ли добиться выполнения одновременно всех трёх условий, большинство скажет «вряд ли». Википедия о таких алгоритмах не знает. Среди программистов ходят слухи, что вроде бы, что-то такое существует. Некоторые говорят, что есть «устойчивая быстрая сортировка» — но у той реализации, которую я видел, сложность была всё те же O(N*(log(N)²) (по таймеру). И только в одном обсуждении на StackOverflow дали ссылку на статью B-C. Huang и M. A. Langston, Fast Stable Merging and Sorting in Constant Extra Space (1989-1992), в которой описан алгоритм со всеми тремя свойствами.

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

Участники

19 ноября прошел финальный тур олимпиады по администрированию Linux среди студентов и молодых специалистов. Я уже несколько лет занимаюсь проведением таких Олимпиад: первые 4 олимпиады были просто по администрированию смешанных систем, а вот последние 2 года мы сосредоточились на Linux.

Последняя олимпиада прошла довольно необычно. Во-первых, вместо одного стандартного дистанционного отборочного тура, мы сделали два этапа — простой и посложнее. Во-вторых, как я и обещал в анонсе, на финал мы приготовили особенное блюдо: 27 участников финала должны были настроить боевой кластер и интегрировать его в инфраструктуру компании, смоделированную на симуляторе.

Ниже будут задания с ответами, описание практического задания и детали, но пока встречайте победителей:


Владимир, Анна и Вячеслав

• I место — Вячеслав Карпухин из Санкт-Петербурга (в прошлом году он занял III место).
• II место — Анна Мартынова из Москвы.
• III место — Владимир Довгелевич из Краснодара.

В данной статье будет показан математический подход к составлению алгоритмов на примере следующих вопросов и задач:

• Двоичные коды Грея. Их существование. Перебор подмножеств данного множества в порядке минимального изменения.
• Существование и реализация перебора подмножеств из k элементов в порядке минимального изменения.

Итак, приступим.

1. Что такое IEMs?

Внутриканальные наушники (англ. In-Ear-Canalphone), еще именуемые как затычки, реже ухо-мониторы или (правильное) IEMs (в дальнейшем в статье будет именно это название, т.к. оно очень лаконичное и нравится автору) — это наушники, внешне очень похожие на вкладыши, но разработанные для максимальной звукоизоляции ушного канала слушателя. Ее (звукоизоляцию) еще называют, звуковая «герметизация», — она имеет две функции: блокировка лишних шумов и формирование звуковой площади (камеры) для достижения полноты звучания. Создает такую герметизацию насадка, надетая на сопло наушника и вложенная в переднюю часть ушного канала. Существуют также наушники, где насадка создана по слепкам ушей владельца, — они называются (у русскоговорящей аудитории) кастомами (англ. Custom molded earplugs), — подобные вещи служат для достижения максимального качества звука и комфорта от прослушивания.

Почему выбирают IEMs? Из-за высокой портативности, качественного звука и способности к блокировке лишних шумов. Некоторые модели уже давно используют аудио-инженеры; музыканты, выступая на сцене. Затычки (в России это название прижилось больше), являются разновидностью IEMs. Когда производители внутриканальных наушников начали клепать их для общего потребителя (поколение iPod), аббревиатура IEMs стала более популярна (не в России), заменив выражение «затычек».  Техническим языком правильно «затычки» называть — IEMs. Реже аббревиатура IEMs используется для обозначения внутриканальных наушников высокого качества.

Не так давно наткнулся на статью о том, как Michael Kozakov не смог решить алгоритмическую задачу на собеседовании в Twitter. Решение этой задачи — почти в чистом виде один из самых стандартных алгоритмов на графах, а именно, алгоритм Дейкстры.
В этой статье я постараюсь рассказать алгоритм Дейкстры на примере решения этой задачи в несколько усложненном виде. Всех, кому интересно, прошу под кат.

Архитектура USB содержит несколько уровней. На самом низком уровне специально обученное железо, называемое хост-контроллером (host controller), общается с USB-устройством специальными сигналами. Сигналы кодируют биты, биты складываются в пакеты, пакеты образуют транзакции, транзакции составляют передачи (transfers).

Я рассказываю о программной поддержке USB, поэтому уровни ниже передач почти неинтересны: за них отвечает хост-контроллер. Зато важно, какой интерфейс представляет хост-контроллер софту. Сейчас распространены три интерфейса, и постепенно распространяется четвёртый:

Аббр.	Название интерфейса	Версия	Код поддержки контроллера в KolibriOS
UHCI	Universal Host Controller Interface	USB 1.1	kernel/trunk/bus/usb/uhci.inc
OHCI	Open Host Controller Interface	USB 1.1	kernel/trunk/bus/usb/ohci.inc
EHCI	Enhanced Host Controller Interface	USB 2.0	kernel/trunk/bus/usb/ehci.inc
XHCI	eXtensible Host Controller Interface (новый)	USB 3.0	В KolibriOS ещё не поддерживается

На этом же уровне взаимодействия с контроллерами находятся файлы kernel/trunk/bus/usb/hccommon.inc, где реализованы некоторые функции, общие для всех контроллеров, и kernel/trunk/bus/usb/init.inc, который запускает всю подсистему. Впрочем, не торопитесь пока лезть в код — во-первых, я ещё не рассказала про то, чего же ожидают от него более высокие уровни, а во-вторых, после демонстрации общей схемы я вернусь к отдельным компонентам с подробностями.

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

Сначала меня попросили решить пару вопросов с Codility, дав на все про все час времени. Вопросы попались средней интересности («является ли слово анаграммой палиндрома» и «посчитать количество седловых точек в двумерном массиве»). Я был не слишком уверен в получившихся решениях, но вскоре Джуди прислала мне письмо с приглашением на телефонное интервью в среду в 17:30.

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

Вы знаете, что каждый третий пылесос, который покупают в Испании – робот-пылесос? Спрос в России на эти устройства также растет из месяца в месяц. Цены варьируются в среднем от 10 000 до 30 000 рублей. Что из себя представляет этот популярный гаджет и как он устроен? На эти вопросы мы ответим в данной статье. Положим на операционный стол робот-пылесос среднего ценового диапазона Yujin Robot iClebo Arte и начнем изучать его внутренности. Звучит жутковато, но уверяю вас, статья подойдет даже для категории читателей 0+.

Спасибо каждому, кто читал и комментировал первую часть. Благодаря вам, продолжение будет еще интереснее. Если еще не читали — рекомендую это сделать. Там мало текста, и есть классные видео.

Изначально планировалось, что эта часть будет завершающей. Но, для удобства попадания в скролл, сейчас остановимся лишь на этих вопросах:

• Тренировки. Вырабатывание летных навыков.
• Выбор модели: самолет, вертолет или мультикоптер?
• Выбор конкретной конструкции и размера
• Моторы и ESC
• Полетный контроллер

Как обычно, сразу к делу.

Сейчас достаточно много постов и видео на тему как сделать из Vim Python IDE. Написать эту статью я решил потому, что уже долгое время пользуюсь этим редактором и надеюсь что мой опыт по его настройке, о котором я напишу в этой статье не помешает. Я не собираюсь делать из Vim «комбайн», напичкав его огромным количеством плагинов, а постараюсь обойтись средствами самого редактора и несколькими расширениями, которые помогут Python разработчикам чувствовать себя более комфортно. Давайте приступим.

Многие наслышаны о проблеме с неоткалиброванными датчиками в новом iPhone 5S – инструмент «уровень», встроенный в родной компас iOS 7 показывает отклонение в несколько градусов, если устройство положить на плоскую поверхность, например, стол.

Если кратко, то в той или иной степени проблема ориентации датчиков присутствовала всегда и на всех устройствах с iOS. Ранее проблему не наблюдали так часто в виду отсутствия встроенного в мобильную OS приложения позволяющего измерять уровень. Аналогичная проблема имеет место быть и на других мобильных устройствах оснащенных акселерометром, поскольку принципы везде заложены одинаковые – с этим не понаслышке должен быть знаком каждый разработчик, которому приходилось иметь дело с различными датчиками движения и ориентации.

Я разрабатываю приложения с использованием датчиков акселерометра, гироскопа и цифрового компаса, ровно с тех самых пор, как разработчикам стал доступен API, практически с самого начала – будучи автором одного из самых популярных компасов для iOS с проблемами калибровки акселерометра и точности других датчиков я столкнулся еще несколько лет назад.

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

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

Многие из нас размышляли об установке камеры на летательный аппарат. Вот я и прошел этот путь. Углубившись в тонкости видеополетов от первого лица (FPV), делюсь полученными знаниями с теми, кто тоже хочет испытать новые ощущения.

Пост состоит из 2 частей. В первой — ответы на основные вопросы. Их легко найти в интернете по-отдельности, но сложно вместе: дальность полета (чем ограничивается и какая максимальная), качество картинки, грузоподъемность, стоимость и сроки (от выделения бюджета до первого полета).

Вторая часть (сейчас в процессе) — о сборе конкретной системы со всеми тонкостями, какие мне только удалось найти и испробовать. Что именно и где купить, как расположить на модели, зачем и что экранировать, где требуются ферритовые кольца, а где виброгасители.

Ну что же, перейдем сразу к делу.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1
Часть 2
Часть 3

Оптимальная сортировка

Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n² ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.

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

Вот такая инфографика по снятию ведра с головы в вопросах хостинга была опубликована в блоге у хостера VPS.ua.

Пару недель назад, необходимо было освежить информацию в голове информацию по структурам данных и алгоритмам для собеседования. Первым делом полез на www.coursera.org, где хотел пробежаться по некоторым лекциям курса Алгоритмы, там же были две сводные таблички, которые в процессе изучения курса взял на заметку — отлично помогали запомнить сложность операций. Но, к моему удивлению, материалы пройденного курса стали недоступны. Быстрое гугление, в надежде, что кто-нибудь выложил лекции на торрентах, к сожалению, не дало результатов. В итоге, я нашел полную коллекцию слайдов по данному курсу. Спешу поделиться. Самое главное, что взял из этих слайдов, — это вышеупомянутые сводные таблички. Думаю многим пригодится.