Ниже я привожу материалы, что я использовал для подготовки к собеседованиям по алгоритмам в FAANG.
Для начала вот самая полезная книга для подготовки к собеседованиям
- Cracking the Coding Interview: 189 Programming Questions and Solutions 6th Edition https://www.amazon.com/Cracking-Coding-Interview-6th-Edition/dp/0984782850?SubscriptionId=0ENGV10E9K9QDNSJ5C82&tag=care02-20&linkCode=xm2&camp=2025&creative=165953&creativeASIN=0984782850
Ищи последнюю редакцию.
- Самая короткая из полезных книг Алгоритмы С. Дасгупта, Х. Пападимитриу, У. Вазирани https://www.ozon.ru/context/detail/id/27676529/
- Онлайн задачники
- https://www.hackerrank.com/ тут есть Interview Preparation Kit, который можно прорешать, с объяснениями
- https://leetcode.com/ задачник с решениями Если освоишь книгу, Interview Preparation Kit и решишь задачек 100 (разных уровней), то считай, что база у тебя какая то будет.
Самая полезная из всех книг по алгоритмам, что я читал, очень хорошо дополнена курсами.
Седжвик https://algs4.cs.princeton.edu/home/ (http://www.ozon.ru/context/detail/id/18319699/)
Курсы по Седжвику (англ) от курсеры из 2 частей
- Скиена http://www.ozon.ru/context/detail/id/6290126/ - Полезно для поннимания, как выбрать алгоритм для задачи
- Кормен http://www.ozon.ru/context/detail/id/2429691/ - сложно и долго, только для специалистов по алгоритмам, содержит много теории, не является обязательной к прочтению.
Онлайн русские
- Алгоритмы: теория и практика. Методы https://stepik.org/course/217
- Алгоритмы: теория и практика. Структуры данных https://stepik.org/course/1547
Мне понравились видосы http://rutracker.org/forum/viewtopic.php?t=3994045 - автор и содержание то же, что на степике, только тут одни видосы, без презентаций, задач и тестов.
Можно порешать - потренироваться на задачках разной сложности. Я юзал вот эти (в порядке приоритета)
- Big-O notation
- Сортировки, пару простых квадратичных, пару за NLogN (обычно это Сортировка вставками, пузырьком, слиянием и быстрая сортировка). Уметь закодить и знать сложность и когда какую применять. Допольнительно к этому я смотрел сортировки кучей, Шелла, подсчетом, Radix сортировки типа LSD/MSD
- Хеш таблицы, варианты имплементации, время работы операций. Быть способным написать свою примитивную, но работающую хеш таблицу
- Деревья, ваианты обхода, n-арные деревья, trie - деревья, сбалансированные деревья поиска (то есть хотя бы знать что за, например, красно-черное древо / AVL / Сплей деревья, время работы операций и зачем вообще балансировать деревья). Никто не попросит тебя это имплементировать, но надо знать что это, зачем это и как быстро это работает и за счет чего оно так быстро работает.
- Варианты обхода деревьев / графов, например BFS/DFS/PreOrder/InOrder/PostOrder - знать как имплементировать и что и когда используется.
- Графы - must know, что такое, какие варианты представления в памяти, обходы графов (выше уже писал про DFS/BFS), сложность (время) на операции обхода графа
- Остальные структуры данных, типа Стеки / Очереди / Деки / Связанные списки / Множества / Кучи и прочке.
- NP задачи, что такое, как понять, что решаешь NP задачу, как их решать
Также теорию надо закреплять практикой, необходимо решать задачи по каждой теме. Чтобы быть на более-менее нормальном уровне, нужно прорешать минимум задач 100, но желательно как можно больше.