Вот и долгожданный ролик по стажировкам в Касперовский. Вместе с Максимом разберемся во всех вопросах, связанных со стажировкой. Вышло много инсайдов и лайфхаков. Обязательно делимся с друзьями, ждем 10 тыс просмотров на ролике и выкладываем обзор VK.

Смотрим! Смотрим! https://www.youtube.com/watch?v=Cq2QiFj6y_g&t=1s

Самая сложная задача ШМР.

Решение:
Пусть dp[i] - максимальная сумма, которую можно заработать, если мы рассмотрели первые i букв в строке s.

Тогда как обновить dp[i] ?
- Для начало мы должны выделить подстроку конец, которой будет в i. Пусть эта подстрока [j, i] где j <= i.
Каким требованием должна удовлетворят переменная j ?
По условию задачи длина подотрезка должна быть между l и r отсюда выходит что нам подходят такие j, что l <= i - j + 1 <= r.
Ваша задача в подотрезке [j, j] быстро узнавать минимальную и максимальную букву. (вот не надо сейчас думать в сторону структур). Чтобы хранить min, max букву на подотрезке [j, i] нам достаточно завести две переменные и пока j сдвигается налево от i обновлять эти переменные. (подробнее смотрите на код).

Ну и наконец теперь мы можем обновлять dp[i].
dp[i] = max(dp[i], dp[j-1] + max-min)
Для тех кто не понял этот кусок, dp[j-1] + max-min:
-Здесь говорится, что вы берете оптимальный ответ на отрезке [0, j-1] и оптимальный ответ на отрезке [j, i] в котором ответ max-min.

Так как в задаче еще должны восстановить ответ, мы заводим массив from, где from[i] равен позиции j от которой обновилась dp[i].

Время работы алгоритма O(n^2).

Код в комментариях.

До отборочных в ШАД буквально 7 дней, товарищи, поэтому сегодня в ролике делюсь главным секретом, который подготовит вас к экзаменам за пару недель😎😎 Свои силы сможет попробовать каждый.

Смотрим! Смотрим! https://youtu.be/U7TgvUE3yqA

Вот и реально собеседование на стажера аналитика в Тинькофф. Во всю присылают приглосы, поэтому мониторим почту, товарищи, и смотрим в ролике, чего ждать от собеса.

Смотрим! Смотрим! https://www.youtube.com/watch?v=73cmSsEg2n8

Задача ШАР
Даются числа N и K, а затем массив a целых чисел длины N
Вам нужно найти такую позицию i в массиве а, что 90% всех чисел слева от позиции i меньше чем число a[i], но число i должно быть больше K.

Решение:
N было до 1e6 и решения использованием дерево отрезков или дерево фенвика не проходили по времени, так как код писать нужно на питоне.

Для решения этой задачи нам нужно научиться хранить для каждой позиции i девяноста процентов наименьших чисел слева от позиции i.
Представьте, что вы это сделали для позиции i, то есть у вас есть массив b с 90% наименьших чисел слева от позиции i.
Что происходит с массивом b, когда вы переходите с позиции i на позицию i + 1 ?
Вам нужно добавить число a[i] в массив и удалить несколько максимальных чисел из массива b, так чтобы длина массива b стала (i+1)*0.9.

А с этим нам поможет heap, единственное он не умеет удалять максимальные числа, а умеет удалять только минимальные, так что будем хранить числа со знаком минус!

Общий алгоритм:
Для начало добавим первые K чисел в heap со знаком минус.
После удалим need_delete = K / 10 максимальных чисел из heap, запомним, что мы удалили count_deleted = K/10 чисел.
Теперь начинаем рассматривать числа из массива a начиная с позиции K.
Если a[i] > -heap[0] это означает что число a[i] больше чем 90% чисел и мы нашли ответ.
Иначе мы добавляем в heap число -a[i] и удаляем максимальные числа из heap пока count_deleted не станет равным need_delete.
Время работы алгоритма O(nlogn).
Код в комментариях:

