Алгоритмы и структуры данных
К текущему моменту я решил 250+ задач на алгоритмы и прошел несколько собеседований.
В этой статье я хочу раскрыть тему алгоритмов как являения и разобрать процесс решения на составляющие, плюс показать почему именно ТЫ сможешь в них преуспеть, и медленно перейти к оным на собеседованиях.
Зачем решать задачи на алгоритмы?
Споры о нужде алгоритмов не утихают до сих пор.
Одни с пеной у рта доказывают, что на работе в них нет никакого смысла, другие топят за улучшение алгоритмического мышления в решении вымышленных задач.
В действительности, решая алгоритмы, мы делаем следующее:
И часто ли вам на работе приходилось выполнять больше двух-трех пунктов из этого списка? Часто ли вы встречались с проблемами, для которых необходим долгий, вдумчивый анализ для составления сложного алгоритмически эффективного решения?
Итог. Если вам не нужно готовиться к алгоритмическим интервью и на работе не приходится писать ПО с нетривиальными алгоритмическими задачами, то нарешивать задачки вам явно не нужно.
Пример из жизни
Однако, это не значит, что знание основ вам никогда не понадобится. Пример из моей работы:
Дан массив каких то структур. Необходимо вызывать определенную функцию у каждого элемента этой структуры, после чего массив почистить. Код будет выглядеть примерно так:
container<Type> elems;
...
for (auto& elem : elems)
{
elem->Finalize();
}
elems.clear();Проблема заключается в том, что метод Finalize() может удалить элемент из elems при определенных условиях, и мы получим краш на изменении размера массива в range-based` цикле.
container<Types> elems;
...
void Type::Finalize()
{
...
if(...)
{
elems.remove(this);
}
}Простой подход для решения проблемы - скопировать исходный массив в другой, и пройтись по элементам копии.
На мой взгляд это неэффективно и некрасиво. Без опыта решения задач я бы так и поступил.
В итоге, лаконичное решение пришло через некоторое время:
container<Type> elems;
...
while (!elems.is_empty())
{
auto elem = elems.pop();
elem->Finalize()
}Вам может показаться этот пример глупым и очень простым. По сути так и есть, однако...
Матерые, опытные синьеры на моем проекте копировали массив.
Значит ли это, что решение не так очевидно...?
И это с учетом того, что алгоритмически сложные задачи у нас бывают очень редко.
Почему именно ты сможешь подготовиться к интервью
Когда я несколько месяцев назад впервые начал решать задачи, то обомлел от разнообразия и сложности этих задач. Казалось, что для подготовки нарешивать их нужно бесконечно.
Кроме того, единственное, что я читал это Грокаем Алгоритмы от Бхаргава А. Поэтому никакой академической подготовки у меня нет.
Правда заключается в том, что это разнообразие и сложность конечны, и чем больше вы нарешаете задач, тем больше паттернов вы будете знать, тем больше возможных комбинаций из паттернов сможете собрать и тем меньше очередная новая задача будет вас удивлять.
У меня, спустя 250 задач, при открытии очередной medium - hard задачи сразу всплывают знакомые паттерны, на которых строится та или иная задача.
Паттерны
Давайте на конкретных примерах.
Возьмем две на первый взгляд никак не связанные задачи: LRU Cache и Two Sum.
Поначалу, у новичка образуется каша в голове и он не знает как к задаче подступиться. Вместо размышлений, составления каких либо тестов сразу бросается писать какой-то код, стремясь избавиться от тотального непонимания и нагнетаемого страха.
В процессе он пробует разные варианты и еле-еле приходит к решению, которое вряд ли даже ложиться в базовые требования задачи.
Опытный алгоритмист на основании требований задачи сразу видит в ней какие-то паттерны.
Самый первый из них, исходя из требований в этих задачах - скорость поиска. Она должна быть константна, а значит тут подойдет только hash map в разных вариацих.
Второе - способ хранения данных.
В первой задаче нужна упорядоченность, которой нет в hash map.
Хорошо. Мы ее туда добавим, если будет хранить ноды связного списка, где каждая нода указывает на последующую внутри контейнера.
Во второй требуется такой способ хранения, который предполагал бы, что взяв какое либо число из массива, мы за константное время сможем понять, составляет ли оно с другим числом такую пару, сумма которых равна искомому.
Хорошо, будем хранить разность текущего и искомого. Если следующее число равно этой разнице, это эти числа образуют пару.
Таким образом, суммарно в этих задачах есть 4 паттерна - оба разделяют использование hash map для скорости поиска, только в первой требуется еще и связный список для контроля последовательности, а во второй специфический способ хранения для удобства поиска.
Имеются и другие способы решения, базирующиеся на других шаблонах.
Важно понимать, что взяв определенных шаблон, hash map в нашем случае, вы начинаете его развивать, собирая мозайку для решения. Проблемы возникают тогда, когда вы берете за основу изначально неверный паттерн, который в лучшем случае будет не самым оптимальным, в худшем - просто не даст пройти все тест кейсы.
Вам нужно научиться эти паттерны отсеивать на самом раннем этапе из возможных, но об этом ниже.
Тогда возникает закономерный вопрос:
А как тогда написать конечное решение, если оно состоит из множества шаблонов? Неуж-то перебирать их все?
И появляется не менее закономерный ответ:
- Тезис 1. В задачах Easy-Medium уровня не высокая глубина. 2-3 паттерна будет достаточно. И их придется подбирать.
- Тезис 2. Формирование идеи нужно устраивать не из всех паттернов. Если задача про тот же LRU Cache, вам может прийти в голову использовать stack или queue для формирования очередей, и это нормально, или начать с hash map и как то комбинировать с очередями. Вторая идея со временем отсеится и вы пойдете дальше.
Опытный алгоритмист эту идею быстро отсеит и не будет тратить слишком много времени. После чего возьмет следующую и после нее. Спустя некоторое время сортировки он начнет развивать ту, с hash map, в правильном направлении, прямо как ожидает интервьюер, накидывая на нее мяса в виде дополнительных возможных функциональностей и способов хранения данных.
Из этого следует простой вывод:
Чтобы эти шаблоны научиться применять, их нужно сначала несколько раз использовать и запомнить.
Тут возникает следующая ошибка: новички сидят за решением Easy-Medium задач несколько часов, пытаясь подобрать паттерн, о котором даже не знают.
Чтобы эту ошибку не допускать, я рекомендую отводить на задачу любого уровня максимум 45 минут. Этого с лихвой хватает для составляения решения и написания кода. Если вы не укладываетесь, значит вы ничего не придумаете и за 2 часа.
Собеседование
В первую очередь, на собеседовании задачу нужно не решать, а обсуждать.
Там редко спрашивают что то сложнее Medium, однако, случаи такие бывают.
Чаще всего, если задача easy-medium, то предполагается, что вы должны решить ее практически без подсказок и по сути самостоятельно.
Если вам выпадет Hard, то вероятнее всего интервьюер жаждет с вами побольше поговорить, увидеть как можно больше ваших попыток подобрать решение, и что не менее важно - это решение с интервьюером обсудить.
Резюмирую: вне зависимости от сложности задачи ваш план действий никак не меняется. Различия будут в количестве попыток для подбора шаблонов и суммарной длительности вашего с интервьюером диалога.
Для полноты понимания о чем я говорю очень рекомендую посмотреть лайв кодинг интервью в разные компании.
В грамотных сценариях на каждом ходу своего решения программист постоянно рассуждает вслух и спрашивает интервьюера, имеет ли его текущий подобранный паттерн смысл, или нет.
Очень часто, если интервьюер видит, что вы неплохо справляетесь, может самостоятельно помочь, указав на какую-то деталь, которую вы не заметили, или намекнуть, если застряли. И это нормально.
Как я уже сказал, самое главное на интервью это общаться, максимально открыто показывая, что происходит в вашей голове.
Заключение
Теперь давайте заключим, что нужно делать программисту, который решил сесть за подготовку к собеседованию.
- Минимальная инструментальная единица в задаче, с которой все начинается - это структуры данных. Знакомимся с их принципами работы по туториалам.
- Нам нужно запомнить определенные шаблоны, которые составляются из структур данных. Чтобы наша ассоциативная машина грамотно работала и связывала эти паттерны с конкретными задачами, грамотно их упаковывая в нашей памяти, мы будем решать задачи группами из определенных категорий. Сначала массивы и хэш-контейнеры, потом стэк, два указателя, бинарный/быстрый поиск и так далее. Тут можно ознакомиться с Road Map от NeetCode, или взять курс на AlgoExpert. Я использовал оба ресурса.
- Взяв очередную задачу из категории, сразу ставим таймер - ~45 минут. Если за 5-10 минут не выходит ничего придумать, достаем первые подсказки, чтобы хоть как-то продвинуть решение. В этом плане мне очень понравился AlgoExpert, который эмитирует процесс интервью, предоставляя 2-4 скрытые шпоры на случай застрявшего решения.
- Прорешав 100-150 задач нам потребуется опыт реальных собеседований. С этой целью ищем интервьера, принимая во внимание описанные мною ключевые моменты.
- Как только вы можете взять любую Medium задачу и с 80%-90% вероятностью ее решить, значит вы готовы для прохождения алгоритмических интевью. Поздравляю. Теперь можно подаваться на желанные вами вакансии.
Лично я на момент написания статьи решил 126 задач на Leetcode, и ровно столько же на AlgoExpert. Некоторые задачи были похожи, единицы были точной копией и большинство представляли из себя по сути уникальные кейсы.
В процессе подготовки я перед работой я нарешивал в среднем 2-3 Medium задачи или 3-6 Easy или 1 Hard. И так на протяжении трех с небольшим месяцев каждый день по 1.5 - 2 часа.
Надеюсь, вы что-то вынесли из этой статьи, и так же надеюсь, что вам потребуется потратить сильно меньше времени и сил для устройства на позицию мечты.