Сколько задач нужно решить? Есть примерно 20 основных тем, список на этой странице. В каждой теме для закрепления нужно решить 15-20 задач, что дает 300-400 задач всего. На самом литкоде более 3000 задач, но их все решать точно не надо.
Сколько времени это занимает? Если решать по 8-12 задач в неделю, то от 6 до 12 месяцев. Это примерно тот же объем, который разбирают студенты-программисты на первом курсе в течение двух семестров.
В каком порядке решать задачи? Я рекомендую разбирать задачи по отдельным темам. Сами темы более-менее независимы, поэтому разбирать можно практически в любом порядке.
Это темы, которые мы разбираем для подготовки к собеседованиях. Практическая часть на 100% построена на программе из литкода. Если сравнивать с вузовской программой, то это примерно 70% от курса по алгоритмам за первые два семестра. Этого достаточно, чтобы проходить собеседоваия в FAANG.
Мы начинаем с префиксных сумм, потому что изначально в этой теме не требуется знать ничего, кроме массивов, а оценки сложности возникают из обычных циклов for: O(1), O(n), O(n²). В более сложных задачах подключается использование словаря (hashmap).
Смежная тема — метод сканирующей прямой, где обычно нужно отсортировать какие-то отрезки. Здесь мы не обсуждаем, почему сортировка работает за O(n×log₂n), а просто ее использем.
Бинарный поиск реализуется всегда один алгоритмом, отрабатываем его на разных задачах, обсуждаем, откуда берется O(log₂n). Бинарный поиск — это инструмент, он может понадобиться в следующих темах.
Обсуждаем природу стека, амортизированную сложность, реализуем очередь через стек.
Помимо базовых задачек, где буквально в условии речь идет про стек, разбираем отельные подтемы: момнотонный стек, парсинг выражений, задачи на правильные скобочные последовательности.
Здесь мы первый раз сталкиваемся с рекурсией. Обычно люди думают, что у них проблема с бинарными деревьями, но на практике трудности с рекурсией. Естественным образом при обходе бинарных деревьев взникает (обход в ширину) dfs. Разбираем два подхода к решениею задач: рекурсивный и спомощью стека.
Дерево отрезков является примером complete binary tree, соотвественно, для него работают все подходы из задач про бинарные деревья.
Еще одним примером complete binary tree является куча. Мы реализуем кучу и решаем разные задачи, где куча используется. В основном это задачи в одно действие, где просто нужно понять, что нужна куча. Далее куча будет использоваться уже как инструмент.
Продолжение dfs из бинарных деревьев. Главное отличие, что теперь в графах появляются циклы. Рассматриваем две категории задач: графы, заданные двумерными массивами, и классические графы, которые нужно собрать из входных данных самостоятельно. Еще одно развитие dfs — топологическая сортировка.
На обход в ширину (bfs) гораздо меньше задач, чем на dfs. Поэтому разбираем те задачи, где bfs удобнее и проще. С использованием кучи реализуем алгорим Дейкстры.
Решаем задачи на графы, которые удобнее решать через систему непересекающихся множеств.
Еще один подход к рекурсии — обход виртуальных деревьев. Если в бинарных деревьях мы обходиои существующую структуру данных, то в бэктрэкинге возникает дерево вариантов, по которому мы ходим решая задачу.
На самом деле здесь разбираются обычные задачи на рекурсию. Единственная тонкость, что для оптимизации по времени необходимо кэшировать результаты работы функций. Если изменить порядок заполнения кэша, то возникает подход, который назвается динамическое программирование.
Рассматриваем три группы задач: одномерное ДП, ДП на двумерных массивах (когда масив дан по условию) и двумерное ДП.
По большей части задачи на односвязные списки легко решаются через рекурсию, и после предыдущих их решать не очень сложно. При этом есть набор других полезных приемов: быстрый и медленный указатели, dummy node и другие.
Также реализуем LRU и LFU кэши с использованием двусвязных списков.
Еще одна тема про два указателя. Простое sliding window — когда ширина окна фиксированная. Сложное sliding window — когда правый указатель двигается каждый раз на один элемент, а левый указатель догоняет его с помощью вложенного цикла.
Зонтичный термин «два укзателя» включает в себя и бинарный поиск, и быстрый/медленный указатели, и sliding window. Это все разбирается в предыдущих темах. Здесь мы в основном разбираем ситуации, когда указатели идут с двух сторон или когда указатели указывают на разные массивы.
Heap sort реализуется в разделе про кучу. Здесь разбираются merge sort и задачи, основанные на этой идеи. А также quick sort и quick select.
Разбираем задачи, где требуется доказать, что решение корректное. Сложность обычно не в решении, а в объяснении. Оставляем на самый конец, потому что в начале обучению люди не хотят слышать про то, что решение нужно обосновывать, даже если оно прошло все тесты на литкоде.