Вот и разбор первого этапа ШАД 2024 года! Обязательно делимся с друзьями, ждем 10 тыс просмотров и разбираем другой вариант. Пока другие варианты можно получить только на наших курсах.

Смотрим! Смотрим! https://www.youtube.com/watch?v=AS4c22KKlgY

Вот и разбор первого этапа ШАД 2024 года! Обязательно делимся с друзьями, ждем 6 тыс просмотров и разбираем следующий вариант. Пока другие варианты и разведку по остальным этапам можно получить только на наших курсах.

Смотрим! Смотрим! https://www.youtube.com/watch?v=bR2jza6gpyU

Вот и задание сегодняшней олимпиады.
Как прошло, товарищи?

Как всегда будет полезно прорешать все задания. Ничего необычного. Все на те темы, которые мы разбирали на наших курсах.

Задача с контеста Яндекс.

Решение:
Во первых заметим, что x[i] <= x[i + 1]. Задача сводится к тому, чтобы выбрать индексы i_1, i_2, ..., i_k, таким образом, что t[i_1] + t[i_2] + .... + t[i_k] + x[i_k] <= T, а также k-> max.

По факту, если бы мы знали до какой позиции Андрею нужно дойти (то есть i_k) то нам нужно было бы взять t[i_k] + x[i_k] и взять самые маленькие t слева от позиции i_k, таким образом чтобы сумма была <=T. Так как мы не знаем оптимальную позицию i_k то куда Андрею стоит идти, нам придется ее перебирать.

Давайте идти слева направо по позициям (то есть for i in range(n)) и предположим, что у вас есть оптимальный набор t-шок слева, я буду хранить их в multiset, (на питоне можно heap).
Пусть сумма оптимальных t-шок (чисел которые лежат в multiset) равна sum_T.
Тогда логично, когда вы в i-той позиции убирать из multiset максимальные числа до тех пор пока sum_T + x[i] > T (так как x[i] возрастают и нам незачем таскать за собой в следующие позиции ненужные t-щки).
Теперь мы оставили такой набор t-щик (замечу мы сделали не хуже для следующих позиций).
У нас 3 случая:
1) sum_T + t[i] + x[i] <= T
2) sum_T + t[i] <= T
3) максимальная t-щка в оптимальном набор больше чем t[i]
Рассмотрим все эти три случая по порядку и обновим ответ/оптимальный набор. (Подробнее смотрите код)

Время работы алгоритма O(NlogN).

Код и полное условие в комментариях.

Олимпиада ШАДа.

Вторая задача олимпиады. Полное условие с тестами оставлю в комментариях.

На плоскости расположены N различных окружностей, любые две либо не пересекаются, либо вложены.
Требуется найти количество подмножеств окружностей мощности K, таких, то их можно упорядочить в цепочку вложенных друг в друга окружностей.

Решение:
Давайте отсортируем окружности по возрастанию радиуса. То есть после сортировки получим r[i] <= r[j] для всех i < j.
В условии сказано, что окружности не пересекаются.

Давайте построим граф на этих окружностях.
Пусть окружности - это вершинки графа. Проведем ориентированное ребро от вершины i в вершину j если окружность j находится внутри i.

Ну такой граф неудобный, так как может содержаться циклы и излишний ребра, давайте лучше построим дерево.
И так построение дерева:
Как мы помним наши окружности отсортированы по возрастанию радиуса. Пусть мы в вершине i, тогда мы проводим ребро к вершине j, если j < i и окружность j находится внутри i, а также у вершины j нет предка.
Если вы будете проводить ребра именно таким образом, то получите дерево.

- А в чем преимущество дерева ?
- В том что если все поддерева вершины i находится строго внутри окружности i.

Теперь как посчитать ответ ?
Мы фиксируем вершинку дерева, пусть это вершина v. Давайте найдем все такие подмножества окружности содержащий v из которых можно построить вложенную цепочку.
Можно легко заметить, что мы должны просто взять подмножество предков вершины v размера k - 1.
Пусть количество предков вершины v равно, тогда в ответ добавляем C(count_parents, k - 1).

