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

🔥 Уже завтра стартует новый поток курсов к ШАД До первого этапа отбора остаётся все меньше времени. Но и за этот период можно подготовиться и уверенно пройти отбор. Поэтому если вы откладывали подготовку до последнего момента — сейчас самое время ее начать. Курсы подготовки к ШАД / AI Masters / ААА начинаются завтра 8 марта, а значит вы еще успеваете присоединиться. Мы готовим по пяти ключевым направлениям: ⬇️ Дискретная математика ⬇️ Алгоритмы ⬇️ Теория вероятностей ⬇️ Линейная алгебра ⬇️ Математический анализ В основе обучения — практика: 🔵задачи формата отборов 🔵разбор контестов 🔵пробные экзамены 🔵мок-интервью 🔵доступ к закрытой базе заданий ШАДа Каждый год мы подробно разбираем все этапы экзамена: смотрим, какие темы появляются чаще, какие задачи повторяются, какие паттерны встречаются в отборах. На основе этого анализа строится программа курсов — вы готовитесь к тому, что реально будет на экзамене. ✨ До 8 марта в честь запуска курсов мы дарим скидку 33% Цена на 1 курс - 12 950 ₽ При покупке 2-х курсов - 12 450 ₽ за курс При покупке от 3-х и более - 11 950 ₽ за курс При покупке 3+ курсов вы получаете курс по дискретной математике в подарок 💫 На курсах уже выложены первые материалы, поэтому при записи вы сразу получаете доступ к лекциям и задачам. ➡️Для вопросов и записи на курсы напишите менеджеру. После старта цены повысятся.

Задача с собеседования в Zoho Даны две строки: word1 и word2. Верните минимальное количество операций, требуемых для преобразования строки word1 в строку word2. Вы можете выполнять следующие три операции над словом: - вставить символ - удалить символ - заменить символ Пример 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (заменить 'h' на 'r') rorse -> rose (удалить 'r') rose -> ros (удалить 'e') Пример 2: Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (удалить 't') inention -> enention (заменить 'i' на 'e') enention -> exention (заменить 'n' на 'x') exention -> exection (заменить 'n' на 'c') exection -> execution (вставить 'u') Ограничения: 0 <= word1.length, word2.length <= 500 word1 и word2 состоят из строчных английских букв НАШ ЧАТ АЛГОРИТМИСТОВ Решение Задача помечена тегом "Dynamic Programming" и является классическим примером задачи на вычисление "расстояния Левенштейна". Используем восходящее dp с табуляцией. Сначала разберём базовое решение, а потом оптимизируем: Заполняем таблицу размером (len(word1) + 1) × (len(word2) + 1), где dp[i][j] - минимальное кол-во операций, необходимое для превращения первых i символов word1 в первые j символов word2. i и j - это кол-во символов, поэтому dp[0][j] соответствует пустой word1, dp[i][0] - пустой word2. Базовый случай, когда одна из строк пустая: word1 пустая: нужно вставить все символы word2 (j вставок); word2 пустая: нужно удалить все символы word1 (i удалений). Остальные ячейки заполняем, смотря на последние символы текущих префиксов (word1[i-1] и word2[j-1]): Если символы совпадают, нам не нужно ничего с ними делать, копируем значение из левой верхней ячейки; Если символы не совпадают, есть три варианта действий, выбираем минимальный по кол-ву операций: 1. Замена: dp[i-1][j-1] + 1 - заменяем последний символ word1 на последний символ word2; 2. Удаление: dp[i-1][j] + 1 - удаляем последний символ из word1; 3. Вставка: dp[i][j-1] + 1 - вставляем последний символ word2 в word1. Оптимизируем: Храним не всю таблицу, а две переменные: prev (предыдущая строка, на первом шаге - первая строка таблицы) и cur (текущая строка, вначале заполнена нулями). Если длина word1 меньше длины word2, меняем строки местами: более короткая строка становится word2, внутренний цикл идёт по ней, оптимизируя память до O(min(m, n)). Во внешнем цикле: проходим по всем символам word1: - в начале каждой итерации устанавливаем первый эл-т текущей строки: cur[0] = i. Это соответствует случаю, когда word2 пустая, поэтому нужно удалить все i символов из word1. Во внутреннем: проходим по word2: - символы совпадают: копируем значение из левой верхней ячейки (prev[j-1]); - не совпадают: берём минимум из трёх значений: prev[j-1] - замена символа word1[i-1] на word2[j-1]; обе строки становятся короче на 1, в таблице dp это диагональ. prev[j] - удаление символа word1[i-1]; word1 становится короче, word2 - той же длины, в таблице это верх. cur[j-1] - вставка символа word2[j-1] в word1; word2 - короче, word1 - той же длины, в таблице это значение слева. + 1, так как любая операция требует одного действия. После заполнения строки меняем местами prev и cur, текущая строка становится предыдущей для следующей итерации. После завершения циклов prev содержит последнюю заполненную строку, а её последний эл-т является ответом. Сложность O(mn) - по времени (проходим по всем парам символов) O(min(m, n)) - по памяти Код class Solution: def minDistance(self, word1: str, word2: str) -> int: if len(word1) < len(word2): word1, word2 = word2, word1 prev = list(range(len(word2) + 1)) cur = [0] * (len(word2) + 1) for i in range(1, len(word1) + 1): cur[0] = i for j in range(1, len(word2) + 1): if word1[i-1] == word2[j-1]: cur[j] = prev[j-1] else: cur[j] = min(prev[j-1], prev[j], cur[j-1]) + 1 prev, cur = cur, prev return prev[-1] @algoses

