Нужны ли программисту алгоритмы и структуры данных
Впервые я написал строчку кода 10 лет назад. С тех пор я каждый день удивляюсь, как много возможностей открыла для человечества разработка. В разработку же меня привело решение алгоритмических задач и участие в соревнованиях по программированию. Первый коммерческий проект я завершил 7 лет назад. Тогда осознал, что недостаточно написать рабочий эффективный код за короткое время. Инженер должен знать архитектурные подходы, придерживаться стиля и банально писать читаемый код.
Но статья будет скорее о первом: о написании рабочего эффективного кода, который прослужит долго. Она будет полезна как новичкам, которые ищут возможности для профессионального роста, так и для опытных специалистов, которые знают несколько языков, могут прихлопнуть любой баг и тянуть любой проект, но стремятся к разработке новых проектов.
Денис Цьоменко с докладом «Зачем мне знать алгоритмы, если они все уже реализованы?» на RunIT в Днепре, май 2019
Вечный холивар по теме «нужна ли программисту математика» подвергается изменению и превращается в более опасный для индустрии спор. Все чаще на форумах, конференциях и в головах мелькает мысль: «Нужно ли программисту знать алгоритмы и структуры данных?». И этот спор имеет место быть. Сомнительно, что разрабатывая продукт, придется самостоятельно реализовывать быструю сортировку или словарь. Продвинутые же структуры данных пригодятся не более чем
Мысль противоположной стороны выражается так: «Через
Поэтому собеседования в FAANG или MINT на 60%-100% состоят из Problem Solving задач, для решения большинства которых нужны знания алгоритмов. Сейчас этот тренд переходит и на middle-size компании в мире и в Украине. Из личного опыта могу сказать, что я писал на С++, .NET и Python. И вне зависимости от языка, я использовал знания алгоритмов.
«Нельзя доверять коду, который вы не написали полностью сами», — Кен Томпсон.
Алгоритмы на собеседованиях
В каждой компании есть свой подход к собеседованиям и оценке кандидатов. Также отличаются цели найма. Но есть вещи, которые их объединяют. Я проходил собеседования в различные компании разных размеров и направлений. Где-то алгоритмы и решение задач были ключевым фактором, где-то — вспомогательным. Задачи могут быть разных уровней сложности. Например, самая простая из тех, что мне встречались, — развернуть строку без использования дополнительной памяти. Одна из задач сводилась к умению быстро считать максимальное значение функции xor на префиксном дереве (бор). Ее сложность скорее заключалась в неочевидном решении, чем в реализации. Хорошая задача на собеседовании должна иметь несколько возможных решений, кроме оптимального. Невозможно знать все.
Пример плохой задачи, которую я встретил на собеседовании, это нахождения решения системы обычных дифференциальных уравнений. За вменяемое время невозможно приблизиться к решению, если ты не знаешь алгоритм Рунге-Кутты. Такого же типа собеседования обычно рассчитаны как раз не на проверку умения заучивать редкие алгоритмы, а на умение эффективно использовать стандартные. Чем же отличаются подходы в разных компаниях?
Большие корпорации
Компаниям-гигантам не важно, какой язык Вы знаете или сколько фреймворков выучили. Microsoft, Google или Tesla не нужны «исполнители», которых у них десятки тысяч. Этим компаниям нужны люди, которые смогут придумать и создать новый продукт, оптимизировать устаревший и дальше продвигать эти компании вверх. Умножьте это на количество кандидатов и необходимый ресурс для отбора. В итоге получим «алгоритмические» собеседования. Такой подход критикуют, пытаются изменить и усовершенствовать. Например, вопросами по софт скиллам или по дизайну систем. Подобные интервью иногда отсеивают достойных кандидатов, но продолжают проводиться и доказывать эффективность.
Нравится вам это или нет, но чтобы попасть в подобную компанию, вам необходимы алгоритмы. Разница между большими и средними компаниями в том, что в первых реже встречаются задачи уровня Hard, а знаний продвинутых алгоритмов не требуют, потому что они набирают много кандидатов и упустить хорошего инженера из-за незнания отдельно взятой структуры данных просто невыгодно.
Пройти такое собеседование помогут даже не знания алгоритмов, а количество решенных типичных задач. Важно понимать, что правильное решение не всегда гарантирует успешное прохождение собеседования. Точно также, как и неоптимальное решение не гарантирует отказ. Люди хотят работать с людьми, а не с машинами для написания кода, поэтому хотят посмотреть, как Вы думаете и говорите. В развитии этого навыка очень помогают пробные интервью. Вы можете проводить их с другом, коллегой или на различных ресурсах, где можно провести и пройти интервью со случайными людьми. Классическим же мануалом по прохождению в большие корпорации является книга «Cracking the Coding Interview». И если Вы хотите попасть в одну из них, то советую прочитать.
Минимальный набор знаний для прохождения интервью в большие компании
| Структуры данных | Алгоритмы | Концепты |
| Стэк/очередь | Бинарный поиск | Битовые операции |
| Списки | BFS/DFS | Память (Stack vs Heap) |
| Хэш-таблицы | Сортировки (quick, merge, stable, bucket) | Рекурсия |
| Списки | BFS/DFS | Динамическое программирование |
| Деревья, графы | — | Big-O notation |
Средние компании
Опыт лучших перенимают и организации, которые гонятся за ними. В Украине существует минимум 3 компании, которые фокусируются на problem solving interview (DataRobot, Ring Labs, Grammarly). Еще большая часть включают их в свой процесс собеседований как вспомогательные.
На определенном этапе развития компании ей понадобятся быстродействие, оптимизация и новые крутые фишки. А возможно ли придумать что-то новое, не зная и не понимая существующее? Ответ очевиден.
В некоторых компаниях среднего размера могут встречаться задачи, которые требуют точечной подготовки. Это возможно из-за конкретных требований проекта и ограничений в количестве набираемых кандидатов. Когда вы набираете 10 человек, а не 1000, тогда вы действительно хотите отобрать лучших из лучших.
Стартапы
Любой успешный стартап — это не только крутая идея, но и качественная реализация. В самом начале пути, когда пишется PoC (Proof of Concept), можно игнорировать и архитектуру, и оптимизацию. В таком случае при развитии и расширении стартапа придется выделить время на переписывание/ доработку/ рефакторинг.
Казалось бы, при чем здесь алгоритмы? Problem solving задачи развивают также умение быстро писать решение задачи, не задумываясь об архитектуре. И это часто то, что нужно для старта: написать «что-нибудь», что будет работать в кратчайшие сроки. Поэтому к «спортивным программистам» относятся с опаской. Да, они напишут для вашего продукта что угодно за минимальное время. Сможет ли этот код поддерживать кто-то другой? Ответ на этот вопрос размыт.
На этой волне можно вспомнить статью об украинском стартапе Looksery, который был основан людьми, связанными с олимпиадами. Они и набирали себе подобных: призеров и участников ACM ICPC (студенческая командная олимпиада), финалистов IOI (олимпиада для школьников), ребят с высоким рейтингом на CodeForces или TopCoder. Чем закончилась эта история, думаю, все осведомлены, или могут узнать по ссылке выше.
С другой стороны, собеседования в стартапы — самые непредсказуемые. Иногда это может быть и одно интервью об опыте и «чем хочешь заниматься», а после этого — офер. В другом случае, это может быть длительный процесс с 8+ интервью различной сложности.
Аутсорс
С аутсорсом все сложнее. Из всех типов компаний я меньше всего собеседовался в аутсорс, но общаясь с многими коллегами/ друзьями, которые работают в разного рода аутсорсинговых компаниях, можно сделать выводы.
Я ни разу не встречал людей, у которых спрашивали problem solving в аутсорсе. В маленьком /среднем/ крупном — не важно.
Связано это с тем, что аутсорсу нужно сразу бросить разработчика в бой. Им важно, чтобы он понимал язык, фреймворки, которые используются на проекте. Также кандидат должен пройти интервью с заказчиком, которому также не выгодно даже
Если у Вас есть истории о прохождении problem solving interview в аутсорсе — поделитесь в комментариях. Будем надеяться на лучшее.
Использование алгоритмов в реальной разработке
За свою карьеру в различных компаниях в трех странах (США, Германия, Украина) я, так или иначе, сталкивался с алгоритмами. Иногда это неявное использование с применением стандартных библиотек, иногда — явная реализация. Даже обычное наследование — это, по сути, граф взаимосвязей между классами. Получается, что каждый день на работе программисты используют какой-то алгоритм или структуру данных. Хэш-таблицы, сортировка, алгоритмы поиска и другие популярные алгоритмы уже реализованы в большинстве популярных языках. И чем лучше понимание как эти алгоритмы реализованы внутри, тем легче будет найти эффективное применение и не встретить неожиданные баги, которые сложно отследить. Два моих любимых примера, которые встречались не один раз, это возгласы: «Почему так долго?» при использовании хэш-таблиц. И второй пример — это флейк тестов при использовании сортировки.
Типичный пример 1
Дано: длинные строки примерно такой структуры: «{время}. {много информации о том, что произошло в этот момент времени}» (структура может отличаться). Для каждой строки нужно посчитать какое-то значение. Например: сколько раз ее просматривали, редактировали и т.д.
Программист решает использовать стандартный dictionary, HashTable, unordered_set, в зависимости от языка. Но «под капотом» — это и есть хэш-таблица.
Код написан, тесты проходят, апрув получили — мерджим и запускаем в продакшн.
И на проде получаем, что запрос исполняется долго, обновление данных так вообще происходит пару минут. Программист в растерянности и панике.
В чем проблема?
В том, что теоретически получение значения по хэшу в среднем занимает константное время работы. Но получение этого хэша от строки — линейно. И с большими строками это работает крайне паршиво. Это если не говорить о коллизиях, которые также могут возникать. В худшем случае, получение значения по хэшу занимает линейное время от размера хэш-таблицы.
Что делать?
Все зависит от конкретной задачи. Самое простое исправление в примере выше — это хранить хэш только от времени (считаем его уникальным), а остальную строку, при необходимости, как значение по этому ключу вместе с остальной нужной информацией. Может быть, выгоднее даже хранить данные в отсортированном виде и проходиться по массиву двоичным поиском. Например, если строки очень длинные, но довольно уникальные. Главное, это понимать и знать, как работает то, что вы используете, какой алгоритм и структуру оптимально выбрать под ваш случай.
Типичный пример 2
Программист достает данные из таблицы, модифицирует их и возвращает клиенту в отсортированном виде. Сортировка производится по ключу, который прислал клиент в запросе.
На первый взгляд, все просто. Вытаскиваем нужные данные. Модифицируем. Сортируем стандартным сортом, в который передаем свой компаратор, ключ и т. д. Если нет необходимости модифицировать, то отсортируем на этапе запроса.
Тесты написаны, код уже давно в мастере. Об этой задаче давно забыли, добавили новые поля в таблицу, клиент присылает запросы с другими ключами — сервер работает как часы. В один прекрасный момент начинают не проходить тесты при проверке задач, которые никак не связаны с этим участком кода. Другие программисты жмут перезапуск тестов, и со второй-третьей попытки тесты проходят. Разработчик думает, что ему не повезло, и в этот момент возникли проблемы с базой, отвалился докер-контейнер или другой инструментарий. Но это начинает происходить все чаще и чаще на одном и том же тесте. Что произошло?
Сортировка во многих языках программирования не гарантирует стабильность. То есть запустив ее два раза на одном и том же наборе элементов, результат не гарантирует тот же порядок элементов. Таким образом, сформировав тест, который отсортирован по нужному ключу после сортировки, порядок других элементов с совпадающим ключом может быть другим. И сравнение двух таких массивов не сработает, но вам может повезти: ключи, по которым производится сортировка, уникальные, и обнаруживается ошибка спустя месяцы после написания кода.
Что делать?
Сортировать по двум ключам: ключу, который нужен, и уникальному в структуре данных. Например, ID элемента таблицы. Тогда каждый раз результат будет одинаковым.
Также поможет использование стабильных сортировок. Например: stable_sort в С++, Enumerable.OrderBy в .Net, sorted в Python (после версии 2.2) или подобное на вашем любимом языке. Даже если стандартная библиотека не содержит стабильную сортировку, напишите сами.
Как итог, понимание, что Вы используете, поможет вам на таких этапах разработки:
- оценка сложности программы на начальном этапе;
- оценка количества необходимых мощностей и памяти;
- возможность оптимизации в зависимости от специфики продукта;
- не подгружать огромные библиотеки ради одного метода;
- «крутой» зеркальный фотоаппарат не сделает из вас фотографа.
Хочешь сделать хорошо — сделай это сам
К сожалению или к счастью, не все алгоритмы уже реализованы. Некоторые реализованные сложные алгоритмы требуют модификации или гибкости в использовании. Ниже приводятся некоторые примеры использования из жизни. Они будут видоизменены и немного упрощены для статьи. Но главные идеи и применения алгоритмов описаны.
Задача 1
Дано: набор пользователей, которые упорядочены по дате регистрации. Для группы людей, которые зарегистрировались в заданный временной промежуток, нужно уметь считать суммарное и максимальное количество взаимодействий с сервером.
Для этой задачи можно придумать большое количество решений в зависимости от вашей инфраструктуры, хранилища и других факторов. Одним из подходящих будет использование дерева отрезков (segment tree).
Количество пользователей — это величина, которая постоянно растет. К тому же, при большом количестве различных запросов даже на миллионе пользователей будут заметны потери скорости.
Дерево отрезков дает возможность обновлять данные за O(logN), получать показатели для последовательной группы людей тоже за О(logN). Да, нагрузка на память увеличилась за счет того, что нужно хранить два таких дерева (для максимума и для суммы), и они занимают в 4 раза больше места, чем массив с данными. Но в моем случае это было не критично.
Почему не использовать готовую реализацию?
Базовая версия пишется/ копируется менее чем за час. Настройка под себя же этой структуры данных из библиотеки потребовала больше ресурсов как для написания, так и для поддержания в будущем.
Планировалось, что могут потребоваться более сложные вещи вроде группового обновления данных. Например, при обнаружении подозрительной активности с аккаунтов, которые были зарегистрированы в одно время. Из доступных дополнений также возможны: получение порядковой статистики, сохранение предыдущих версий дерева.
Примитивное дерево отрезков для функции минимума
Результат
Как я знаю от бывших коллег, это работает и модифицируется до сегодняшнего дня. Хотя было написано меньше чем за день (вместе с тестами). Если бы в команде никто не слышал о таком алгоритме, то на его поиски и реализацию ушли бы недели.
Задача 2
Люди работают в большой корпорации. Необходимо оптимизировать бизнес-процессы и документооборот. У каждого сотрудника есть своя нагрузка, количество необходимых утверждений (подписей) для дальнейшей обработки документа/ товара. Нужно максимизировать эффективность и минимизировать время обработки и затраченные ресурсы.
Пример графа для поиска максимального потока
Решение
При решении схожей задачи у меня не было представления о линейной алгебре и транспортной задаче. Но я слышал об алгоритме Min Cost Max Flow.
По сути, каждого человека/ транспорт можно представить в виде вершины графа с показателями эффективности: количество обработанных единиц за время и затраты на них. Между вершинами есть последовательные взаимосвязи, которые известны.
С изменениями, но для решения этого применялся алгоритм поиска минимальной стоимости максимального потока.
Сомневаюсь, что данный алгоритм пригодится мне еще хоть один раз. Но он также интересен тем, что в базовом варианте объединяет три других: BFS, Форда-Фалкерсона и Белмана-Форда.
Результат
В свое время для меня это выглядело как шедевр. А в объединении с приятным UI, было еще и используемой вещью. Но проект завершил свое существование, а вместе с ним оборвалась жизнь и этого кода.
Задача 3. Разбор логов сервера
Дано: Файл логов 100 МБ+. Нужно наладить быстрый поиск по этому файлу. Слова и фразы поиска — это коды, тексты ошибок и ID пользователей (короткие строки).
Стандартные средства уже не удовлетворяли запросы проекта и нужно было придумать более быстрый способ. И снова помог алгоритм, который я видел до этого — Ахо-Корасик. Про результаты лучше всего расскажет график:
Результат
Это было не так давно, но есть подозрение, что эта реализация прослужит еще пару лет. Если инфраструктуру и процессы не изменят раньше.
Как я пришел к изучению алгоритмов и советы
Честно признаюсь, мне повезло. Я пришел в разработку и начал осваивать архитектурные и технические подходы после изучения алгоритмов и решения 1000+ задач на различных ресурсах. И мой путь выглядел примерно так: видишь задачу -> не знаешь, как решать -> изучаешь, реализовываешь, модифицируешь подходящий алгоритм.
Этот путь долгий и трудоемкий, особенно при совмещении с реальной работой. Но существуют ресурсы, которые помогают оптимизировать этот процесс.
При подготовке к прохождению интервью, два самых популярных ресурса — это:
- LeetCode. Тут собрано много задач и подборок от easy до hard уровня. Для каждой задачи доступен discuss, где люди делятся идеями решений и реализацией на различных языках.
- InterviewBit. Здесь задачи разделены по уровням и темам. Также можно установить количество дней до интервью и видеть свой прогресс. Плюс для каждой задачи представлены подсказки и решения.
Существуют также ресурсы, которые предлагают обучение в более игровой форме. Например: Codewars или Code in game.
Если же вы захотите перейти на следующий уровень, изучать продвинутые алгоритмы и решать связанные с ними задачи, то стоит взглянуть на соревновательные сайты, такие как Topcoder, Codechef и другие.
А также абсолютно всем советую ознакомиться с книгой «Алгоритмы. Построение и анализ» Томаса Кормена. В ней подробно описаны большинство популярных алгоритмов. К тому же, книга написана понятным языком и легко читается, как в оригинале, так и в переводе.
Выводы
Сейчас в работе вы можете не нуждаться в алгоритмах. Например, если вы верстаете страницы, разрабатываете API и имеете сотни других рутинных задач.
Когда вы работаете с архитектурой, хайлоадом, базами данных, то знания алгоритмов и структур данных вам однозначно пригодятся. Невозможно заниматься 3D-моделированием, машинным обучением, IoT-разработкой, не погружаясь в детали и нюансы алгоритмики. Любая отрасль, где нужна оптимизация памяти или времени, требует этого. Они помогут вам и в выборе архитектуры. Вы не сможете выбрать графовую базу данных для своего проекта, если не знаете, что такое граф.
Конечно, для начинающих разработчиков, которые хотят в кратчайшие сроки найти свою первую работу, лучшим вариантом будет выучить один язык и несколько фреймворков, и с третьего, пятого, двадцатого собеседования вы ее найдете. При продвижении в карьере, алгоритмы вам точно пригодятся.
Опытным разработчикам, которым на текущий момент не нужны знания подобного характера, могу сказать только одно: фундаментальные знания помогут вам найти более интересный проект, где нужно будет писать новый функционал, а не поддерживать и тащить на себе старый. Небольшая часть разработчиков в восторге от legacy-кода. А может вы узнаете о какой-то интересной для вас задаче и сможете улучшить существующее решение, создать свой продукт на его основе.
Алгоритмы и структуры данных помогут вам продвинуться в карьере. На конференции RunIT в Днепре, где я выступал с этой темой, человек в зале привел простой пример: «Однажды за то, что я сумел решить задачу о перемещении шахматного коня из одной клетки в другую за наименьшее количество шагов, мне подняли зарплату на 500 $». Чего и вам желаю.
