Алгоритмы - Собеседования, Олимпиады, ШАД

Задача с собеседования в TCS

Дан массив nums, состоящий из различных чисел в диапазоне от 0 до n. Верните единственное число из диапазона, отсутствующее в массиве.

Follow up: можете ли вы реализовать решение с использованием лишь O(1) дополнительной памяти и временной сложностью O(n)?

Пример 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n=3, так как в массиве три числа; таким образом, все числа находятся в диапазоне [0, 3]. Число 2 отсутствует в этом диапазоне, поскольку его нет в массиве nums.

Пример 2:
Input: nums = [0,1]
Output: 2
Explanation: n=2, так как в массиве 2 числа; таким образом, все числа находятся в диапазоне [0, 2]. Число 2 отсутствует в этом диапазоне, поскольку его нет в массиве nums.

Пример 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n=9, так как в массиве 9 чисел; таким образом, все числа находятся в диапазоне [0, 9]. Число 8 отсутствует в этом диапазоне, поскольку его нет в массиве nums.

Ограничения:
n == nums.length
1 <= n <= 10⁴
0 <= nums[i] <= n
Все числа в nums уникальны.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задача может быть решена арифметическим способом: подсчитываем сумму всех чисел диапазона от 0 до n и вычитаем из неё сумму эл-тов входного массива - разница равняется отсутствующему числу.

Предлагаю разобрать более интересный вариант решения с помощью побитового оператора XOR (исключающего ИЛИ), сравнивающего два бита:
- если биты одинаковые -> 0
- если биты разные -> 1

Применяем XOR для "обнуления" повторяющихся значений из массива nums и полного набора чисел диапазона от 0 до n, используя свойство: a ^ a = 0. Отсутствующее число встретится только один раз и останется в результате по свойству a ^ 0 = a. Предварительная сортировка массива не требуется, так как a ^ b = b ^ a.
- проходим циклом по числам от 0 до n, накапливая XOR в res;
- проходим циклом по массиву nums, также накапливая XOR;
- возвращаем res.

Сложность
O(n) - по времени (проходим двумя циклами по n элементам)
O(1) - по памяти (храним только одну переменную res)

Код
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
res = 0

for i in range(n + 1):
res ^= i

for num in nums:
res ^= num

return res

@algoses

Разбор контеста на стажировку в Яндекс за подписку!

Чтобы получить разбор:
➡️Подпишитесь на нас в запрещенной странице тут
➡️Поставьте «+» в комментариях под последней каруселью тут
➡️После этого бот пришлёт вам материал в директ

Внутри будет разбор контеста и заданий, которые помогут подготовиться к отбору в Яндекс

Задача с собеседования в TCS

Дана строка s, верните true, если возможно разделить её на 3 непустые палиндромные подстроки. В противном случае верните false.
Строка называется палиндромом, если в перевёрнутом виде она остаётся той же самой строкой.

Пример 1:
Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", все три подстроки являются палиндромами.

Пример 2:
Input: s = "bcbddxy"
Output: false
Explanation: s нельзя разделить на 3 палиндрома.

Ограничения:
3 <= s.length <= 2000
s состоит только из строчных английских букв.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задача помечена тегом "Dynamic Programming". Реализуем восходящее dp для проверки подстроки на палиндромность: заполняем таблицу от коротких подстрок к длинным, используя результаты для маленьких подстрок при вычислении больших. Запоминаем булево значение для каждой пары (i, j) и используем для получения ответа за O(1):

- Создаём таблицу размером n * n, заполненную False, где dp[i][j] - ответ, является ли подстрока от индекса i до j палиндромом;
- Заполняем таблицу вложенным циклом, двигаясь переменной i от конца строки к началу, а переменной j - от i вправо, строя подстроки по возрастанию длины. Таким образом, направление i и j гарантирует, что когда вычисляем dp[i][j], ответ для середины подстроки (dp[i+1][j-1]) уже готов.
- Проверяем подстроку на палиндромность:
Если крайние символы равны (s[i] == s[j]), то подстрока является палиндромом при выполнении хотя бы одного из двух условий:
- подстрока состоит из одного или двух символов (j - i <= 1) => подстрока - палиндром;
- внутренняя часть подстроки (dp[i+1][j-1]) - палиндром => вся подстрока - палиндром, так как крайние символы равны.