🔊 Добавляем курс по дискретной математике Мы расширяем линейку курсов подготовки к ШАД / AI Masters / ААА и запускаем курс по дискретной математике. У нас было много запросов на этот курс, и неудивительно: по статистике именно на задачах по дискретке люди теряют заветные баллы. Также без ее понимания почти нет шансов решить задачи по теорверу. Программу, подробности и отзывы на курс смотрите на сайте. Итого мы готовим по пяти ключевым направлениям: ⬇️ Дискретная математика ⬇️ Алгоритмы ⬇️ Теория вероятностей ⬇️ Линейная алгебра ⬇️ Математический анализ ✨ До 1.03 включительно скидка 33% на - курс по дискретной математике: 20 150 12 950₽ - покупки от трех+ курсов: от 60450 35 850₽ А если вы приобрели из линейки 3 и более курса, то курс по дискретной математике идет в подарок. ➡️Для вопросов и записи на курсы напишите менеджеру

Задача с собеседования в Zoho Вы поднимаетесь по лестнице. Чтобы достичь вершины, нужно сделать n шагов. Каждый раз вы можете подняться либо на 1, либо на 2 ступеньки. Сколькими различными способами вы можете подняться на вершину? Пример 1: Input: n = 2 Output: 2 Explanation: Существует два способа подняться на вершину: 1. 1 шаг + 1 шаг 2. 2 шага Пример 2: Input: n = 3 Output: 3 Explanation: Существует три способа подняться на вершину: 1. 1 шаг + 1 шаг + 1 шаг 2. 1 шаг + 2 шага 3. 2 шага + 1 шаг Ограничения: 1 <= n <= 45 НАШ ЧАТ АЛГОРИТМИСТОВ Решение Задача помечена тегом "Dynamic Programming", оптимальным вариантом решения будет использование восходящего подхода с табуляцией, так мы избавимся от риска переполнения стека при глубокой рекурсии. Для оптимизации памяти до O(1) храним только две переменные (cur_step и prev_step) вместо dp массива. Начинаем с базовых случаев (ступеньки 0 и 1), при которых ответ будет равен 1 способу => инициализируем наши две переменные значениями 1. Запускаем цикл и поднимаемся вверх по лестнице со второй ступеньки, обновляя значения кол-ва способов подняться на предыдущую и текущую ступеньки, с каждой итерацией: - текущая ступенька становится предыдущей; - новая текущая ступенька равняется сумме способов подняться на две предыдущие ступеньки (по сути, классическая формула из задач о числах Фибоначчи: f(n) = f(n-1) + f(n-2)). После окончания работы цикла выводим cur_step с последним вписанным в переменную значением. Сложность O(n) - по времени (так как делаем один проход по всем ступенькам) O(1) - по памяти (так как храним только две переменные) Код class Solution: def climbStairs(self, n: int) -> int: if n == 0 or n == 1: return 1 cur_step, prev_step = 1, 1 for _ in range(2, n + 1): prev_step, cur_step = cur_step, prev_step + cur_step return cur_step @algoses

🔥 До отборов в ШАД осталось всего 2 месяца Мы открываем набор на новый поток математических курсов к ШАД / AI Masters / ААА/, где за несколько месяцев системной подготовки вы научитесь уверенно решать задачи. Курсы специально созданы для тех, кто

