Чтобы решать «нерешаемые» задачи, нужно знать алгоритмы

Артём Мурадов — Senior Software Development Engineer в Amazon и автор курса «Алгоритмы: roadmap для работы и собеседований ^[1]». Уже больше 14 лет он использует алгоритмы для решения рабочих задач и прохождения собеседований. С помощью алгоритмов он повышал производительность приложений, побеждал в спорах с коллегами и ускорял исследование ДНК. Даже попасть в Amazon ему помогло знание алгоритмов.

Мы пообщались с Артёмом, чтобы узнать о его опыте. Он подробно рассказал, как изучал алгоритмы и как они помогали ему в работе.  

Ускорил приложение в 600 раз с помощью алгоритма

2012 год. Я прихожу на работу и узнаю, что система, которую мы писали, медленно запускается. Настолько медленно, что мы даже не можем выпустить релиз.

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

Тогда меня это поразило: человек просто поменял квадратичный алгоритм на линейный, и всё снова стало прекрасно.

Прошло 5 лет, я оказался в другой компании, где отвечал за приложение, которое сравнивало объекты. Представьте, у вас есть объект №1 с полями, и объект №2 с полями. Вам нужно понять, чем они отличаются. Вы открываете форму, и она показывает разницу между объектами: какие поля добавились или удалились.

В какой-то момент приложение начало долго открываться, что было критично. Невозможно работать, если у тебя обычная форма сравнения объектов открывается 30 минут.

Припоминая историю спасённого релиза, я уже догадывался, в чём может быть дело, и начал смотреть код. Причина оказалась та же — неэффективный алгоритм. Когда приложение создавалось, полей было около 200, алгоритм справлялся. Прошло 10 лет, и количество полей возросло до десятков тысяч. Такие объёмы алгоритму были уже не под силу: он начал работать очень медленно.

Я произвёл ту же замену, что и мой коллега когда-то, — заменил квадратичный алгоритм на линейный. На всё это ушёл один день, и время открытия формы уменьшилось с 30 минут до 3 секунд. Скорость выросла в 600 раз.

За 2 дня сделал то, на что ушло 2 года

Я всегда читал много разных книг по алгоритмам. Особенно меня поразили «Жемчужины программирования» Джона Бентли. По большому счёту, это сборник историй и рассказов о том, как помогают алгоритмы. Одна из историй рассказывала о сортировке подсчётом. Обычно, если ты хочешь отсортировать какие-то вещи, ты предварительно сравниваешь их друг с другом. А особенность сортировки подсчётом в том, что тебе не нужно ничего сравнивать.

В то время я даже не мог представить, что существует такой алгоритм. Мозг ^[2] взрывался от нового знания, и я пошёл решать задачи. Какие-то давались легко, какие-то сложнее. Наконец, на одной платформе попалась такая, которую никак не получалось решить. Точнее моё решение работало, но было слишком медленным, что, конечно, меня не устраивало.

Шли месяцы, я всё пытался «одолеть» задачу, но она упорно не поддавалась. Теоретически, можно было бы подсмотреть решение в интернете, но я был слишком горд для этого.

В 2014 года я попал на онлайн-курс от Западного университета, где рассказывали про определённую структуру данных и её использование. К тому моменту про структуру данных я уже знал, но никогда не применял её на практике.

Открылась простая истина: недостаточно просто знать алгоритм, нужно понимать, когда его применить.

На курсе рассказали, что «структура данных» — это префиксное дерево, и показали, как с ним работать. Я начал решать примеры, и тут в голове щёлкнуло: «Это ведь та самая задача!». Я потратил ещё 2 дня и наконец-то справился с ней. Проблема была в теоретический базе — как только я её получил, сразу смог найти решение.

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

Пранк вышел из-под контроля: решил нерешаемую задачу

В 2016 году меня пригласили работать в Польшу. Хорошо помню первую задачу в новой компании. Она касалась блоттера.

Блоттер — грид по типу Excel с двумя особенностями. Первая особенность в том, что он держит в памяти только те данные, которые показывает. Предположим, есть таблица с миллионом элементов, из которых видны только 100. Эта сотня — то, что есть прямо сейчас. Всех остальных элементов нет. Когда крутишь блоттер, он начинает запрашивать новые пачки данных, чтобы отображать их.

Вторая особенность — все данные изменяются в реальном времени. Это значит, что в любой момент какие-то строчки могут пропасть, или, наоборот, добавиться.

Мне нужно было сделать так, чтобы, когда пользователь выделял какую-то область в блоттере, а после этого проматывал вверх или вниз, выделенная область сохранялась в памяти. Проблема заключалась в том, что строки постоянно добавлялись, удалялись и обновлялись. Всё это было очень динамично и, разумеется, не сохранялось. Если что-то промотал, всё тут же исчезало.

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