Теперь имея результаты табличных вычислений, перебираем две точки разреза, которые делят строку на три части: s[0..i] + s[i+1..j] + s[j+1..n-1]
i - индекс конца первого палиндрома
j - индекс конца второго палиндрома
Проходим внешним циклом i от 0, оставляя как минимум по одному символу для второго и третьего палиндромов:
- если префикс (dp[0][i]) - палиндром, переходим ко внутреннему циклу от i+1 до предпоследнего индекса (оставляем хотя бы один символ для третьего палиндрома):
- если второй отрезок - палиндром и третий отрезок - палиндром => можно разбить на 3 палиндрома => возвращаем True.
Иначе возвращаем False.

Сложность
O(n^2) - по времени (строим дп-таблицу за n^2, перебираем разрезы за n^2)
O(n^2) - по памяти (храним дп-таблицу)

Код
class Solution:
def checkPartitioning(self, s: str) -> bool:
n = len(s)

dp = [[False] * n for _ in range(n)]

for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j]:
dp[i][j] = (j - i <= 1) or dp[i+1][j-1]

for i in range(n - 2):
if dp[0][i]:
for j in range(i + 1, n - 1):
if dp[i + 1][j] and dp[j + 1][n - 1]:
return True

return False

@algoses

Уточнил у кандидата работал ли он со скоринговыми моделями как "Ясасу Бибу" и "Цист Яна". Ответ убил.

https://youtube.com/shorts/ccNWpP5grzg

Участвуй в алгоритмическом треке всероссийского ИТ-чемпионата МТС True Tech Champ 2026. Призовой фонд 2 750 000 рублей.

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

Решай задачи разного уровня сложности: от базовых до тех, что проверяют скорость мышления и умение оптимизировать решения за ограниченное время. В финале сильнейшие участники со всей страны сразятся в лайв-кодинге за призовой фонд 2 750 000 рублей.

Финал — 22 октября в МТС Live Холл. Масштабный финал объединит соревнования, выступления хедлайнеров, доклады спикеров и активности для всех гостей мероприятия.

Регистрируйся до 27 сентября.

Задача с собеседования в TCS

Дан целочисленный массив nums. Изначально вы находитесь на первом индексе массива, а каждый элемент массива представляет максимальную длину прыжка из этой позиции. Верните true, если вы можете достичь последнего индекса, или false в противном случае.

Пример 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Прыгаем на 1 шаг с индекса 0 на 1, а затем — на 3 шага к последнему индексу.

Пример 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: Вы всегда будете оказываться на индексе 3. Максимальная длина прыжка равно 0, из-за чего добраться до последнего индекса невозможно.

Ограничения:
1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁵

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Используем жадный алгоритм: максимальная достижимая позиция является локальным оптимумом; нам не нужно выбирать, на сколько позиций стоит прыгнуть, а только знать - какой самый дальний индекс можем достичь на текущей итерации.

max_reach - самый дальний индекс, до которого можем допрыгнуть; инициализируем, как 0, так как начинаем с индекса 0.

Проходим по массиву nums (i - индекс, на который хотим прыгнуть на текущей итерации):
- Если i больше значения max_reach: мы застряли и не можем достичь проверяемой позиции -> достичь конца массива невозможно, возвращаем False;
- Иначе, если можем достичь индекса i: из текущей позиции можно прыгнуть на nums[i] шагов, то есть возможно достичь индекса (i + nums[i]). Сравниваем прошлый максимум доступной нам дальности с новым, обновляя max_reach.

Если удалось пройти от начала до конца массива, возвращаем True.

Сложность
O(n) - по времени (один раз проходим по массиву длиной n)
O(1) - по памяти (храним только одну переменную max_reach)

Код
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach = 0

for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])

return True

@algoses

Для тех кто хочет прокачаться в DS

Качественные материалы и подборки бывают не только на нашем канале! Для тех, кто хочет разобраться во всех этих бустингах, пресижн и реколл, советую заглянуть в канал @asisakov_channel и прочитать тот самый роудмап по вкатыванию в Data Science.

Автор канала Александр руководит командой внедрения AI-агентов в Яндекс Лавке 🛒, а в свободное время в блоге пишет про ML, агентов, софты и свою жизнь

Что рекомендую почитать на канале:

1. Грандиозная подборка по собесам
2. Как заботать SQL?
3. Как понять теорвер?
4. Как упороться в статистику?
5. Как заботать математику для Data Science?

Ну и вишенка на канале - есть задачи и мемы, так что всё в лучших традициях авторского блога. Подписывайся, чтобы не потерять @asisakov_channel

Товарищи, Поступашкам нужны контент мейкеры по ДС-МЛ. Если вы творческая личность, вам нравится писать посты/ придумывать идеи для контента, то обязательно пишите @vice22821. Оплата сдельная, ориентировочно за один пост от 2 тыс до 15 тыс рублей.

Обязательно делитесь с ребятами, которым это может быть интересно.

Выкладываем задания Т-Академии и Т-Интенсива

Товарищи, прямо сейчас Т-Банк набирает участников на программы по аналитике и разработке. Задания уже выложены здесь.
Мы разберём вступительные испытания на карьерных курсах — выбирайте направление и смотрите, какой курс поможет подготовиться:

⭐️Т-Академия
— Разработка ПО: программирование
Разбор экзамена будет на «Бэкенд Старт» и «Алгоритмы Старт»
Дедлайн: 31 июля

— Продуктовая аналитика: математика и SQL
Разбор экзамена будет на «Аналитика Старт»
Дедлайн: 31 июля

⭐️Т-Интенсив
— Риск-аналитика: математика и программирование
Разбор экзамена будет на «ML Старт»
Дедлайн: 26 июля

— Бизнес-аналитика: математика, SQL и аналитический кейс
Разбор экзамена будет на «Аналитика Старт»
Дедлайн: 8 августа

Программы дают возможность поработать над реальными задачами со специалистами Т-Банка, а финалисты могут получить фаст-трек на стажировку или джуновскую позицию. Но сначала нужно пройти отбор. Делимся мини-гайдом с неочевидными нюансами, которые помогут повысить шансы на поступление.

Подписаться: @algoses

Задача с собеседования в TCS

Дан целочисленный массив nums, передвиньте все чётные числа в начало массива, а за ними — все нечётные.
Верните любой массив, удовлетворяющий этому условию.

Пример 1:
Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: результаты [4,2,3,1], [2,4,1,3] и [4,2,1,3] также были бы приняты.

Пример 2:
Input: nums = [0]
Output: [0]

Ограничения:
1 <= nums.length <= 5000
0 <= nums[i] <= 5000

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Используем метод двух указателей, движущихся в одном направлении (в этом случае сохранится относительный порядок чётных чисел в массиве):
left - индекс, указывающий, куда нужно записать следующее чётное число;
right - указатель, который проходит по массиву и последовательно проверяет каждый эл-т на чётность.
Вначале оба указателя указывают на первый эл-т.

Проходим указателем right по массиву nums:
- если число чётное: меняем его местами с числом на позиции left;
- сдвигаем указатель left вправо.

В конце возвращаем изменённый массив nums.

Сложность
O(n) - по времени (проходим по массиву длиной n)
O(1) - по памяти (храним две переменные, меняем эл-ты in-place)

Код
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
left = 0

for right in range(len(nums)):
if nums[right] % 2 == 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1

return nums

@algoses

Скоро начнутся отборы на осенние стажировки. Самое время обсудить на какие программы обратить свое внимание в первую очередь и как гарантировано пройти отбор! Смотрим! Смотрим!

https://www.youtube.com/watch?v=8QxduqUBn3g

Задача с собеседования в Blinkit

Дан целочисленный массив nums. Найдите подмассив с наибольшей суммой и верните эту сумму.

Follow up: если вы нашли решение с асимптотикой O(n), попробуйте реализовать ещё одно, используя метод "разделяй и властвуй".

Пример 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Подмассив [4,-1,2,1] имеет наибольшую сумму, равную 6.

Пример 2:
Input: nums = [1]
Output: 1
Explanation: Подмассив [1] имеет наибольшую сумму, равную 1.

Пример 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: Подмассив [5,4,-1,7,8] имеет наибольшую сумму, равную 23.

Ограничения:
1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

НАШ ЧАТ АЛГОРИТМИСТОВ

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

Разберём подробнее:
max_sum - глобальный максимум; инициализируем, как float("-inf"), гарантируя, что первый эл-т массива обновит максимум;
cur_sum - текущая сумма подмассива; инициализируем, как 0 (пустой префикс).

