Собеседования в крупные 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" можно на сайте книги.
Комментарии (17)
TiesP
17.06.2022 17:15+3один из вариантов решения на PythonДля решения используем структуру данных «Куча»import heapq def get_min_length(a): if len(a) > 2: heapq.heapify(a) res = 0 while len(a) > 1: min_sum = heapq.heappop(a) + heapq.heappop(a) res += min_sum heapq.heappush(a, min_sum) else: res = sum(a) return res
Alexandroppolus
18.06.2022 09:41Вторую минимальную необязательно извлекать из кучи. Можно к ней добавить первую (которую извлекли) и просеять вниз, будет чуть меньше действий.
red_elk
17.06.2022 19:00Интуитивно, на каждом шаге нужно соединять две самые короткие на данный момент верёвки.
wataru
17.06.2022 19:36Достаточно доказать, что можно первым шагом две минимальные веревки объединить. А дальше, после первого шага, задача сводится к той же самой.
Если представить дерево, как эти веревки сливаются, то там листья — это входные числа, а промежуточные вершины отвечают объединениям. Каждый лист посчитается в ответе ровно столько раз, какая у него глубина. Значит можно жадно минимальные веревки запихивать как можно глубже. Не факт, что это уже будет оптимальный ответ, ведь может самое дерево надо переформатировать, но то, что в оптимальном ответе первый шаг, это две минимальные веревки, уже доказано.
WhiskyBar
18.06.2022 12:49Из России как оплатить можно? Мир не принимает, платеж визой не проходит, якобы потому что банк отклоняет, но подозреваю, что из-за ограничений визы.
alexanderskulikov Автор
18.06.2022 12:50Оказывается, что из России никак, к сожалению. Я вот и сам этого не знал.
WhiskyBar
18.06.2022 12:54Я посмотрел правила площадки, если вы выставите цену в рублях за курс, то платежи пойдут через ю-кассу, которая поддерживает мир и работает с российскими картами. Не знаю, насколько это применимо в вашей ситуации - но если получится, было бы здорово.
alexanderskulikov Автор
18.06.2022 13:06Если выставить в рублях, то не сможем в долларах принимать, к сожалению, как выяснилось.
YAKOROLEVAZAMKA
Насколько я понимаю, после каждой итерации нужно получать верёвки минимальной длинны, т.е. по сути мы создаем массив из длин веревок и соединяем первую и последнюю, вторую и предпоследнюю и тд, и так на каждой итерации.
Это очень сильно напоминает главу из книги Перельмана ("Занимательная арифметика" если не ошибаюсь) где учитель дал ученикам задачу сложить все числа от 1 до 100..
alexanderskulikov Автор
И одним из этих учеников был Гаусс, да? =)
Но почему в Вашем решении получится оптимальная стоимость всё-таки?
YAKOROLEVAZAMKA
не знаю, интуиция)
а вот объясните мне, пожалуйста, откуда вот тут 39 взялось:
Сначала соединим 10 и 5, потом соединим 21 и 3, после чего соединим две полученные верёвки. Стоимость: 15+24+39=78.
мы же соединили
1) 10 + 5 = 15,
2) 21 + 3 = 24,
3) 24 + 15 = 39
Ответ: 39
Или я неправильно условие задачи понимаю?
wataru
3+5 = 8, 8+10 = 18, 18+21 = 39.
Итого: 8+18+39= 65
Сильно меньше ваших 78.
YAKOROLEVAZAMKA
я получается неправильно условие задачи понял, думал что после каждой итерации мы получаем новую веревку и её складываем со следующей, а не то, что нужно найти сумму всех складываний веревок - тогда, конечно, надо складывать минимальные по очереди :)