🔵Только задумался о подготовке 🔵Уже готовился, но чувствует, что есть пробелы 🔵Давно не занимался математикой и хочет изучить нужное для отбора 🔵Готовится параллельно к собеседованиями в бигтех и поступлению в магистратуру

Мы готовим по четырём ключевым направлениям: ⬇️ Алгоритмы ⬇️ Теория вероятностей ⬇️ Линейная алгебра ⬇️ Математический анализ Занятия не пересекаются, а нагрузка распределена так, чтобы вы могли учиться параллельно на нескольких курсах и комфортно совмещать подготовку с учебной/работой. На нашем сайте можно найти программу, подробности и отзывы на каждый курс. В основе обучения - практика Мы разбираем только нужный материал и решаем типовые задачи с экзаменов и собесов. А также разбираем контесты, проводим еженедельные пробники и мок-интервью, даем доступ к закрытой базе заданий ШАДа. ✨ Цена на 1 курс - 20 150 ₽ При покупке 2-х курсов - 18 550 ₽ за курс При покупке от 3-х и более - 17 550 ₽ за курс ➡️Для вопросов и записи на курсы напишите менеджеру

Это твой ПОСЛЕДНИЙ шанс стать лидером будущего «МАЯКИ» — всероссийский проект Сбера и Фонда «Вклад в будущее». Здесь ищут студентов, которые умеют действовать: проверять гипотезы, брать на себя иницитиву, быстро учиться и доводить начатое до результата. Отбор уже идёт — 300 лучших участников со всей России встретятся с экспертами Сбера и получат доступ к уникальным возможностям и 300 000₽ на реализацию самых смелых идей. Если ты из тех, кто не ждёт «идеального момента», а создаёт его сам — подавай заявку до 27 февраля.

Задача с собеседования в Zendesk Вам дано целое число money, обозначающее сумму денег (в долларах), которая у вас есть, и другое целое число children, обозначающее количество детей, между которыми вы должны распределить деньги. Вы должны распределить деньги в соответствии со следующими правилами: - Все деньги должны быть распределены; - Каждый получает хотя бы 1 доллар; - Никто не получает 4 доллара. Верните максимальное количество детей, которые могут получить ровно 8 долларов, если вы распределите деньги согласно вышеуказанным правилам. Если распределить деньги невозможно, верните -1. Пример 1: Input: money = 20, children = 3 Output: 1 Explanation: Максимальное количество детей, которые получат 8 долларов, будет равно 1. Один из способов распределить деньги: - 8 долларов первому ребёнку; - 9 долларов второму ребёнку; - 3 доллара третьему ребёнку. Можно доказать, что не существует такого распределения, при котором количество детей, получающих 8 долларов, будет больше 1. Пример 2: Input: money = 16, children = 2 Output: 2 Explanation: Каждому ребёнку можно дать по 8 долларов. Ограничения: 1 <= money <= 200 2 <= children <= 30 НАШ ЧАТ АЛГОРИТМИСТОВ Решение Итак, нам нужно определить максимальное кол-во детей, которые могут получить ровно 8 долларов. Сначала раздадим каждому по 1 обязательному доллару, чтобы гарантировать соблюдение правила. Оставшаяся после распределения сумма не должна быть отрицательной, иначе это означает, что детей было больше, чем долларов, и мы не смогли бы дать каждому даже по 1 доллару. Оставшиеся деньги мы можем распределить дополнительно и раздать максимально возможному кол-ву детей ещё по 7 долларов => кол-во детей, которые могут получить ровно 8 долларов равно: remaining_money // 7. Рассмотрим три случая: 1. Все дети получат по 8 долларов, если результат целочисленного деления будет равен количеству детей с остатком равным 0. 2. Если можем дать дополнительные 7 долларов всем, кроме одного, и при этом остаток денег равняется 3: мы вынуждены забрать доллар у ребёнка с 8 долларами и отдать его ребёнку с 4 долларами. Таким образом, у нас гарантированно будет 2 ребёнка, которые не смогут получить 8 долларов, не нарушая правила (значит, кол-во тех, кто сможет: children - 2). 3. Базовый случай: у нас есть два ограничения - кол-во денег (remaining_money // 7) и кол-во детей, которые могут получить 8 долларов с учётом того, что необходимо отдать остаток после распределения одному ребёнку (children - 1). Ограничения должны быть соблюдены одновременно, поэтому мы выбираем самое строгое из них. То есть берём минимум, который и будет нашим максимально возможным кол-вом детей. Сложность O(1) - по времени O(1) - по памяти Код class Solution: def distMoney(self, money: int, children: int) -> int: remaining_money = money - children if remaining_money < 0: return -1 if (remaining_money // 7 == children and remaining_money % 7 == 0): return children if (remaining_money // 7 == children - 1 and remaining_money % 7 == 3): return children - 2 return min(children - 1, remaining_money // 7) @algoses

