Собеседования в крупные IT-компании почти всегда содержат алгоритмическую секцию — даже если вы собеседуетесь на позицию, в работе на которой алгоритмы возникать вряд ли будут. Ниже мы приводим пример задачи, с которой вы можете столкнуться на вашем следующем интервью. Мы расскажем, как эта задача решается, но мы настоятельно рекомендуем вам читать решение только после того, как вы попробуете решить задачу самостоятельно: во-первых, это отличная тренировка; во-вторых, вы лучше запомните решение, если придумаете его сами (не отказывайте себе в этом удовольствии!); в-третьих, даже если вы подумаете над задачей, но не решите её, время не будет потеряно: прочитав потом решение, вы лучше его поймёте и оцените его красоту.
Задача: минимальная стоимость соединения верёвок
Найти минимальную стоимость соединения данных верёвок в одну, где стоимость соединения двух верёвок равна сумме их длин.
В качестве примера рассмотрим два сценарии соединения четырёх верёвок, длины которых равны 10, 5, 21 и 3.
Сначала соединим 10 и 5, потом соединим 21 и 3, после чего соединим две полученные верёвки. Стоимость: 15+24+39=78.
Сначала соединим 3 и 5 — получим верёвку длины 8. После этого соединим 8 и 10 — получим верёвку длины 18. Наконец, соединим 18 и 21. Стоимость: 8+18+39=65.
Интерактивный учебник для подготовки к собеседованиям
Недавно мы с Павлом Певзнером, профессором Университета Калифорнии в Сан-Диего (UCSD), написали интерактивный учебник, помогающий подготовиться к алгоритмическим собеседованиям. Вот в чём заключается интерактивность этого учебника:
В книжке есть 30 автоматически проверяемых задач на программирование. Сдавать их можно практически на любом языке программирования, проверяющая система сразу сообщает вам результат прохождения тестов. Для каждой задачи мы приводим подробное решение и стараемся сделать это так, чтобы было видно, как до этого решения можно было догадаться самому. Каждая задача сопровождается решением на языке программирования Python. Задачи тщательно подобраны: в каждой из них используется алгоритмическая идея, которая возникает во многих задачах на собеседованиях.
Есть 28 задач с собеседований: каждая из них сопровождается серией подсказок, которые постепенно складываются в решение.
Отдельная глава посвящена решению и тестированию таких задач, а также лучшим практикам написания кода. Эти советы помогут вам писать код так, чтобы уменьшить вероятность возникновения ошибок.
Мы оперативно отвечаем на вопросы слушателей на форуме. Для каждой задачи также есть форум с решениями, где вы сможете посмотреть, как эту задачу решили другие участники.
Чтобы помочь вам дойти до многих идей самостоятельно, мы используем интерактивные пазлы, каждый из которых посвящён своей алгоритмической идее. Пример такого пазла: соседние клетки разного цвета.
Решившим все задачи мы предлагаем также сдать экзамен (тоже автоматически проверяемый), по результатам которого мы готовы написать персональное рекомендательное письмо.
Учебник платный, но несколько его разделов, включая раздел с решением задачи о соединении верёвок, доступны бесплатно. Промокоду ALGHABR даёт скидку 50% до 25 июня. Узнать больше об использующемся в книге подходе "active learning approach" можно на сайте книги.