Проходим по массиву:
- формула, обновляющая cur_sum, выбирает: начать новый подмассив с текущего эл-та или продлить существующий. Если накопленная сумма отрицательна, значит, любой подмассив, начинающийся до текущего эл-та и идущий дальше, будет иметь сумму меньше, чем если бы он начинался с текущего эл-та => выгодно начать новый подмассив;
- обновляем глобальный максимум, выбирая максимальное значение среди max_sum и cur_sum.

Сложность
O(n) - по времени (проходим по массиву один раз)
O(1) - по памяти (храним две переменные)

Код
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float("-inf")
cur_sum = 0

for num in nums:
cur_sum = max(num, cur_sum + num)
max_sum = max(max_sum, cur_sum)

return max_sum


Подход "разделяй и властвуй":
Идея: делим массив пополам. Подмассив с наибольшей суммой попадает в один из трёх случаев:
- находится в левой половине;
- в правой половине;
- пересекает середину (начинается в левой половине и заканчивается в правой).

Рекурсивная функция принимает границы текущего подмассива [left, right], при первом вызове - весь массив:
База: если left == right - подмассив из одного эл-та, возвращаем его.

Рекурсивное ветвление:
1. Находим середину mid;
2. Рекурсивно ищем максимум в левой [left, mid] и правой половине [mid + 1, right];
3. Ищем максимум, пересекающий mid:
- идём влево от mid до left, накапливая текущую сумму; ищем cross_left - максимальный суффикс левой половины.
- идём от mid+1 вправо до right, накапливая текущую сумму; ищем cross_right - максимальный префикс правой половины.
- вычисляем cross_max, как сумму cross_left и cross_right.
4. Находим максимум среди left_max, right_max и cross_max.

Сложность:
O(n log n) - по времени (T(N) = 2T(N/2) + O(N) = O(N log N), где 2T(N/2) - рекурсивные вызовы для левой и правой половин и O(N) - проход от left до right для вычисления cross_max)
O(log n) - по памяти (глубина стека рекурсии)

Код:
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def divide_and_conquer(left: int, right: int) -> int:
if left == right:
return nums[left]

mid = (left + right) // 2
left_max = divide_and_conquer(left, mid)
right_max = divide_and_conquer(mid + 1, right)

cross_left = float("-inf")
cur_sum = 0
for i in range(mid, left - 1, -1):
cur_sum += nums[i]
cross_left = max(cross_left, cur_sum)

cross_right = float("-inf")
cur_sum = 0
for i in range(mid + 1, right + 1):
cur_sum += nums[i]
cross_right = max(cross_right, cur_sum)

cross_max = cross_left + cross_right

return max(left_max, cross_max, right_max)

return divide_and_conquer(0, len(nums) - 1)

@algoses

Товарищи, мы обновили линейку СТАРТ и открываем новый набор! 🚀

Мы переработали программы: обновили темы, добавили новые кейсы и вопросы с реальных собеседований, усилили практику и запустили полноценный карьерный блок.

Если раньше упор был только на технические навыки, то теперь на курсе вы также научитесь:
— составлять сильное резюме;
— презентовать свой опыт, даже если коммерческой работы не было;
— искать вакансии и понимать, куда лучше откликаться;
— проходить HR-этапы и уверенно чувствовать себя на всех интервью.

Открываем набор сразу на 4 направления:
- Аналитика
- Алгоритмы
- Backend
- Машинное обучение

📎Кому подойдет СТАРТ?

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

Что будет на курсах?

➡️Аналитика
Освоим SQL, продуктовые метрики, дашборды и A/B-тесты. В качестве пет-проекта пройдете полный цикл АВ тестирования — от запроса в БД до презентации результатов. Именно так работает аналитик.

➡️Алгоритмы
Разберем всё, что действительно спрашивают на технических интервью: структуры данных, графы, динамическое программирование, деревья, теория чисел и многое другое. Закроем фундамент для алгособеседований и контестов.

➡️Backend
Изучим архитектуру приложений, базы данных, Docker, gRPC и современные подходы к разработке. Итоговый пет-проект — полноценный сервис аналитики и прогнозирования цен криптовалют.