🔥 До отборов в ШАД осталось всего 2 месяца Мы открываем набор на новый поток математических курсов к ШАД / AI Masters / ААА/, где за несколько месяцев системной подготовки вы научитесь уверенно решать задачи. Курсы специально созданы для тех, кто

🔵Только задумался о подготовке 🔵Уже готовился, но чувствует, что есть пробелы 🔵Давно не занимался математикой и хочет изучить нужное для отбора 🔵Готовится параллельно к собеседованиями в бигтех и поступлению в магистратуру

Мы готовим по четырём ключевым направлениям: ⬇️ Алгоритмы ⬇️ Теория вероятностей ⬇️ Линейная алгебра ⬇️ Математический анализ Занятия не пересекаются, а нагрузка распределена так, чтобы вы могли учиться параллельно на нескольких курсах и комфортно совмещать подготовку с учебной/работой. На нашем сайте можно найти программу, подробности и отзывы на каждый курс. В основе обучения - практика Мы разбираем только нужный материал и решаем типовые задачи с экзаменов и собесов. А также разбираем контесты, проводим еженедельные пробники и мок-интервью, даем доступ к закрытой базе заданий ШАДа. ✨ До 24.02 включительно действует скидка 33% на все курсы Цена на 1 курс - 12 950 ₽ При покупке от 2-х курсов - 12 450 ₽ за курс При покупке от 3-х и более - 11 950 ₽ за курс ➡️Для вопросов и записи на курсы напишите менеджеру

🔘 Как не завалить тестовое и пройти отбор на летнюю стажировку? Отвечает Михаил Густокашин — директор центра студенческих олимпиад ФКН ВШЭ, тренер Чемпионов мира ICPC и легенда наших Тренировок по алгоритмам.

В новом сезоне Тренировок не только изучаем теорию и решаем задачи, а готовимся ко всем этапам отбора на стажировку в Яндекс: от контеста до собеседования.

Регистрируйся, тренируйся и получай призы от Яндекса: yandex.ru/yaintern/training/algorithm-training Реклама. ООО "Яндекс". ИНН 7736207543

Задача с собеседования в eBay Дана закодированная строка. Верните её в раскодированном виде. Правило кодирования: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Гарантируется, что k - целое положительное число. Считайте, что входная строка всегда корректна: нет лишних пробелов, квадратные скобки сформированы правильно и т.д.. Кроме того, можно считать, что исходные данные не содержат цифр, а цифры используются только для указания числа повторов k. Например, не будет таких входных данных, как 3a или 2[4]. Тестовые примеры сгенерированы так, что длина выходной строки никогда не превысит 10⁵. Пример 1: Input: s = "3[a]2[bc]" Output: "aaabcbc" Пример 2: Input: s = "3[a2[c]]" Output: "accaccacc" Пример 3: Input: s = "2[abc]3[cd]ef" Output: "abcabccdcdcdef" Ограничения: 1 <= s.length <= 30; s состоит из строчных английских букв, цифр и квадратных скобок "[]"; s гарантированно является корректным входом; Все целые числа в s находятся в диапазоне [1, 300]. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Очевидная сложность раскодирования в том, что скобки могут быть вложенными. Сначала должны обрабатываться внутренние скобки, поэтому будем использовать стек для хранения символов и промежуточных результатов. Итерируемся по строке s: Добавляем символ в стек, если он не является закрывающей скобкой. Если же встречаем закрывающую скобку, начинаем собирать подстроку: Пока верхний эл-т стека не является открывающей скобкой: извлекаем символы из стека и добавляем в начало substring. Далее открывающую скобку из стека удаляем: мы обработали содержимое внутри скобок, теперь нужно получить число его повторов, находящееся перед открывающей скобкой. Так как число k может быть многозначным, необходимо извлекать символы до тех пор, пока стек не пуст и верхний эл-т является цифрой. Преобразовываем k в целое число и умножаем подстроку на него, добавляем результат в стек. После того, как строка s будет полностью обработана, возвращаем итоговую строку, содержащую объединённые эл-ты стека. Сложность O(maxK^countK * n) - по времени (где maxK - максимальное значение k, countK - количество вложенных k значений (уровень вложенности), а n - максимальная длина закодированной строки) O(n) - по памяти Код class Solution: def decodeString(self, s: str) -> str: stack = [] for char in s: if char != "]": stack.append(char) else: substring = "" while stack[-1] != "[": substring = stack.pop() + substring stack.pop() k = "" while stack and stack[-1].isdigit(): k = stack.pop() + k stack.append(int(k) * substring) return "".join(stack) @algoses