Время работы алгоритма O(N ^ 2)
Код в комментариях.

Вот и разбор экзамена ШАД 2024 года!

Смотрим! Смотрим! https://www.youtube.com/watch?v=SxjyPnXFxH0

Я в шоке! Академия Авито объявила набор... Мне стыдно, товарищи, что советовал поступать в этот содом, простите... Подобно Эдипу мне предстоит выколоть глаза и отправиться в изгнание. Прощайте! Оставляю вас Михаилу Абрамовичу. О том, что случилось в новом ролике..

Смотрим! Смотрим! https://www.youtube.com/watch?v=ZV6HX9AsHp8

Задача Яндекса.

Дается массив a из целых положительных чисел, а также число k. Найти максимальный по длине подотрезок в котором разница между максимальным и минимальным элементом будет не больше k.

Решение:
Наум, конечно, приходит два указателя. Это, кстати, хорошая идея.

И так, думаем в сторону двух указателей. Всё по шаблону, перебираем правый край отрезка 0 <= r < n, для каждого такого r будем искать оптимальный l, в котором разница максимального и минимального элемента не больше k.
Можно легко понять, что для каждого следующего r его оптимальный l будет не левее чем l для r - 1.

Осталось только быстро находить минимум и максимум на отрезке... Да, конечно, можно попытаться написать дерево отрезков, что позволит вам находить мин/макс за логарифм, но, к сожалению, задачу так не засчитают, нужно научиться за константу находить.

Для тех, кто не знал, можно с помощью монотонного стека находить мин/макс на отрезке, а в этой задаче нам понадобятся два монотонных стека, один для минимума, другой для максимума. Вот пример.

И так для решения - этой задачи нужно было хранить два стека. (ГПТ кстати хорошо решает такую задачу :))

Время работы алгоритма O(N)

Код в комментариях:

Задача AI-Masters.

Постройте алгоритм, который получает на вход дерево и за линейное время определяет, есть ли в нем совершенное паросочетание, то есть множество ребер, такое, что каждая вершина графа встречается ровно в одном ребре множества.

Решение:

Определение совершенного паросочетания дано в условии задачи.

Давайте подвесим дерево за вершину 1 и запустим dfs от этой вершины.
Стандартный dfs принимает два аргумента v, p - вершина в котором находимся и вершина от которой пришли в вершину v.
Но давайте еще передавать булеву переменную bool_took, которая равна true если вершина взята в паросочетание и false иначе.
Таким образом дфс выглядит следующим образом dfs(int v, int p, int bool_took), наша функция вернет true если поддерво вершины v при условии bool_took, можно сделать совершенным паросочетанием.

Вот мы вошли в функцию dfs, что мы должны сделать если bool_took = false и что мы должны сделать если bool_took = true ?

- Если bool_took = true нужно запустить dfs от всех детей вершины v с параметром bool_took = false и если все вызовы dfs вернули true то мы в свою очередь тоже можем вернуть true.

- Если bool_took = false нужно выбрать какого-то ребенка вершины v и взять их в паросочетание, пусть эта вершина u, тогда если dfs(u, v, true) вернул true и dfs(to, v, false) вернул true для всех детей to не равным u мы можем спокойно возвращать true.

Время работы алгоритма O(N).

Код с комментариями в описание.

Задача ШАДа.

Эта задача была на собеседовании в ШАД в 2023 году. Я считаю задача одна из коварных по сравнению с остальными, подумайте над этой задачей и думаю вы поймете о чем я.

Задача:
Дается массив из целых чисел, вернуть True, если можно за один swap двух чисел сделать массив отсортированным (по возрастанию или по убыванию). В массиве могут быть повторы.

Решение: (Настоятельно рекомендую перед этим подумать)

Будем предполагать, что в массиве нет повторов. (вы можете убрать подряд идущие элементы из массива за O(n) двумя указателями)


Пойдем с конца, возьмем отсортированный массив по возрастанию и сделаем swap двух чисел, как будет выглядит массив (например если рисовать график) ?

