Иногда собеседования в IT-компаниях становятся настоящими испытаниями, требующими не только знаний, но и логического мышления и умения быстро принимать решения. Давайте об этом сегодня поговорим подробнее.
Представим ситуацию: в качестве последнего вопроса на собеседовании в IT-компанию вам дают несколько листиков бумаги. На них изображены цифры, из которых вам предстоит составить максимально возможное число. Ваш результат станет вашей зарплатой, поэтому вы более чем заинтересованы решить эту задачу!
Например, если на листках написаны: «1», «5», «9», то составить из них самое большое число нетрудно — ответом будет 951. А сможете ли вы справиться, если достанутся цифры: «4», «42», «46», « 427», «465»?
Выше просто подводка к интересной алгоритмической задаче — написать программу, которая получает на вход список чисел и составляет из них максимальное.
Подобная задача может встречаться на алгоритмических собеседованиях. Готовы проверить свои силы?
Ниже мы предоставим решение (через серию тщательно подобранных подсказок, аналогичных тем, что даются на собеседованиях), а также предоставим код на Python. Проверьте себя в нашей интерактивной головоломке!
► Первый шаг в решении алгоритмической задачи — это придумать хоть какое-то решение. На этом этапе нас интересует только корректность решения, ускорять его будем позже. Итак, становится понятно, что для составления максимального числа нам нужно переставить исходные числа. Это и наталкивает на первое поспешное решение — перебрать перестановки всех чисел, на Python это выглядело бы так:
Для нашего рабочего примера этот код выдаст ответ мгновенно: 46546442742. Однако с ростом количества чисел время работы кода растёт непозволительно быстро — из-за того, что есть очень много перестановок: количество перестановок n объектов равно n ! (это произведение первых n целых положительных чисел; читается как «n факториал»).
Для наглядности мы выписали все перестановки пяти чисел:
Современные компьютеры делают порядка миллиарда базовых операций в секунду. Если считать, что машина, на которой мы запустим этот код, перебирает как раз миллиард перестановок в секунду, то ей понадобится примерно семьдесят семь лет, чтобы справиться с задачей. На собеседовании вас точно попросят найти что-то более эффективное!
► Второй шаг: для разработки более быстрого алгоритма воспользуемся полезным трюком — поймём, как вручную решить задачу на примере небольшого набора данных. Например, на наших числах: «4», «42», «46», « 427», «465». Если их вообще не переставлять (просто склеить), то получится — 44246427465. Однако такой результат не является максимальным (код выше выдал другой ответ). Что мы делаем не так?
Если внимательно рассмотреть наш массив, то становится заметно, что «42» стоит до «46». Если мы хотим получить максимальное число, в таком порядке их оставлять не стоит. Расстановку можно улучшить, поменяв числа местами. Затем мы видим, что можем поменять местами числа «4» и «46», чтобы наше число начиналось с «464», а не с «446». И так далее.
Таким образом подобные локальные улучшения стоит применять, пока они применяются и в массиве остаются два числа, от перестановки местами которых становится лучше. Этот метод позволяет установить порядок входных чисел, где число A считается лучше числа B, если при их конкатенации AB > BA. Такой подход к сортировке легко применить к нашей задаче, упорядочивая числа по убыванию в соответствии с этим отношением.
Этот код будет работать мгновенно даже на больших наборах чисел, если числа не очень длинные. Время его работы составляет O (n log n), где n — количество входных чисел. Однако и это ещё не всё!
► Третий шаг: хотя наш алгоритм выглядит правильным и быстрым, необходимо доказать его корректность на любых входных данных. Данный вопрос обязательно возникнет на собеседовании. Не отказывайте себе в удовольствии доказать это самостоятельно.
Строгое доказательство корректности алгоритма, а также возможность протестировать его в автоматизированной системе проверки доступны в интерактивном учебнике Алгоритмические задачи с собеседований! Кстати, этот курс идеально подходит всем, кто действительно хочет научиться оценивать время работы алгоритмов.