❗️ Яндекс открыл контест на весеннюю стажировку, задания тут, а их разбор уже выложен на наших курсах: ➡️ алгоритмы старт ➡️ аналитика старт ➡️ машинное обучение старт ➡️ бэкенд разработка старт Помимо разборов, которые проходят все скрытые тесты на наличие ИИ в решениях, на наших курсах вы получаете:

🔽 Огромный банк реальных техвопросов 🔽 Записи реальных собесов и интервью 🔽 Реальные тестовые задания топовых бигтехов 🔽 Разбор всех задач с алгсобесов Яндекса

🎁 А специально для наших подписчиков до 18 февраля доступна скидка в 30% по промокоду «Яндекс»! Успей написать администратору и не откладывай: задания могут поменять!

💌 Валентинка, которая не завянет Цветы - хороший подарок, но они не помогут наладить отношения с оффером, а наши курсы помогут 💋 В честь 14 февраля дарим скидку 30% на любой курс из нашей карьерной линейки. А если идете вместе со своей второй половинкой, то скидка будет будет 40% ! Дарите полезные подарки и растите вместе ♥️ А наши курсы вам помогут:

🔽 Разобрать контесты Яндекса 🔽 Заботать банк технических вопросов и увидеть записи реальных интервью и собесов 🔽 Нарешать тестовые задания топовых бигтехов 🔽 Разобраться в решении задач с алгсобесов Яндекса

😘 Скикда действует до 14 февраля (включительно). Успей написать менеджеру и подарить лучший подарок для себя или второй половинки!

Задача с собеседования в eBay Даны n пар скобок. Напишите функцию генерации всех возможных комбинаций правильных скобочных последовательностей. Пример 1: Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] Пример 2: Input: n = 1 Output: ["()"] Ограничения: 1 <= n <= 8 НАШ ЧАТ АЛГОРИТМИСТОВ Решение Известно, что правильная скобочная последовательность должна состоять из одинакового количества открывающих и закрывающих скобок, то есть общая длина правильной комбинации - n * 2. Для решения задачи используем алгоритм поиска с возвратом, где на каждом шаге, в зависимости от условий, добавляем либо открывающую, либо закрывающую скобку. После построения полной правильной комбинации и её сохранения мы не прерываем поиск, а последовательно возвращаемся по стеку вызовов до последней точки выбора и исследуем другие ветки из этой точки. Создаём два списка: result - для хранения найденных правильных комбинаций; combination - временный список для "собирания" текущей комбинации. Запускаем рекурсивную функцию backtrack(open_count, close_count) для генерации комбинаций, отслеживая кол-во открывающих и закрывающих скобок. Базовый случай: если длина текущей комбинации достигла n * 2 - добавляем готовую комбинацию в result и возвращаемся. Рекурсивное ветвление: можем добавить открывающую, если ещё не использованы все n открывающих скобок. Можем добавить закрывающую, если кол-во открывающих скобок больше кол-ва закрывающих, это условие гарантирует, что у нас есть незакрытая открывающая скобка, которую можно закрыть. Для каждого допустимого выбора: - добавляем скобку в combination - вызываем рекурсию с обновленными параметрами - удаляем последнюю добавленную скобку для возврата к развилке и исследованию других путей построения последовательности. Функция завершается, когда полностью исследовано дерево возможных комбинаций. Для начального вызова backtrack(0, 0) это означает, что исследованы все пути первого if, а путь второго if невозможен, так как последовательность не может начаться с закрывающей скобки. Сложность Экспоненциальная: O(4ⁿ/√n) - по времени (определяется n-ым числом Каталана Cₙ, равным кол-ву правильных скобочных последовательностей для n пар скобок); в кач-ве упрощения иногда говорят о сложности O(2**n) O(n) - по памяти Код class Solution: def generateParenthesis(self, n: int) -> List[str]: result = [] combination = [] def backtrack(open_count, close_count): if len(combination) == 2 * n: result.append("".join(combination)) return if open_count < n: combination.append("(") backtrack(open_count + 1, close_count) combination.pop() if open_count > close_count: combination.append(")") backtrack(open_count, close_count + 1) combination.pop() backtrack(0, 0) return result @algoses