В таком случае у нас сначала элементы возрастают, а потом резко падает и снова возрастает, а еще раз падает и после опять возрастает.
Если же были свапнуты две соседние элементы, тогда у нас массив сначала возрастает, потом падает и после опять начинает возрастать.

Назовем позиции i особенными если, a[i - 1] > a[i].

-Если особенных позиций больше 2 ответ False.

-Если такой позиции ровно 1, то вы должны сделать swap чисел a[i] и a[i - 1] и проверяете что массив отсортирован по возрастнанию.

-Если таких позицй ровно 2 (пусть это i1 и i2) то вы должны сделать swap чисел a[i1 - 1], a[i2] после проверить, что массив стал отсортированный.


Мы упустили случай, когда массив изначально был отсортирован по убыванию. Но у нас есть решение (функция) выше, нам надо вызывать ровно это же решение, умножив все элементы массива на -1.

Время работы алгоритма O(n).

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

https://news.1rj.ru/str/algoses/6
https://news.1rj.ru/str/algoses/12
https://news.1rj.ru/str/algoses/29
https://news.1rj.ru/str/algoses/33
https://news.1rj.ru/str/algoses/37
https://news.1rj.ru/str/algoses/90
https://news.1rj.ru/str/algoses/95

Алгоритмы в Ai-Masters

AI Masters — это двухгодичный курс, который можно сравнить с ШАД. Обучение на курсах AI Masters действительно качественное, и это прекрасная возможность получить дополнительные полезные знания за два года.

Подробный пост о этапах поступление написано здесь.

В Ai-Masters алгоритмы встретите в основном на экзамене, и там будет всего одна задача. Эта задача значительно отличается от тех, с которыми можно столкнуться на собеседованиях или в ШАД (за исключением олимпиады ШАД, которую запустили в 2024 году). Также алгоритмы будут на собесе, но по опыту прошлых лет там простетские вопросы в духе: какие знаете сортировки, посчитайте сложность алгоритма.

Если у вас есть опыт участия в олимпиадах по программированию, то эти задачи покажутся вам несложными. Они примерно соответствуют второй задаче ВсОШ.

Мне кажется, что если у вас есть пробелы по математике, то лучше сосредоточиться именно на ней. Многие люди спокойно поступают не решая задачу по алгоритмам, но знать алгоритмы важно для того чтобы успешно закрыть курс по алгоритмам, так что ботать алгоритмы стоит, но не для того чтобы решить эту единственную задачу, а для того чтобы была база и заодно прокачать скилы для успешного прохождения собесов.

С примером и разбором одной из задач можно ознакомиться здесь.

И так как все таки подготовиться.
Как уже сказал вам необходима прочная база. Подготовка к алгоритмическому собеседованию или в ШАД отлично подходит. Подробнее про подготовку можно почитать здесь и здесь

Теперь готовимся к AI-Masters (кстати эта подготовка вам поможет к собесу и в какую-то хорошую HFT компанию).

Так как задачи по алгоритмам попадаются разные, то нужно перестраховаться и прокачать алгоритмы по следующим темам.
* Многомерное ДП и дп по подмножествам
* Дп по поддеревьям
* Теория игр
* Эйлерев путь
* Планарные графы, независимое множества (графы)
* Структуры данных (ДО, Фенвик, Sparce Table)
* Хеши

Также рекомендую решать региональные олимпиады школьников - первых двух задач будет достаточно.

Все темы выше проходят в стандартном курсе по алгоритмам, например в МФТИ, лекции которые можно найти в ютубе.
Задачи на эти темы спокойно можно найти в informatics.

Задача Яндекса.
Обязательно реши эту задачу если идешь в Яндекс.

Не могу не поделится задачей, которую крутят уже пятый раз подряд.
Задача называется Permutation in String.
В задаче говорится, что дается две строки s1 и s2 и нужно вернуть true если в s2 существует подстрока, которая является перестановкой строки s1.

Единственное собеседующий скажет что в строках могут быть абсолютно любые символы (то есть не только латинские буквы)