Но самое интересно дальше — начинаю рассказывать обо всём коллегам, а они только удивляются. Я, естественно, ничего не понимаю, спрашиваю, в чём дело. Тут выясняется, что надо мной просто пошутили. Все в команде уже пытались решить эту задачу, но ни у кого не получилось. И когда пришёл новичок, они просто хотели посмотреть, что он будет делать, столкнувшись с нерешаемой задачей. Правда, шутка вышла из-под контроля. И даже, когда спустя 4 года я уходил из компании, коллеги всё ещё вспоминали эту историю.

Ускорил исследование ДНК в 4000 раз

У меня около 900 ответов на Stack Overflow, из которых больше сотни по алгоритмам. В потоке вопросов я хорошо запомнил один, связанный с ДНК.

ДНК — молекула, которая обеспечивает хранение и передачу информации. Она состоит из нуклеотидов. Каждый нуклеотид содержит сахарную и фосфатную группу, а также азотистые основания. Эти азотистые основания делятся на 4 типа: аденин, тимин, гуанин и цитозин.

Эти же азотистые основания — 4 буквы, отвечающие за определённые позиции в ДНК. А сама ДНК выглядит как последовательность букв, алфавит которых ограничен 4 значениями. Для исследования нужно было обрабатывать миллионы таких последовательностей. Делать это автору вопроса приходилось в полуручном режиме. На то было две причины.

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

У меня родилась идея, как решить проблему. Если взять две последовательности, которые одинаковы на всех позициях, кроме одной, их можно смёржить в одну. Нужен только специальный символ, который скажет, что это не одна последовательность, а две.

Объясню на примере. У нас есть два имени: «Артем» и «Артём». Пускай, «е» и «ё» — это какая-нибудь спецбуква, например «у». Мы берём «Артём» и «Артем» и мёржим в «Артум». Теперь все, кто будет смотреть на слово «Артум», будут знать, что это два имени, но обрабатывать его смогут как одно.

Благодаря такому варианту сжатия можно было сократить количество последовательностей ДНК до нужного уровня. Допустим, на входе 600 элементов, а на выходе 17. На входе 3 миллиона, а на выходе 150 тысяч.

Я закончил писать алгоритм под свою идею, и автор вопроса опробовал его в действии. Он установил приложение с моим алгоритмом на новый компьютер и запустил обработку 4 миллионов последовательностей по 11 символов. Это было в 450 раз больше, чем могла посчитать его старая программа. Операция заняла 7 секунд. Производительность выросла в 4000 раз.

Я не делал никаких сложных распараллеленных вычислений. Только реализовал одну идею в простом алгоритме, который написал за пару дней. Всё. 

История попадания в Amazon

Скажу сразу, Amazon — не единственная крупная компания, куда я пытался устроиться. Я ходил на собеседование в Microsoft, дважды участвовал в отборе в Google. Каждый раз я добирался до финального этапа, но выбор делали в пользу другого кандидата.

Признаюсь, три неудачных собеседования дают повод усомниться в реальности попадания в компанию уровня FAANG. Хотя я и готовился ко встрече с представителем Amazon, шёл туда больше по фану: на других посмотреть, себя показать и шутеечки пошутить.

Прихожу, меня спрашивают: «Ну, что, готов?».

Отвечаю: «Да, погнали. Давай мне алгоритмы, сейчас всё разберём!».

Возможно, дело было в том, что я два раза готовился к собеседованию в Google, два раза участвовал в чемпионате внутри моей компании и вообще был адово нагретый по алгоритмам. Но когда мне задавали задачу, я даже не дослушивал её до конца. Говорил: «Всё, стоп. Я знаю, как решать». И начинал решать. Для некоторых задач даже код не писал — просто объяснял, что нужно сделать.

Когда уходил с собеседования, был в состоянии типа: «А что это было вообще? А где настоящее собеседование? Почему меня не разносят задачами?».

Вскоре со мной связались и сказали, что я прошёл, да ещё и назвали senior. Я тогда удивился, но сейчас понимаю, что это закономерно. Каждое новое собеседование добавляло мне опыта и развивало.

Я шёл трудным путём: сам составлял себе программу обучения, сам всё учил, сам выбирал задачи и решал их без помощи извне. В Microsoft я подался в 2012 году, а работать в Amazon начал только в 2020 году. За 8 лет у меня было 4 собеседования в FAANG, 3 из которых прошли неуспешно.

Когда я рассказал на прошлой работе, что прошёл собеседование в Amazon, меня сразу стали спрашивать, что там и как. И спрашивали так часто, что пришлось сделать шпаргалку, которую я просто копипастил и отправлял всем интересующимся. Но это было не напрасно — те, кто воспользовался моими рекомендациями, теперь работают там, где мечтали.