Учишься в 10–11 классе и хочешь решать задачи реального бизнеса, а не учебные примеры? Кейс-чемпионат DEADLINE от Центрального университета — твой шанс решить реальную задачу от крупной ритейл-компании и показать себя лидерам IT и бизнеса. Тебя ждёт: — реальные бизнес-кейсы от топового ритейла; — лекции и менторы из IT и бизнеса; — очный финал в Москве; — нетворкинг, мерч и экскурсия в офис Т-Банка. И да, про призы: — возможность получить грант в Центральный университет до 100% стоимости обучения; — Яндекс Станция, подписка Pro в Т-Банке; — фаст-трек при поступлении в ЦУ. Регистрируйся до 9 марта и пробуй себя в реальном бизнесе, а не в учебниках.

Задача с собеседования в eBay Перед вами замок с 4 вращающимися дисками. Каждый диск имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Диски можно свободно вращать вперёд и назад: например, вы можете превратить '9' в '0' или '0' в '9'. Каждый ход - это поворот одного диска на одну позицию. Замок начинает с комбинации '0000' (строка, представляющая состояние 4-х дисков). Вам дан список тупиков - deadends: если на замке отображается какая-либо из запрещённых комбинаций, диски замка перестают вращаться, и вы не можете его открыть. Вам также дана целевая комбинация target, представляющая значение дисков, при котором замок откроется. Верните минимальное возможное количество вращений, необходимое для открытия замка. Если это невозможно, верните -1. Пример 1: Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6 Объяснение: последовательность допустимых ходов может быть такой: "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". Обратите внимание, что последовательность типа "0000" -> "0001" -> "0002" -> "0102" -> "0202" будет недопустимой, так как диски замка остановятся после запрещённой комбинации "0102". Пример 2: Input: deadends = ["8888"], target = "0009" Output: 1 Объяснение: мы можем повернуть последний диск в обратном направлении, чтобы перейти от "0000" к "0009". Пример 3: Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output: -1 Объяснение: мы не можем достичь цели, не попав в тупик. Ограничения: 1 <= deadends.length <= 500 deadends[i].length == 4 target.length == 4 target не может присутствовать в списке deadends target и deadends[i] состоят только из цифр НАШ ЧАТ АЛГОРИТМИСТОВ Решение Рассмотрим задачу как поиск кратчайшего пути в графе. Вершины графа - комбинации цифр на 4 дисках, каждый диск - одна позиция в комбинации. Некоторые вершины (deadends) заблокированы, мы не можем посещать их на пути к целевой вершине (target). Граф - невзвешенный, так как все рёбра имеют одинаковый вес (один поворот диска) => используем алгоритм поиска в ширину (BFS). Начинаем обход с начального состояния '0000' (если оно в списке deadends - до target мы не дойдём, возвращаем -1), добавляем в очередь в виде кортежа (комбинация цифр и количество вращений). Все запрещённые комбинации сразу добавляем во множество visited, чтобы избежать попадания в тупик. Пока очередь не пуста: извлекаем текущую комбинацию и количество вращений. Если комбинация соответствует target - возвращаем число вращений. Иначе: генерируем 8 следующих комбинаций, увеличивая и уменьшая каждую из 4 цифр (2 направления: 1 поворот диска вперёд и назад). Чтобы реализовать закольцованность дисков: деление по модулю (%10), "9" -> "0" при вращении диска вперёд ((9 + 1) % 10 = 0) и "0" -> "9" при вращении назад ((0 - 1) % 10 = 9). Проверяем комбинацию: если ещё не посещена - добавляем в visited и помещаем в очередь, увеличивая количество вращений на 1. Если очередь опустела, а target не достигнута - пути не существует, возвращаем -1. Сложность O(V + E) - по времени O(V) - по памяти Код class Solution: def openLock(self, deadends: List[str], target: str) -> int: if "0000" in deadends: return -1 def new_combinations(node): result = [] for i in range(4): next_digit = (int(node[i]) + 1) % 10 result.append(node[:i] + str(next_digit) + node[i + 1:]) prev_digit = (int(node[i]) - 1) % 10 result.append(node[:i] + str(prev_digit) + node[i + 1:]) return result q = deque([("0000", 0)]) visited = set(deadends) visited.add("0000") while q: node, turns = q.popleft() if node == target: return turns for combination in new_combinations(node): if combination not in visited: visited.add(combination) q.append((combination, turns + 1)) return -1 @algoses