➡️Machine Learning
Метрики качества, классические алгоритмы, бустинг, нейронные сети и Transformer. Пет-проект — система кредитного скоринга. Без искусственных задач вроде «обучи свою LLM», только то, с чем реально сталкивается ML-инженер в начале карьеры.

Участникам курса также доступны:

🔵разбор контеста донабора Т-банк, стажировки в Яндекс, Авито буткемп DS (DS только на мл старт);
🔵mock-собеседования с обратной связью;
🔵закрытый банк вопросов с реальных интервью Яндекса, Т-Банка, Ozon, WB, Авито и других компаний;
🔵банк тестовых заданий и задач из бигтеха;
🔵реферальную рекомендацию в бигтех после успешной защиты пет-проекта.

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

🔊Подробную программу и стоимость курсов смотрите на сайте

Дополнительные скидки:
-500 ₽, если учились уже у нас на других курсах
-500 ₽, если берете с другом

Действует гарантия: прошел курс, выполнил все рекомендации, но не получил оффер — вернем деньги

📌Для вопросов и записи на курс напишите менеджеру

Задача с собеседования в Josh Technology Group

Дан целочисленный массив nums, индексированный с нуля, длины n и целое число target. Верните количество пар (i, j), где 0 <= i < j < n и nums[i] + nums[j] < target.

Пример 1:
Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: Существует 3 пары индексов, удовлетворяющих условию:
- (0, 1), так как 0 < 1 и nums[0] + nums[1] = 0 < target
- (0, 2), так как 0 < 2 и nums[0] + nums[2] = 1 < target
- (0, 4), так как 0 < 4 и nums[0] + nums[4] = 0 < target
Обратите внимание, что пара (0, 3) не учитывается, так как сумма nums[0] и nums[3] не является строго меньшей target.

Пример 2:
Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: Существует 10 пар индексов, удовлетворяющих условию:
- (0, 1), так как 0 < 1 и nums[0] + nums[1] = -4 < target
- (0, 3), так как 0 < 3 и nums[0] + nums[3] = -8 < target
- (0, 4), так как 0 < 4 и nums[0] + nums[4] = -13 < target
- (0, 5), так как 0 < 5 и nums[0] + nums[5] = -7 < target
- (0, 6), так как 0 < 6 и nums[0] + nums[6] = -3 < target
- (1, 4), так как 1 < 4 и nums[1] + nums[4] = -5 < target
- (3, 4), так как 3 < 4 и nums[3] + nums[4] = -9 < target
- (3, 5), так как 3 < 5 и nums[3] + nums[5] = -3 < target
- (4, 5), так как 4 < 5 и nums[4] + nums[5] = -8 < target
- (4, 6), так как 4 < 6 и nums[4] + nums[6] = -4 < target

Ограничения:
1 <= nums.length == n <= 50
-50 <= nums[i], target <= 50

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
При наивном решении мы бы проходили по вложенному циклу за O(n²).
Но в данном случае заметим, что для удовлетворения условию nums[i] + nums[j] < target важны не позиции эл-в в массиве, а только их значения => мы можем отсортировать массив в восходящем порядке, и для каждого текущего nums[i] все подходящие nums[j] будут идти подряд от начала до некоторого индекса (образовывать префикс), так как если nums[i] + nums[j] < target, то nums[i] + nums[k] < target для любого k < j.

Логично использовать алгоритм двух указателей и двигать указатели навстречу друг другу, проверяя сумму nums[left] и nums[right]. К count (счетчик пар) добавляется не одна пара, а целая группа пар (count += right - left), так как nums[left] - самый маленький текущий эл-т, и, если его сумма с самым большим текущим эл-м (nums[right]) меньше target => сумма nums[left] и любого эл-та между left и right будет также меньше target.

Переменные:
left - индекс первого эл-та в массиве;
right - индекс последнего эл-та;
count - счётчик пар, удовлетворяющих условию.

Пока left меньше right, проходим по массиву, сужая окно между указателями:
Сравниваем сумму текущей пары эл-в с target:
Если меньше:
- добавляем к count значение right - left. Таким образом, все пары с текущим left учтены;
- сдвигаем left вправо.
Если сумма больше или равна target:
- сдвигаем right влево.

В конце возвращаем count.

Сложность
O(n log n) - по времени (сортируем массив, где n - кол-во элементов в массиве; обход двумя указателями - за O(n), так как проходимся по каждому элементу единожды)
O(n) - по памяти (для сортировки на питоне)