Решение:
Первое решение, которое попросят улучшить:
Давайте в словаре d1 посчитаем то сколько раз встречается каждая буква в s1.
Теперь наша задача, найти такой i, что Count(s2[i, i + len(s1) - 1]) = d1.
Для этого мы могли бы хранить второй словарь d2 где будем хранить вхождения букв на подотрезке длины len(s1) и обновлять значения ключей (делаем +1 и -1 к буквам s[i] и s2[i - len(s1)] соответственно)

Сложность такого алгоритма O(n * min(len(s1), m) где m - количество различных букв в строках.
Вы могли подумать откуда тут произведение ?
Произведение возникает из за того что мы на каждом шагу сравниваем две хеш-тиблицы.

Второе решение:
Обойдемся только одной хеш таблицей, чтобы не сравнивать на каждом шаге две хеш таблицы как мы это делали выше.
Посчитаем словарь d1 также как и выше для строки s1.
Теперь проходится по строке s2 окошкой длины len(s1) и мы когда делаем -1 и +1 для букв s2[i] и s2[i - len(s1)] соответственно, таким образом храня в словаре разницу!
Когда значения какого-то ключа обнулилось мы должны удалить этот ключ.
Когда словарь становится пустым (то есть len(d1) == 0) мы нашли нужный подотрезок.
Сложность алгоритма O(n)

Код в комментариях.

Задача Яндекса.

Дается N пар чисел a_i, b_i.
Вы строите N отрезков, где концы i-того отрезка находятся в (a_i, 0) и (1, b_i).
Найти количество отрезков этого множества, которые не пересекаются с другими отрезками.

Например
a = [1, 2, 3, 4, 5]
b = [4, 5, 1, 5, 6]
Ответ 1
Только последний отрезок не пересекается.

Решение:
Давайте отсортируем отрезке по координате a_i.
Теперь подумаем, когда отрезок (a_i, 0), (1, b_i) пересекается с другим отрезком j.
У нас два варианта пересечения
1) a_j <= a_i and b_j >= b_i
2) a_j >= a_i and b_j <= b_i

Пусть мы в i-той позиции, так как мы отсортировали все по a нас интересует максимальный b_j. Максимальный b_j можно хранить в отдельной переменной во время обхода обновляя. Таким образом мы должны просто проверить правда ли max_b >= b_i.

Аналогично давайте пройдемся справа налево, но уже будем хранить минимальный b справа. Для каждой позиции i проверяем min_b <= b_i.

Асимптотика O(N logN).

Код в комментариях.

Академия Бэкенда Тинькофф

Бесплатная образовательная программу по бэкенд-разработке. Длительность курса -1.5 года.
Обучение будет проходить по 4 направлением.
Java, Golang, Python, Scala.

С программой Академии бэкенда можно ознакомиться здесь. Конкурировать с такой программой может только ШАД по направлению инфраструктура больших данных.
Чего только стоит "Компьютерные сети", "Асинхронный обмен сообщениями", "Балансировка нагрузки", SRE курс. Не каждый опытный разработчик знает такие технологии.

Первый семестр не такой крутой, а больше нацелен, чтобы сравнить всех по знаниям и дать хорошую базу в разработке.
Второй семестр действительно крутой на самостоятельное изучения, которых вы потратите много лет. А если вы хотите стать крутым разработчиком, то знания которые дают на втором семестре must have.
SRE курс - курс достаточно короткий, в этом плане курс ШАДа намного сильнее, но будем честны, знания в SRE курсы вы не можете спокойно получить в интернете. Очень мало практических заданий и материалов.

Также нужно понимать, что это Тинькофф и программа бесплатная, значит велик шанс столкнуться с некоторым количеством кринжа. Например, ручная проверка всех ДЗ: понятно, что кураторам никто особо не платит, у них своих дел куча, поэтому ревьюить особо не будут. Или например препод отказывается делать записи занятий, мол их должны посещать. Или не любит, когда к нему пишут в тг аккаунты без реальных имен и фамилий) Про порой мало качественный материал, наверное, и говорить не стоит: опять же у преподавателей особо мотивации нет, вдобавок на последние занятия никто обычно не ходит.