Подкаст, который точно попадёт в твоё избранное 💚 Ко Дню науки Сбер запустил подкаст «Инструкция не прилагается» про то, как олимпиадный опыт помогает создавать технологии, которыми пользуются миллионы. Участники — юные победители олимпиад по ИИ, программированию, точным наукам и эксперты Сбера, которые сейчас создают новые технологии и в своё время тоже блистали на олимпиадах 💻 В первом выпуске обсудили, как ИИ влияет на всё — от ежедневных привычек до продуктов Сбера. Смотри подкаст на удобной площадке: VK Видео | RUTUBE 🎬

Разбор алгоритмов Т-банк (первая часть) Разбор второй части и всех направлений выложен только на наших курсах. До конца дня действует льготная цена 13450 8950. Записываемся осталось 6 часов до конца экзамена! @algoses

Задача с собеседования в Zoox Дан массив prices, где prices[i] - это цена акции в i-й день. Вы хотите максимизировать прибыль, выбрав один день для покупки акции и другой день в будущем для её продажи. Верните максимальную прибыль, которую вы можете получить с этой сделки. Если прибыль получить невозможно, верните 0. Пример 1: Input: prices = [7,1,5,3,6,4] Output: 5 Объяснение: Покупаете акцию во 2-й день (цена = 1) и продаёте в 5-й (цена = 6). Прибыль: 6 - 1 = 5. Обратите внимание, что покупка во 2-й день и продажа в 1-й невозможна, так как вы должны сначала купить, а потом продать! Пример 2: Input: prices = [7,6,4,3,1] Output: 0 Объяснение: В этом случае сделок не совершается (нет выгодных условий), и максимальная прибыль равно 0. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Для получения максимальной прибыли - покупаем на минимуме и продаём на максимуме. Заводим две переменные: min_price (находим самую выгодную цену) и max_profit (ищем наибольшую разницу между минимумом и текущей стоимостью акции). Осуществляем проход по массиву и сравниваем минимальную цену (вначале она равняется первому эл-ту массива) с текущей. Если текущая меньше минимальной, обновляем значение минимума. Последний найденный минимум - цена, по которой мы купим акцию. Далее, в независимости от того, выполнилось ли условие для обновления минимума, проверяем: будет ли максимальной прибыль от продажи акции в текущий день. Сравниваем ранее найденное значение max_profit с прибылью, которую получим от продажи акции "сегодня". После окончания работы цикла выводим max_profit с последним вписанным в переменную значением. Задача помечена тегом "Dynamic Programming", подход использован в решении: мы храним две переменные (min_price, max_profit) и используем их найденные значения для вычисления следующих. Сложность O(n) - по времени O(1) - по памяти Код class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 min_price = prices[0] max_profit = 0 for price in prices: if price < min_price: min_price = price max_profit = max(max_profit, price - min_price) return max_profit @algoses

😀😃😄😁😆😅🙂🥰😎😊 Сбер не просто так играл со светом и тенью в своих афишах: это был анонс программы МАЯКИ! Молодых, Активных, Ярких, Креативных, Инициативных студентов приглашают принять вызов, предложить нестандартное решение и реализовать самые смелые идеи. «Стань тем, кто ведёт» и будь первым, кто встанет у начала прогрессивных изменений! МАЯКИ ждут, когда ты присоединишься к ним.

😀😃😄😁😆😅🙂🥰😎😊 Сбер не просто так играл со светом и тенью в своих афишах: это был анонс программы МАЯКИ! Молодых, Активных, Ярких, Креативных, Инициативных студентов приглашают принять вызов, предложить нестандартное решение и реализовать самые смелые идеи. «Стань тем, кто ведёт» и будь первым, кто встанет у начала прогрессивных изменений! МАЯКИ ждут, когда ты присоединишься к ним.