#How_to_заботать алгоритмы для карьеры Все слышали об история | Поступашки - Карьера

#How_to_заботать алгоритмы для карьеры

Все слышали об историях успеха ребят, которые прорешали 300-500 задач с литкода и получили работу мечты: Яндекс, FAANG и тд. Немало таких ребят и из наших учеников. Потому наш преподаватель Тимур составил подборку материалов, исходя из своего опыта и опыта своих учеников в прохождении собесов. Если же вам кажется, что один вы не справитесь, то приглашаем на наш курс по алгоритмам, где вас ждут авторские материалы, талантливый преподаватель и заботливый контроль.

Асимптотика алгоритмов
Первое, что нужно уметь это оценивать асимтотику алгоритмов, чтобы различать, какие алгоритмы лучше для решений той или иной задачи. На эту темы можно посмотреть лекций Андрея Станкевича в ЛКШ или найти в книге Олимпиадное программирование Антии Лааксонен 3 главу

Главная характеристика алгоритма, спросят везде

Теории чисел
Теоретическая часть.
НОД двух чисел за логарифм
Проверка на простоту числа за корень
Решето Эратосфена
Нахождения ответа по какому-то простому модулю. (Полезно будет знать малую теорему ферма)
Если никогда не писали нахождения НОД или проверку числа на простоту, то для начала решаем задачи с acmp из раздела "НОД и НОК", "Простые числа", "Целые числа". Обязательно нужно прорешать более сложные задачи на leetcode. Лучше набивать руку именно на средних по сложности задачах, ибо именно такие дают на собесах.

Обычно прям задачи на нахождения НОД или проверку на простоту числа вам не дают, но дают такие задачи в которых эти знания необходимо использовать. Особенно такое любят спрашивать при отборе в какие-то лаборатории, научные институты или в тот же ШАД.

Префиксные суммы и два указателя
Теория на префиксные суммы по ссылке. В качестве задач порешайте задачи A, B, D по peltorator контесты. И конечно же задачи с leetcode
Всю теорию на тему двух указателей с задачами можно найти по ссылке. Там есть простые и более сложные задачи. Для понимания достаточно решить хотя-бы 6 задач на эту тему.

При отборе в Яндекс, FAANG и подобное вам встретиться хотя бы одна задача на эти темы. Оно неудивительно, ибо для оптимизации решения нередко используются именно префиксные суммы/ два указателя.

Бинарный поиск
Теорию можно посмотреть также от Пашки в codeforces. Там же есть практические задачи. А также подойдут набор задач из этого списка leetcode. Некоторые задачи от сюда даже попадались на собесах зарубежных компаний.

Предыдущие два пункта обычно спрашивают на ds, ml, аналитика и тд, ибо принципы несложные, а что-то спрашивать на алго секции все равно нужно..

Графы
Для начало нужно разобраться какие виды графов существуют. Советую посмотреть в codeforces
Обязательно научиться писать обходы, такие как "Обход в ширину/глубину". После научиться находить кратчайшие пути в графах. Для этого есть старый добрый e-maxx и в книге Олимпиадноепрограммирование Антти Лааксонен можно посмотреть 7 главу. Для практики подойдут тренировки от СПбГУ, а также простые и средние задачи из leetcode

Жадные алгоритмы и динамическое программирование
Жадные алгоритмы можно прочувствовать только при решение задач.
В качестве теории по ДП можно посмотреть Андрея Станкевича в ЛКШ и почитать 6 главу в книге Олимпиадноепрограммирование Антти Лааксонен. Для практики по жадным алгоритмам советую. Для практики по стандартным задачам по ДП можно использовать acmp, а также leetcode

Структуры данных
Важные темы. Бинарные деревья. Кучи. Система непересекающихся множеств. Дерево отрезков, а также дерево фенвика.
Полезно будет знать о существование:
Красно-черные деревья.
Sqrt-декомпозиция
Из этого списка чаще всего встречаются БИНАРНЫЕ ДЕРЕВЬЯ.
Теорию по ДО (дерево отрезков) можно посмотреть у ПАШКИ там же есть и вторая часть.
И СНМ (Система непересекающихся множеств) по ссылки
Задачи с литкод
На бинарные деревья, Дерево отрезков (некоторые задачи можно решать и деревом фенвика).

Предыдущие два пункта просто обожают спрашивать разработчиков, но нередко такое попадается и остальным