Код
class Solution:
def countPairs(self, nums: List[int], target: int) -> int:
nums.sort()
count = 0
left = 0
right = len(nums) - 1

while left < right:
if nums[left] + nums[right] < target:
count += right - left
left += 1
else:
right -= 1

return count

@algoses

Товарищи, Поступашкам нужны контент мейкеры. Если вы творческая личность, интересующейся бэкендом, дата сайнс, аналитикой, алгоритмами и так далее, вам нравится писать посты/ придумывать идеи для контента, то обязательно пишите @vice22821. Оплата сдельная, ориентировочно за один пост от 2 тыс до 15 тыс рублей.

Обязательно делитесь с ребятами, которым это может быть интересно.

Хотите учить алгоритмы, но не знаете Python?

Товарищи, алгоритмы сами по себе не самые простые. А если параллельно с решением задачи приходится гуглить, как написать цикл for, подготовка превращается в отдельный вид страдания 😔

Поэтому запускаем бесплатный открытый курс «Python для алгоритмов».

С 14 по 19 июля разберём базу Python, которая нужна именно для решения алгоритмических задач.

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

За 6 дней разберём условия, циклы, функции, строки и основные структуры данных. Научимся читать код, работать с вводом и выводом и переводить уже придуманное решение задачи на Python.

Задача курса — построить фундамент, с которым вы сможете полноценно начать изучать алгоритмы и структуры данных.

Курс подойдёт, если вы:
➡️ никогда раньше не программировали
➡️ когда-то учили Python, но забыли базовый синтаксис
➡️ планируете проходить отборы на стажировки, в ШАД, Академию аналитиков Авито и другие школы

🏆А самых сильных участников ждёт отдельный бонус. Лучшим подарим полный курс по алгоритмам

📌Ссылка на курс в нашем боте - @Postupashkianalitycsbot
Первые материалы уже выложены!

Задача с собеседования в Josh Technology Group

Дан массив целых чисел temperatures, представляющий ежедневные значения температуры. Верните массив answer, где answer[i] - это количество дней, которое нужно подождать после i-ого, чтобы наступил день с более высокой температурой. Если нет будущего дня, для которого это возможно, вместо этого сохраните answer[i] == 0.

Пример 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Пример 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Пример 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]

Ограничения:
1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
При наивном решении мы бы итерировались по массиву для каждого дня в поисках более тёплого c асимптотикой O(n²).
Но мы видим паттерн - поиск ближайшего большего/меньшего эл-та, поэтому используем монотонный стек (стек, элементы которого хранятся в строго возрастающем или строго убывающем порядке).
В данном случае стек будет монотонно убывающим. При добавлении нового эл-та алгоритм будет сравнивать его с вершиной стека:
- Пока текущий эл-т больше верхнего эл-та стека (stack[-1][0]): достаём верхний элемент, вычисляем ответ для него (через разницу между индексами текущего эл-та и эл-та из стека) и удаляем эл-т из стека.
Кладём текущий эл-т в стек.


Разберём более подробно:
Создаём:
- стек для хранения пар (температура, индекс) в монотонно убывающем порядке;
- массив answer длиной n, равной длине входящего массива. Заполняем его нулями.

Итерируемся по массиву температур:
Пока стек не пуст и в нём есть дни холоднее текущего:
- достаём значение и индекс более холодного дня, удаляя его из стека;
- вычисляем разницу между индексом текущего дня и индексом более холодного дня - таким образом, узнаем кол-во дней, которые должны пройти между ними. Записываем разницу в массив answer по индексу более холодного дня (answer[stack_i]).
После выхода из цикла while или непопадания в него: добавляем текущий день в стек для последующего сравнения с другими значениями.

В конце возвращаем заполненный массив answer.

Сложность
O(n) - по времени (каждый эл-т добавляется в стек только 1 раз и может быть удалён только 1 раз)
O(n) - по памяти (в худшем случае в стек придётся добавить все элементы входного массива длиной n)

Код
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
stack = []
answer = [0] * n

for i, temp in enumerate(temperatures):
while stack and stack[-1][0] < temp:
stack_temp, stack_i = stack.pop()
answer[stack_i] = i - stack_i

stack.append((temp, i))

return answer

@algoses