اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Алгоритмы - Собеседования, Олимпиады, ШАД
رفتن به کانال در Telegram
Номер заявления регистрацию в РКН: № 5731053751 Чат: @algoses_chat По всем вопросам: @vice22821
نمایش بیشتر📈 تحلیل کانال تلگرام Алгоритмы - Собеседования, Олимпиады, ШАД
کانال Алгоритмы - Собеседования, Олимпиады, ШАД (@algoses) در بخش زبانی روسی بازیگری فعال است. در حال حاضر جامعه شامل 11 871 مشترک است و جایگاه 17 038 را در دسته آموزش و رتبه 55 513 را در منطقه روسيا دارد.
📊 شاخصهای مخاطب و پویایی
از زمان ایجاد در невідомо، پروژه رشد سریعی داشته و 11 871 مشترک جذب کرده است.
بر اساس آخرین دادهها در تاریخ 14 ژوئن, 2026، کانال فعالیت پایداری دارد. در ۳۰ روز گذشته تغییر اعضا برابر 20 و در ۲۴ ساعت گذشته برابر -1 بوده و همچنان دسترسی گستردهای حفظ شده است.
- وضعیت تأیید: تأیید نشده
- نرخ تعامل (ER): میانگین تعامل مخاطب 21.17% است و در ۲۴ ساعت نخست پس از انتشار، محتوا معمولاً 12.00% واکنش نسبت به کل مشترکان کسب میکند.
- دسترسی پستها: هر پست به طور میانگین 2 513 بازدید دریافت میکند. در اولین روز معمولاً 1 425 بازدید جمعآوری میشود.
- واکنشها و تعامل: مخاطبان بهطور فعال حمایت میکنند؛ میانگین واکنش به هر پست 4 است.
- علایق موضوعی: محتوا بر موضوعات کلیدی مانند строка, собеседование, foo, delete, o(n تمرکز دارد.
📝 توضیح و سیاست محتوایی
نویسنده این فضا را محل بیان دیدگاههای شخصی توصیف میکند:
“Номер заявления регистрацию в РКН: № 5731053751
Чат: @algoses_chat
По всем вопросам: @vice22821”
به لطف بهروزرسانیهای پرتکرار (آخرین داده در تاریخ 15 ژوئن, 2026)، کانال همواره بهروز و دارای دسترسی بالاست. تحلیلها نشان میدهد مخاطبان بهطور فعال با محتوا تعامل دارند و آن را به نقطه اثرگذاری مهم در دسته آموزش تبدیل کردهاند.
11 871
مشترکین
-124 ساعت
-127 روز
+2030 روز
آرشیو پست ها
Задача с собеседования в Zopsmart
Дана входная строка s. Переверните порядок слов в ней.
Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены хотя бы одним пробелом.
Верните строку, содержащую слова в обратном порядке, объединённые одним пробелом.
Обратите внимание, что строка s может содержать начальные или конечные пробелы, или несколько пробелов между двумя словами. В возвращаемой строке должен быть только один пробел между словами. Не включайте каких-либо лишних пробелов.
Follow-up: если строковый тип данных - изменяемый в вашем языке, можете ли вы решить задачу in-place c O(1) дополнительной памяти?
Пример 1:
Input: s = "the sky is blue"
Output: "blue is sky the"
Пример 2:
Input: s = " hello world "
Output: "world hello"
Пример 3:
Input: s = "a good example"
Output: "example good a"
Ограничения:
1 <= s.length <= 10⁴
s содержит буквы английского алфавита (в нижнем и верхнем регистре), цифры и пробелы ' '.
s состоит хотя бы из одного слова.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Так как в питоне строки неизменяемы, мы не можем реализовать решение in-place с O(1) дополнительной памяти.
Преобразуем строку в список строк методом split(), автоматически удаляя лишние пробелы - O(n).
Используем два указателя:
left - индекс первого слова в списке
right - индекс последнего слова
Пока left меньше right:
- меняем местами элементы под индексом left с элементами под индексом right;
- сдвигаем указатели навстречу друг другу.
В конце объединяем слова списка в строку через один пробел и возвращаем её.
Делитесь решением на вашем языке с O(1) дополнительной памяти в комментариях!
Сложность
O(n) - по времени (сплит и обход списка строк)
O(n) - по памяти (храним список строк)
Код
class Solution:
def reverseWords(self, s: str) -> str:
words = s.split()
left, right = 0, len(words) - 1
while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 1
return " ".join(words)
@algoses
Ваше исследование стоит того, чтобы о нем рассказать
На междисциплинарной молодежной конференции Центрального университета сможете не просто выступить, но и получить публикацию тезисов в РИНЦ и поддержку опытных исследователей.
Студентам, аспирантам и молодым ученым доступны 6 секций: гуманитарные и естественные науки, ИИ, математика, бизнес и кибербезопасность. Секцию по кибербезу делаем совместно с факультетом ВМК МГУ.
И да, будут не только доклады: пленарные сессии с учеными и инди-группа тоже в программе.
Конференция пройдет 17 мая, но тезисы нужно подать до 3 мая
Не готовы выступать? Приходите слушать. Регистрация — до 12 мая.
Repost from Поступашки - ШАД, Стажировки и Магистратура
🚀Интенсивы к ШАД: экспресс подготовка за 2 недели
Товарищи, первый этап отбора в ШАД начинается уже 30 апреля. Мы открываем наши интенсивы с разбором первого этапа, чтобы вы успели подготовиться за оставшееся время.
➡️Интенсив подойдёт, если:
🔵 поступаешь в ШАД в этом году и хочешь натаскаться за короткий срок
🔵 знаешь школьную программу, ведь этого достаточно для старта, все остальное мы возьмем на себя
🔵 уже готовился, но чувствуешь пробелы в отдельных темах
🔵 хочешь довести решение задач до автоматизма и научиться оформлять решение на полный балл
➡️ Доступны интенсивы по направлениям:
⬇️ Алгоритмы
⬇️ Теория вероятностей
⬇️ Линейная алгебра
⬇️ Математический анализ
⬇️ Дискретная математика
➡️Что внутри каждого интенсива:
🔵 Систематизированная теория + конспекты + ДЗ с проверкой от преподавателя
🔵 8 пробников и их разбор
🔵 Закрытая база заданий ШАД
🔵 Консультации и поддержка преподавателя во время отборочных
🔵 Мок-интервью к собеседованию
➡️Как устроен интенсив:
Весь материал, который нужен к первому этапу шад будет разобран до 1 мая. Весь материал, который нужен ко второму этапу будет разобран до 15 мая. На каждом курсе 3 живых семинара.
💰До 18 апреля скидки 35%:
Цена за 1 интенсив - 9 150 5 950 ₽
При покупке 2-х интенсивов - 18 300 10 900 ₽
При покупке 3-х интенсивов - 27 450 14 850 ₽
При покупке 4-х интенсивов - 36 600 17 800 ₽
При покупке от трёх и более + дискра в подарок
📌 Времени остается немного, начать подготовку нужно уже сейчас! Для вопросов и записи на курсы напишите менеджеру
В новом ролике обсудим изи темку, как получать офферы на 10 000$. Смотрим! Смотрим!
https://www.youtube.com/watch?v=ovYjaPpV6pw
Задача с собеседования в Zopsmart
Дан массив nums, состоящий из n объектов, окрашенных в красный, белый и синий цвета. Отсортируйте их in-place так, чтобы объекты одного цвета оказались соседними, следуя порядку: красные, белые, синие.
Будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего, соответственно.
Решите задачу без использования встроенной функции сортировки.
Follow up: можете ли вы реализовать однопроходный алгоритм, использующий только константную дополнительную память?
Пример 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Пример 2:
Input: nums = [2,0,1]
Output: [0,1,2]
Ограничения:
n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.
НАШ ЧАТ АЛГОРИТМИСТОВ
Сборник алгоритмический задач с собесов
Решение
Базовое решение: двухпроходный алгоритм с сортировкой подсчётом. При первом проходе - подсчитываем кол-во 0, 1 и 2. При втором - перезаписываем массив, помещая сначала все 0, затем все 1 и, наконец, все 2.
Сложность такого алгоритма: O(n) - по времени (проходим по массиву два раза) и O(1) - по памяти (храним только три переменные, перезаписываем массив in-place).
Однако, предлагаю реализовать решение с использованием однопроходного алгоритма (follow-up). Для этой задачи подойдёт алгоритм "Национальный флаг Нидерландов", использующийся для сортировки массива с тремя различными значениями за один проход.
Основная идея в разделении массива на три части (по типу цветовых границ на флаге) и использовании трёх указателей:
low (сначала равен нулю) - отслеживает границу, где должны заканчиваться 0;
mid (сначала равен нулю) - проходит по массиву слева направо;
high (сначала равен len(nums) - 1) - отслеживает границу, где должны начинаться 2.
Идём по массиву указателем mid, пока mid <=high:
Если текущий элемент равен 0: меняем его местами с элементом под индексом low и увеличиваем значения обоих указателей;
Если текущий элемент равен 1: оставляем его на месте и сдвигаем указатель mid вперёд;
Иначе, если текущий элемент равен 2: меняем его местами с элементом под индексом high и уменьшаем значение указателя high. Указатель mid не сдвигается, так как нужно проверить эл-т, который пришёл из правой части.
Сложность
O(n) - по времени
O(1) - по памяти
Код
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
low, mid = 0, 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[mid], nums[low] = nums[low], nums[mid]
mid += 1
low += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
@algoses
Алгоритмические задачи - это не только про найм. Это способ проверить, как ты думаешь: работаешь ли с ограничениями, замечаешь ли крайние случаи и умеешь ли упрощать сложное.
Сейчас есть возможность сделать это на практике.
Решайте задачу от Ильи Царева, руководителя разработки Яндекс Go, до 12.00 12 апреля.
Правильное решение даёт шанс попасть на конференцию Day&Night* Городских сервисов Яндекса, которая пройдет 18 апреля в Москве, и выиграть другие призы.
Либо через заявку и ожидание, либо интереснее - через челлендж-задачкиии! Задачки тут
*День и Ночь
Алгоритмические задачи - это не только про найм. Это способ проверить, как ты думаешь: работаешь ли с ограничениями, замечаешь ли крайние случаи и умеешь ли упрощать сложное.
Сейчас есть возможность сделать это на практике.
Решайте задачу от Ильи Царева, руководителя разработки Яндекс Go, до 12.00 11 апреля.
Правильное решение даёт шанс попасть на конференцию Day&Night* Городских сервисов Яндекса, которая пройдет 18 апреля в Москве, и выиграть другие призы.
Либо через заявку и ожидание, либо интереснее - через челлендж-задачкиии! Задачки тут
*День и Ночь
Задача с собеседования в eBay
Дано целое положительное число n. Каждой цифре n присваивается знак в соответствии со следующими правилами:
- самой старшей цифре присваивается положительный знак;
- каждая следующая цифра имеет знак, противоположный знаку предыдущей цифры.
Верните сумму всех цифр с соответствующими знаками.
Пример 1:
Input: n = 521
Output: 4
Объяснение: (+5) + (-2) + (+1) = 4.
Пример 2:
Input: n = 111
Output: 1
Объяснение: (+1) + (-1) + (+1) = 1.
Пример 3:
Input: n = 886996
Output: 0
Объяснение: (+8) + (-8) + (+6) + (-9) + (+9) + (-6) = 0.
Ограничения:
1 <= n <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Сначала разберём базовое решение:
Заводим переменные:
sign - знак текущей цифры, сначала равняется 1 (самая старшая цифра имеет положительный знак)
res - для накопления суммы цифр
Преобразуем n в строку, проходим по ней слева направо:
- присваиваем знак текущей цифре, умножая её на sign, и прибавляем к res;
- меняем sign на противоположный, умножая на -1.
Теперь оптимизируем решение, используя только математические операции без строки:
В цикле проходим по цифрам числа, от младших разрядов к старшим:
- остатком от деления получаем последнюю цифру. Обновляем сумму, вычитая из цифры предыдущий результат.
- переходим к следующему разряду, применяя целочисленное деление.
Формула гарантирует правильное присвоение знаков, так как вычитание предыдущего результата эквивалентно умножению всех накопленных цифр на -1.
К примеру, для n = 521:
res = 1 - 0 = 1
res = 2 - 1 = 1
res = 5 - (2 - 1) = 4
=> +5 - 2 + 1 = 4
Сложность
Базовое:
O(log n) - по времени (количество цифр в числе)
O(log n) - по памяти (храним строку)
Оптимизированное:
O(log n) - по времени
O(1) - по памяти (храним res)
Код
Базовое:
class Solution:
def alternateDigitSum(self, n: int) -> int:
n_str = str(n)
sign = 1
res = 0
for char in n_str:
res = res + int(char) * sign
sign *= -1
return res
Оптимизированное:
class Solution:
def alternateDigitSum(self, n: int) -> int:
res = 0
while n:
res = n % 10 - res
n //= 10
return res
@algoses
Хочешь в магистратуру, которая реально повлияет на твою карьеру?
Центральный университет проводит День открытых дверей ИТ-магистратуры 6 и 7 апреля, онлайн и офлайн в Москве!
Ты узнаешь:
— как и на какие программы можно поступить в 2026 году;
— как можно получить грант до 75%;
— как обучение приводит к работе мечты, а не просто диплому.
А также тебя ждут экскурсии по кампусу со студентами и ответы на все вопросы.
Регистрируйся и разберись, какое направление действительно тебе подходит
Задача с собеседования в eBay
Дан целочисленный массив nums. Переместите все нули в его конец, сохранив при этом относительный порядок ненулевых элементов.
Обратите внимание, что необходимо сделать это in-place, без создания копии массива.
Пример 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Пример 2:
Input: nums = [0]
Output: [0]
Ограничения:
1 <= nums.length <= 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем метод двух указателей, идём по массиву в одном направлении слева направо:
l - позиция, куда нужно поставить следующее ненулевое число
r - проходит по всем элементам массива
Проходим по массиву указателем r:
если r указывает на ненулевой элемент, меняем его местами с элементом на позиции l и двигаем левый указатель.
После завершения итерации с индексом r:
- все элементы до l будут ненулевыми;
- все элементы от l до r включительно - нули.
Вывод результата не требуется. Решение соблюдает принцип in-place (работаем с исходным массивом) и сохраняет порядок ненулевых элементов.
Сложность
O(n) - по времени (проходим по массиву один раз)
O(1) - по памяти (используем две переменные, изменяем только исходный массив)
Код
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l = 0
for r in range(len(nums)):
if nums[r] != 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
@algoses
Хэнбук по алгоритмам ШАД
Собрали и разобрали все задачи с собеседований в ШАД. Привели необходимую теорию и задачи для закрепления. Вам же осталось только сесть, разобраться и прорешать - и алгособес в кармане!
Еще больше подобных материалов на наших курсах в ШАД, залетаем в ШАД уже этим летом.
@postypashki_old
Задача с собеседования в Zoho
Дана строка s, разверните (изменив порядок на обратный) только все гласные в строке и верните полученную строку.
Гласными являются буквы 'a', 'e', 'i', 'o', и 'u'. Они могут быть как в нижнем, так и в верхнем регистре, а также встречаться более одного раза.
Пример 1:
Input: "IceCreAm"
Output: "AceCreIm"
Explanation:
Гласные в s: ['I', 'e', 'e', 'A']. После разворота гласных s превращается в "AceCreIm".
Пример 2:
Input: s = "leetcode"
Output: "leotcede"
Ограничения:
1 <= s.length <= 3 * 105
s состоит из печатных символов ASCII.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Будем использовать метод двух указателей:
left - индекс первого элемента в списке (после преобразования строки в список)
right - индекс последнего элемента
Гласные храним во множестве для быстрой проверки за O(1).
Пока left меньше right: идём по строке в двух направлениях, проверяя символы, на которые указывают left и right.
Если символ слева - не гласная: сдвигаем левый указатель;
Если символ справа - не гласная: сдвигаем правый указатель;
Если оба символа - гласные: меняем их местами и двигаем оба указателя.
Так проходим по всему списку, пока указатели не встретятся, и в конце возвращаем полученную строку.
Сложность
O(n) - по времени (так как проходим по списку один раз)
O(n) - по памяти (так как создаём список из символов строки)
Код
class Solution:
def reverseVowels(self, s: str) -> str:
s = list(s)
vowels = set("aeiouAEIOU")
left, right = 0, len(s) - 1
while left < right:
if s[left] not in vowels:
left += 1
elif s[right] not in vowels:
right -= 1
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return "".join(s)
@algoses
Repost from Поступашки - ШАД, Стажировки и Магистратура
Финальные скидки на карьерные курсы!
Камрады, сейчас разгар сезона стажировок. Самое время взять себя в руки и подтянуть хард скиллы и проходить собесы.
Поэтому мы открываем доступ к нашим карьерным курсам со скидкой 40% 🔥
Курсы подойдут начинающим специалистам, которые хотят прокачаться и уверенно проходить интервью в топовые компании.
Обучение построено так, чтобы вы прошли путь от «я ничего не знаю и не понимаю» до «могу уверенно пройти тех собес и получуть оффер». Вы научитесь решать задачи с реальных отборов, сделаете пет-проект и пройдёте пробный собес с нами, чтобы полностью быть готовым к настоящим, а также получите помощь на всех этапах отбора: от резюме до испытательного срока.
На карьерных курсах готовим по 4 направлениям:
➡️ алгоритмы старт
➡️ аналитика старт
➡️ машинное обучение старт
➡️ бэкенд разработка старт
(если не открываются ссылки, нужно скопировать и вставить в браузер)
Что входит в каждый курс:
13 450 7 950 ₽
При покупке от 2-х курсов - 7 250 ₽ за курс
При покупке от 3-х и более - 6 450 ₽ за курс
Программу и отзывы на курсы можно найти на сайте
➡️Советуем не затягивать. Для вопросов и записи на курсы напишите менеджеру
🔵Разбор донабора Т-Банка и Яндекса на весеннюю стажировку 🔵Мгновенный доступ к лекциям и семинарам - учитесь в своём темпе 🔵ДЗ и пет-проект с обратной связью от преподавателя 🔵Практика на реальных боевых задачах 🔵Банк заданий и вопросов с собеседований в BigTech 🔵Пробный тех.собес с обратной связью от эксперта 🔵Помощь на всех этапах: от составления резюме до испытательного срока 🔵Рефералка в топовую компанию по итогу прохождения курса📌 Скидка 40% действует до 18 марта Цена за 1 курс -
Repost from Поступашки - ШАД, Стажировки и Магистратура
🔥 Уже завтра стартует новый поток курсов к ШАД
До первого этапа отбора остаётся все меньше времени. Но и за этот период можно подготовиться и уверенно пройти отбор.
Поэтому если вы откладывали подготовку до последнего момента — сейчас самое время ее начать.
Курсы подготовки к ШАД / 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
Repost from Поступашки - ШАД, Стажировки и Магистратура
🔊 Добавляем курс по дискретной математике
Мы расширяем линейку курсов подготовки к ШАД / 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
Repost from Поступашки - ШАД, Стажировки и Магистратура
🔥 До отборов в ШАД осталось всего 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