Кому подходит Академия ?
-Отлично подходит для тех кто уже работает бэкенд разработчиком и хочет быстро апгрейдить свои знания, и сильно повысить зарплату. Занятость спокойно позволяет совмещать учебу и работу.

-Для студентов вуза с плохим программированием. К сожалению во многих вузах нет курса по разработке... Академия является отличной возможностью найти хорошую работаю по окончанию универа.

-Для тех кто решил поменять стэк/направление.


Поступление.
-Заполнить анкету до 22 июля. Как заполнить смотрим здесь.
-Написать 4-5 часовой контест по алгоритмам. Кстати подготовиться к нему поможет наш курс по алгоритмам.
-Языковая секция: вам предложат практическое задание, которое нужно выполнить на языке программирования, выбранном для курса.

Пример 2023 года по алгоритмическому контесту. Задачи чуть легче чем отбор на стажировку.
Пример 2023 года языковой секции на GO.

Отбор действительно непростой. С одной стороны вы должны знать хорошо алгоритмы, а с другой уже иметь опыт в разработке. Конкуренция высокая. Только не переусердствуйте с анкетой, а то вдруг организаторы подумают, что вы слишком круты для них и уже все знаете, откажут (такие случаи были).

Но пробовать однозначно стоит!

Таблица задач с алго собесов Яндекса со всей актуальной информацией: ссылка на leetcode, частота, процентов принятия.
Именно эти задачи будут подробно разобраны на нашем предстоящем курсе по алгоритмам (код + видео) как бонус!

Яндекс наверное самая популярная компания, где открыта куча вакансий от стажера до лида, потому будем активно развивать эту отдельную страничку на нашем сайте. Обязательно делитесь табличкой с друзьями, будем активно дополнять и расширять, мест в Яндексе хватит на всех!

Задача Яндекса.
Дается строка, найти наибольший палиндромную подстроку.

Давно такая задача не встречалась на собесах, но недавно дали на собесе в яндекс.
Решение:

Наверное самое тупое решение - это зафиксировать длину подотрезка, пусть это число len. Теперь надо перебрать начало отрезка длины len, то есть зафиксировать [i, i + len - 1]. После нужно проверить правда ли этот подотрезок палиндром. Такое решение займет O(n^3) времени.

Скорее всего после такого решения вас не позовут дальше.....
Теперь обсудим решение, которое примут.
Переберем длину подотрезка len, после переберем начало подотрезка.
То есть зафиксировав len и i, мы получим отрезок [i, i + len - 1]. Остается вопрос, а как узнать правда ли подотрезок палиндром.
Во первых необходимо, что буквы s[i] и s[i + len - 1] были равны (иначе подотрезок точно не палиндром)
Во вторых нам важно чтобы подотрезок [i + 1, i + len - 2] был палиндром.
Если мы рассматриваем подотрезки по возрастанию длин (то есть по len), то по факту информацию о том, что подотрезок [i + 1, i + len - 2] является палиндромом, мы уже давно посчитали.
Пусть dp[l][r] = 1 если отрезок [l, r] палиндром.
В таком случае мы говорим, что dp[i][i + len - 1] = 1, если s[i] == s[i + len - 1] и dp[i + 1][i + len - 2] = 1.

Время работы алгоритма O(n^2).

Код в комментариях.

Эту задачу видел в Yandex Leetcode. Так что, если вы готовитесь к собеседованию, то имеет смысл прорешать Yandex Leetcode.

Также мы запускаем два курса по алгоритмам.
Если задачи на БП, два указателя, одномерные дпшки для тебя простые, то на продвинутом курсе по алгоритмам мы прорешаем ~200 задач на БОР, ДП по поддеревьям, игры и стратегии, bit manipulation.....

Если ты новичок в алгоритмах и хочешь хорошенько подтянуть за лето алгоритмы то тебе стоит взять основной курс по алгоритмам.