Алгоритмы - Собеседования, Олимпиады, ШАД
رفتن به کانال در Telegram
Номер заявления регистрацию в РКН: № 5731053751 Чат: @algoses_chat По всем вопросам: @vice22821
نمایش بیشتر
شبکه:📈 تحلیل کانال تلگرام Алгоритмы - Собеседования, Олимпиады, ШАД
کانال Алгоритмы - Собеседования, Олимпиады, ШАД (@algoses) در بخش زبانی روسی بازیگری فعال است. در حال حاضر جامعه شامل 12 167 مشترک است و جایگاه 16 649 را در دسته آموزش و رتبه 52 903 را در منطقه روسيا دارد.
📊 شاخص‌های مخاطب و پویایی
از زمان ایجاد در невідомо، پروژه رشد سریعی داشته و 12 167 مشترک جذب کرده است.
بر اساس آخرین داده‌ها در تاریخ 21 اکتبر, 2026، کانال فعالیت پایداری دارد. در ۳۰ روز گذشته تغییر اعضا برابر 86 و در ۲۴ ساعت گذشته برابر -5 بوده و همچنان دسترسی گسترده‌ای حفظ شده است.
- وضعیت تأیید: تأیید نشده
- نرخ تعامل (ER): میانگین تعامل مخاطب 19.18% است و در ۲۴ ساعت نخست پس از انتشار، محتوا معمولاً 11.13% واکنش نسبت به کل مشترکان کسب می‌کند.
- دسترسی پست‌ها: هر پست به طور میانگین 2 334 بازدید دریافت می‌کند. در اولین روز معمولاً 1 354 بازدید جمع‌آوری می‌شود.
- واکنش‌ها و تعامل: مخاطبان به‌طور فعال حمایت می‌کنند؛ میانگین واکنش به هر پست 4 است.
- علایق موضوعی: محتوا بر موضوعات کلیدی مانند строка, собеседование, foo, delete, o(n تمرکز دارد.
📝 توضیح و سیاست محتوایی
نویسنده این فضا را محل بیان دیدگاه‌های شخصی توصیف می‌کند:
“Номер заявления регистрацию в РКН: № 5731053751
Чат: @algoses_chat
По всем вопросам: @vice22821”
به لطف به‌روزرسانی‌های پرتکرار (آخرین داده در تاریخ 22 اکتبر, 2026)، کانال همواره به‌روز و دارای دسترسی بالاست. تحلیل‌ها نشان می‌دهد مخاطبان به‌طور فعال با محتوا تعامل دارند و آن را به نقطه اثرگذاری مهم در دسته آموزش تبدیل کرده‌اند.
12 167
مشترکین
-524 ساعت
+17 روز
+8630 روز
آرشیو پست ها
Задача с собеседования в eBay
Дана строка s, проверьте, можно ли составить её, взяв какую-либо её подстроку и повторив её два или более раз подряд.
Пример 1:
Input: s = "abab"
Output: true
Explanation: Это подстрока "ab", повторяющаяся дважды.
Пример 2:
Input: s = "aba"
Output: false
Пример 3:
Input: s = "abcabcabcabc"
Output: true
Explanation: Это подстрока "abc", повторяющаяся четыре раза, или подстрока "abcabc", повторяющаяся дважды.
Ограничения:
1 <= s.length <= 10⁴
s состоит из строчных английских букв.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Если s состоит из повторяющихся подстрок, то у неё есть длинный собственный префикс, равный её суффиксу.
Классический метод решения задачи - префикс-функция из алгоритма Кнута-Морриса-Пратта.
Префикс-функция даёт длины наибольших бордеров для всех префиксов.
Бордер - собственный префикс строки, являющийся одновременно её суффиксом. Необходимо проверить, образует ли бордер период всей строки.
Создаем массив lps (longest prefix-suffix), где lps[i] хранит длину наибольшего собственного префикса подстроки s[0..i], который одновременно является её суффиксом.
Если при вычислении префикс-функции символы не совпадают, длина префикса (k) не сбрасывается в ноль, а "откатывается" к уже вычисленному значению для более короткого префикса.
Идём по строке слева направо, храня k - длину текущего совпавшего префикса:
Пока k > 0 (префикс непустой) и s[i] != s[k] (символы не совпали):
- "откатываемся" к наибольшему валидному бордеру меньшей длины: k = lps[k - 1] (если префикс s[0..k-1] равен суффиксу s[i-k..i-1], то любой бордер строки s[0..k-1] также является бордером и для s[0..i-1]. Наибольший такой бордер имеет длину lps[k - 1]).
Если s[i] == s[k]:
- продлеваем совпавший префикс текущим символом (k += 1).
Записываем результат: lps[i] = k.
Разберем на примере 1, где s = "abab":
- Подстрока "a" (i = 0): собственных префиксов нет => lps[0] = 0.
- Подстрока "ab" (i = 1): префикс "a" != суффикс "b" => lps[1] = 0.
- Подстрока "aba" (i = 2): префикс "a" == суффикс "a" => lps[2] = 1.
- Подстрока "abab" (i = 3): префикс "ab" == суффикс "ab" => lps[3] = 2.
Получившийся массив lps: [0, 0, 1, 2]
L (длина бордера всей строки) = lps[n - 1]. Если L > 0, то префикс длины L совпадает с суффиксом длины L: s[0..L-1] == s[n-L..n-1].
Суффикс начинается с индекса n - L, т.е. для любого индекса j от 0 до L-1 будет выполняться s[j] == s[j + (n - L)]. Таким образом, строка сдвигается сама на себя с шагом p = n - L.
p - кандидат на длину минимального периода.
Чтобы строка состояла из точных повторов этого периода, должны выполняться следующие два условия:
- L > 0 (иначе p = n и n % n == 0 даст true для любой строки, к примеру, "abcd")
- n % p == 0 (общая длина строки должна нацело делиться на длину периода. К примеру, для "ababa", где n = 5, L = 3, p = 2 и 5 % 2 != 0).
Сложность
O(n) - по времени (k увеличивается не более чем на 1 за каждую итерацию внешнего цикла for, в цикле while - k только уменьшается. Таким образом, суммарное число итераций while не превышает n)
O(n) - по памяти (строим массив lps)
Код
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
lps = [0] * n
for i in range(1, n):
k = lps[i - 1]
while k > 0 and s[i] != s[k]:
k = lps[k - 1]
if s[i] == s[k]:
k += 1
lps[i] = k
L = lps[n - 1]
p = n - L
return L > 0 and n % p == 0
@algoses
Что делать с данными? 💬
Строить отчёты. А ещё, например:
✅находить закономерности в больших массивах; ⬜️предсказывать поведение пользователей; ⬜️строить рекомендательные системы; ⬜️обучать и улучшать ML-модели; ⬜️создавать продукты и помогать бизнесу расти.В Школе аналитиков данных МТС учатся решать такие задачи на практике. В программе — SQL и Python, математика и статистика, анализ данных, машинное обучение и большие данные, а также нейросети и рекомендательные системы. Занятия ведут действующие эксперты Центра BigData MWS. Теория чередуется с практикой, а преподаватели дают обратную связь по работам и помогают отслеживать прогресс. Это будет интересно:
➡️студентам последних курсов и выпускникам технических вузов ➡️алитикам данных, которые хотят погружаться в исследования ➡️ИТ-специалистам, которые хотят перейти в новое для себя направлениеОбучение продлится 10 месяцев и будет полностью бесплатным. ⚡️ Сейчас — последний шанс подать заявку, так как прием закрывается 25 октября. Для поступления кандидатам предстоит заполнить анкету, написать мотивационное письмо и пройти отборочное тестирование. Отправить заявку ↗️
Стажировка в BigTech или ШАД? Будь готов, что спросят про LLM.
На собесах в ML всё чаще говорят про агентов, RAG и свежие модели. Пока ты решаешь матан, индустрия уже ушла туда.
Каждый день разбираем коротко, с кодом и ссылками на статьи. Чтобы на собесе было что рассказать.
🎁 А для своих собрали папку для подготовки-: матан, бесплатные книги по ИИ и стажировки.
Читай до собеса, а не после: t.me/data_analysis_ml
Задача с собеседования в OYO
Дан целочисленный массив nums. Верните все тройки [nums[i], nums[j], nums[k]] такие, что i != j, i != k и j != k, а также nums[i] + nums[j] + nums[k] == 0.
Обратите внимание, что результирующий набор не должен содержать дублирующиеся тройки.
Пример 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
Искомые тройки: [-1,0,1] и [-1,-1,2].
Обратите внимание, что порядок вывода и порядок троек не имеют значения.
Пример 2:
Input: nums = [0,1,1]
Output: []
Explanation: Сумма единственной возможной тройки не равна 0.
Пример 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: Единственная возможная тройка даёт в сумме 0.
Ограничения:
3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Для оптимального решения используем предварительную сортировку и метод двух указателей, движущихся навстречу друг другу.
После сортировки сумма будет монотонно зависеть от положения указателей: если сдвигаем l вправо - сумма не уменьшается (растёт или остаётся прежней из-за дубликатов), если сдвигаем r влево - сумма не увеличивается (уменьшается или остаётся прежней из-за дубликатов). Сортировка также упрощает обработку дубликатов, которые теперь стоят рядом.
Фиксируем первое число тройки как nums[i] и проходим переменной i по массиву nums.
Если nums[i] > 0: прерываем цикл, так как оставшиеся числа точно положительные.
Если i > 0 и nums[i] == nums[i - 1]: пропускаем текущую итерацию, так как встретили дубликат первого числа в тройке.
Инициализируем указатели:
l - указывает на эл-т, следующий за текущим i
r - указывает на последний эл-т массива
Пока l меньше r, двигаем указатели навстречу друг другу:
Вычисляем общую сумму тройки эл-в.
Если сумма больше 0:
- уменьшаем r.
Если сумма меньше 0:
- увеличиваем l.
Если сумма равна 0:
- добавляем эту тройку в res;
- сдвигаем l вправо и пропускаем дубликаты nums[l], если они есть, сдвигая l ещё раз вправо.
Возвращаем res, содержащий все уникальные тройки, сумма которых равна 0.
Сложность
O(n^2) - по времени (сортировка - O(n log n); внешний цикл - O(n), на каждой итерации i - проход двумя указателями в цикле while за O(n). Итого: O(n^2))
O(1) - по памяти (храним некоторое кол-во переменных; без учёта сортировки)
Код
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
res = []
for i in range(len(nums)):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
three_sum = nums[i] + nums[l] + nums[r]
if three_sum > 0:
r -= 1
elif three_sum < 0:
l += 1
else:
res.append([nums[i], nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l - 1]:
l += 1
return res
@algoses
+4💬👨💻🐍💩🤖🤖🐧👩💻🧑💻👋🦀
Дождались! Ребята сделали крутейший канал про IT новой эпохи
Нейросети, ИИ-агенты, вайбкодинг, вайбхакинг и новые инструменты уже меняют привычный мир технологий.
Там разбирают эти изменения и другие интересные IT-темы на простых картинках и понятном языке, а еще делятся полезными ресурсами и свежими новостями
Подписывайтесь: @IT_Portal
+4Рынок пока жив, и мы это видим
Последнее время вокруг IT много разговоров, что рынок сдулся, вакансий нет, компании фризят найм.
Несмотря на всю ситуации, наших студентов приглашают на интервью, и они собирают офферы 💰
Кто-то пришёл на СТАРТ летом, кто-то подключился к ПРО в сентябре. И сейчас мы уже видим результаты!
Почему у них получается? Потому что после курсов ребята выходят на рынок осознанно и готовыми ко всему пути до оффера. Этим и выигрывают на фоне тех, кто бездумно откликается, валит собесы и винит во всем рынок.
Как вас ведем до оффера:
➡️Сначала закрываем техническую часть: теория, много практики, ДЗ и пет-проекты с проверкой, реальные задачи и вопросы с собеседований, подготовка к техническим секциям
➡️Далее преподаватели помогают собрать карьерную стратегию: понять, куда подаваться, как упаковать опыт, оформить резюме и LinkedIn, писать сопроводительные и выстроить стратегию откликов так, чтобы повышать шанс попасть на собеседование
➡️Отрабатываем на практике: mock-собеседования, где в условиях, приближенным к реальному собеседованию, вы проходите техническую секцию и мотивационную
К моменту выхода на рынок у вас уже собрана вся подготовка:
харды + проекты + резюме + упакованный опыт + стратегия откликов + навык проходить собеседования
Лучшим студентам мы помогаем с рефералками и рекомендуем их в компании.
А если вы прошли курсы, выполнили рекомендации, но оффер не получили — вернём деньги.
Через 4 часа распродажа закрывается.
➡️Любой курс СТАРТ или ПРО — 8 350 ₽
➡️Комбо: СТАРТ + ПРО — 14 950 ₽
➡️Ультра-комбо: СТАРТ+ПРО+Алгоритмы СТАРТ — 20 950 ₽, а Алгоритмы ПРО получаешь в подарок
И это последнее понижение цен на курсы СТАРТ и ПРО в этом году.
⭐ЗАПИСАТЬСЯ НА КУРС⭐️
Стажировки отменили? Диплом теперь будут проверять?
С 1 марта 2027 года в России меняются правила стажировок.
Теперь «стажировка в сфере труда» будет официально привязана к вашему образованию или полученной квалификации.
То есть стажироваться можно будет по профессии, специальности или направлению, которое вы осваиваете или уже освоили, либо по новой квалификации, которую получили через профессиональное обучение / переподготовку.
И ещё два новых ограничения:
➡️ договор о стажировке можно заключить не позднее года после соответствующего обучения
➡️ сама стажировка может длиться максимум 6 месяцев
Ничего непонятно? Сейчас объясним
Допустим, вы учитесь на лингвиста, экономиста или химика, но в последнее время думаете:
«Когда-нибудь попробую себя аналитиком».
Или сначала хотите сходить на стажировку в аналитику, потом попробовать ML, а потом решить, что вам вообще ближе.
Так вот, товарищи, с 2027 года рассчитывать на стажировку как на универсальный способ «просто попробовать любую профессию» станет сложнее. Для стажировки направление должно быть связано с вашим образованием или новой квалификацией.
Поэтому если вы давно хотели попробовать себя в аналитике, ML, backend или другом IT-направлении, рекомендуем использовать ближайшие отборы и стажировки, ибо в следующем году это будет сделать сложнее.
В этом вам помогут наши карьерные курсы СТАРТ и ПРО мы как раз готовим к стажировкам, упаковываем ваш опыт и даем конкретный план, как действовать с учетом новых правил.
До 18 октября 23:59 все курсы доступны с большой скидкой, идут последние часы, торопитесь присоединиться!
➡️ Записаться
+1Самая большая и последняя распродажа карьерных курсов СТАРТ И ПРО в этом году, где тебя 100% доведут до оффера по 5 направлениям:
⏩ Аналитика
⏩ Machine Learning
⏩ Backend
⏩ Алгоритмы
⏩ AI-агенты
Как выбрать уровень?
➡️ СТАРТ — если только начинаешь карьеру, меняешь направление или нужно укрепить базу. Собираем системный фундамент и готовим к стажировкам и первой работе
➡️ ПРО — если база уже есть и хочется быть сильнее других кандидатов: углубляем знания, разбираем сложные задачи и помогаем двигаться от junior к senior
Подробная программа
Всем участникам доступны:
🔵 разборы контестов в Яндекс (стажировка, IWO), Т-Банк (донабор), Kaspersky (GO, Python) и другие программы 🔵 закрытая база собесов и тестовых заданий Бигтехов: Яндекс, Т-банк, Ozon, Cбер и так далее 🔵 ДЗ и пет-проекты проверкой, помощь с резюме, рефералками в бигтех 🔵mock-собеседования HR/технических собесов с обратной связью 🔵 курс по выходу на доход в валюте: LinkedIn, валютные вакансии, позиционирование и прохождение интервью.А еще мы гарантируем результат Проходишь курсы, выполняешь рекомендации, но не получаешь оффер — вернём деньги Отзывы 🔊Распродажа закончится 18 октября в 23:59. И это последний набор в этом году, когда можно попасть на эти карьерные курсы с проверкой ДЗ, мок-собесами и и карьерной поддержкой. Дальше такой возможности в этом году уже не будет. ⭐ЗАПИСАТЬСЯ НА КУРС⭐️
Задача с собеседования в eBay
Дано целое положительное число n, найдите и верните максимальное расстояние между любыми двумя соседними единицами в его двоичном представлении. Если в числе нет двух соседних единиц, верните 0.
Две единицы считаются соседними, если между ними находятся только нули (возможно, ни одного нуля). Расстояние между двумя единицами - это абсолютная разность между их битовыми позициями. Например, расстояние между двумя единицами в "1001" равняется 3.
Пример 1:
Input: n = 22
Output: 2
Explanation: 22 в двоичном представлении - "10110".
Первая пара соседних единиц: "10110" с расстоянием 2.
Вторая пара соседних единиц: "10110" с расстоянием 1.
Ответ - наибольшее из этих двух расстояний, то есть 2.
Обратите внимание, что пара "10110" не является допустимой, так как между подчёркнутыми единицами стоит ещё одна единица, разделяющая их.
Пример 2:
Input: n = 8
Output: 0
Explanation: 8 в двоичном представлении - "1000".
В двоичном представлении числа 8 нет ни одной пары соседних единиц, поэтому возвращаем 0.
Пример 3:
Input: n = 5
Output: 2
Explanation: 5 в двоичном представлении - "101".
Ограничения:
1 <= n <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Итак, необходимо найти максимальную разность между соседними единицами. Заметим, что нам не нужно хранить все позиции, достаточно обновлять позицию последней встреченной единицы (last_pos), чтобы при встрече следующей вычислить расстояние между ними.
Соседство единиц гарантируется тем, что last_pos обновляется только на единицах; если текущий бит - ноль, last_pos не меняется. Соответственно, когда встречаем следующую единицу, она является ближайшей (т.е. соседней) к последней встреченной.
Заводим переменные:
max_gap - для хранения максимального расстояния; инициализируем как 0 (если в числе нет соседних единиц, вернём 0)
current_pos - текущая позиция бита; начинаем с младшего (0)
last_pos - позиция последней встреченной единицы; изначально -1, так как ещё нет ни одной обработанной единицы.
Пока в n есть хотя бы один необработанный бит, проходим от младшего бита к старшему (справа налево):
- Проверяем, является ли текущий бит единицей с помощью операции побитового И: если (n & 1) == 1, значит, бит равен единице.
- Если это единица, и единица уже встречалась ранее (last_pos != -1):
- обновляем max_gap, если расстояние между текущей позицией бита и позицией последней встреченной единицы (current_pos - last_pos) больше текущего.
- Запоминаем текущую позицию как "последнюю встреченную единицу". Таким образом, следующая единица будет сравниваться с этой.
- В конце итерации:
- сдвигаем n вправо на один бит (с помощью операции n >>= 1 отбрасываем обработанный младший бит, следующий бит становится младшим);
- увеличиваем текущую позицию на 1.
Когда n обнулилось (не осталось ни одного бита), возвращаем max_gap, хранящий накопленный максимум.
Сложность
O(log n) - по времени (кол-во итераций равняется кол-ву бит в числе)
O(1) - по памяти (храним некоторое кол-во переменных)
Код
class Solution:
def binaryGap(self, n: int) -> int:
max_gap = 0
current_pos = 0
last_pos = -1
while n:
if n & 1:
if last_pos != -1:
max_gap = max(max_gap, current_pos - last_pos)
last_pos = current_pos
n >>= 1
current_pos += 1
return max_gap
@algoses
Собеседование ШАД 2026 года
В прикрепленном файле задачи, которые спрашивали в этом году. Если хотите добавить задачу с вашего собеседования пишите @vice22821. Взамен могу провести консультацию по любым вопросам или поделиться своими материалами. Еще больше материалов на наших курсах.
Математика
Раньше было 10-15 простых задач на минуту, затем предлагали на 15 минут 3 задачи посложнее на матан, линал, теорве вер. Сейчас же предлагали только 4 задачи посложнее на 25 минут: матан, линал, теор вер, дискретная математика, анализ данных. Нужно выбрать 2 задачи и рассказать их решение, ответить на доп вопросы.
Алгоритмы
Секция алгоритмов осталась той же: одна задача аля leetcode на 30 минут. Нужно рассказать решение, сделать оценку сложности и написать код. А также ответить на доп вопросы интервьюера.
Собеседование — это главная отсечка тех, кто реально готовился. Потому что формат очень необычный и к нему лучше готовиться заранее. На этом этапе валятся даже сильные ребята из топовых ВУЗов. Потому что все таки в классический академических курсах не учат решать задачи на идею: обычно это просто изучение абстрактной теории и нарешка стандартных задач на алгоритм. Да и собесы там проходить тоже не учат.
На наших же курсах основной упор делается именно на решение идейных задач, вся теория в лекциях разбирается на задачах. Мы тренируемся решать задачу вслух как на реальном собеседовании, учимся отвечать на злые вопросы интервьюера без паники за счет живых семинаров, консультаций и мок собесов. Мы настолько уверены в своем подходе, что даем гарантию поступления. Стартуем уже в понедельник, успей записаться по последней скидке!
➡ Записаться
Подписаться: @matesha_shad
Repost from Поступашки - ШАД, Стажировки и Магистратура
12 октября стартует подготовка к ШАДу
90% наших учеников, поступивших в ШАД, советуют начинать подготовку как можно раньше. Весенний отбор кажется далёким, но за это время нужно не только пройти темы, а ещё научиться уверенно решать задачи и уметь проходить экзамены и собесы в формате ШАД.
В этот понедельник стартуют наши курсы по поступлению в ШАД. И ты успеваешь присоединиться к старту потока.
Готовим по 6 направлениям:
⏩Алгоритмы
⏩Анализ данных
⏩Линейная алгебра
⏩Теория вероятностей
⏩Дискретная математика
⏩Математический анализ
За 3 месяца пройдём путь от базовых понятий до сложных задач. В основе курсов — практика:
🔵ДЗ и еженедельные пробники с проверкой
🔵Обратная связь по твоему решению: где ошибка и что доработать
🔵Задачи прошлых отборов и закрытая база для самостоятельной практики
🔵Пробный экзамен и мок-собеседования
Каждый год мы подробно разбираем все этапы экзамена: смотрим, какие темы появляются чаще, какие задачи повторяются, какие паттерны встречаются в отборах. На основе этого анализа строится программа курсов —
вы готовитесь к тому, что реально будет на экзамене.
🔊Скидки к запуску действуют до 11 октября
Собери комбо из предметов для системной подготовки по спеццене. Расписание курсов не пересекается, удобно совмещать с учебой и работой, а если что-то не получается, то куратор поможет.
Остались вопросы, или ты не уверен, что курс подойдет тебе? Пиши в личку менеджеру — поможем и объясним ▶️
⭐️ЗАПИСАТЬСЯ НА КУРС⭐️
Repost from Поступашки - ШАД, Стажировки и Магистратура
Через 2 часа вебинар про ШАД
Сегодня в 19:00 МСК разберёмся, кому и зачем нужен ШАД, как устроено поступление и что на самом деле проверяют на отборе. А ещё решим задачи и посмотрим, в каких местах ИИ может ошибаться.
Если думаете о поступлении, но пока не понимаете, с чего начать, приходите послушать экспертов и задать им вопросы.
🔗 Ссылка на вебинар
Ближе к началу пришлём ещё одно напоминание в @Postupashkianalitycsbot
Подключайтесь к боту, чтобы не пропустить эфир.
Задача с собеседования в Josh Technology
Обмен определяется как выбор двух различных позиций в массиве и перестановка их значений местами.
Круговой массив определяется как массив, в котором первый и последний элементы считаются соседними.
Дан бинарный круговой массив nums. Верните минимальное количество обменов, необходимых для того, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте.
Пример 1:
Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Есть несколько способов сгруппировать все 1 вместе:
[0,0,1,1,1,0,0] с использованием 1 обмена.
[0,1,1,1,0,0,0] с использованием 1 обмена.
[1,1,0,0,0,0,1] с использованием 2 обменов (используя круговое свойство массива).
Не существует способа сгруппировать все 1 вместе, не выполнив ни одного обмена.
Таким образом, минимальное необходимое количество обменов - 1.
Пример 2:
Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: Есть несколько способов сгруппировать все 1 вместе:
[1,1,1,0,0,0,0,1,1] с использованием 2 обменов (используя круговое свойство массива).
[1,1,1,1,1,0,0,0,0] с использованием 2 обменов.
Не существует способа сгруппировать все 1 вместе с использованием 0 или 1 обменов.
Таким образом, минимальное необходимое количество обменов - 2.
Пример 3:
Input: nums = [1,1,0,0,1]
Output: 0
Explanation: Все 1 уже сгруппированы вместе, учитывая круговое свойство массива.
Таким образом, минимальное количество обменов - 0.
Ограничения:
1 <= nums.length <= 10⁵
nums[i] равно 0 или 1.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Обратим внимание, что кол-во единиц, которые нужно сгруппировать, фиксировано и равняется общему кол-ву единиц в массиве (total_ones). Так как единицы могут быть разбросаны по массиву, необходимо проверить каждый подмассив длиной total_ones и определить среди них тот, в котором уже находится максимальное кол-во единиц (а следовательно потребуется меньше обменов).
=> Кол-во необходимых обменов равняется кол-ву нулей в подмассиве с максимумом единиц (кол-во нулей = total_ones - максимальное кол-во единиц в окне).
Чтобы избежать повторного подсчёта нулей в подмассиве, используем метод "скользящего окна" с двумя указателями.
total_ones - размер окна (определяем методом count())
window_ones - счётчик единиц в текущем окне
max_window_ones - лучший результат по кол-ву единиц в окне
l - левая граница окна
r - правая граница окна
Если общее кол-во единиц в массиве равно 1 или 0:
- возвращаем 0, так как группировать нечего.
Для корректной обработки окон в циклическом массиве - проходим 2n итераций, беря индексы по модулю (% n), что позволит вернуться в начало при выходе за правую границу.
Проходим по массиву правым указателем:
- Добавляем правый эл-т в окно.
- Если длина окна превысила total_ones:
- убираем один эл-т слева;
- сдвигаем l вправо.
- Обновляем max_window_ones.
Возвращаем ответ как разность между общим кол-вом единиц и кол-вом единиц в наиболее «единичном» окне.
Сложность
O(n) - по времени (проходим 2n итераций, константа отбрасывается)
O(1) - по памяти (храним некоторое кол-во переменных)
Код
class Solution:
def minSwaps(self, nums: list[int]) -> int:
n = len(nums)
total_ones = nums.count(1)
if total_ones <= 1:
return 0
l = 0
window_ones = max_window_ones = 0
for r in range(n * 2):
window_ones += nums[r % n]
if r - l + 1 > total_ones:
window_ones -= nums[l % n]
l += 1
max_window_ones = max(max_window_ones, window_ones)
return total_ones - max_window_ones
Оптимизация
Решение можно оптимизировать, сохранив текущую асимптотику:
Так как размер окна фиксирован (total_ones), можем обойтись без левого указателя: считаем кол-во единиц в первом окне, а затем проходим по массиву, совершая n сдвигов. На каждой итерации прибавляем входящий эл-т и вычитаем уходящий. Проверка на превышение длины окна не требуется.
Кол-во операций сократится до n (сдвиги) + total_ones (построение первого окна).
Пишите оптимизированный вариант кода в комментариях!
@algoses
Собеседование по алгоритмам в ШАД 2026
На прикрепленном фото задачи, которые спрашивали в этом году. Если хотите добавить задачу с вашего собеседования пишите @vice22821. Взамен могу провести консультацию по любым вопросам или поделиться своими материалами.
Никаких изменений с форматом в этом году почти не было, все также одна задача на полчаса, нужно решение и код, могли быть доп вопросы и как бонус предлагался чужой код на оценку.
Но формат достаточно интенсивный и для подготовки мало просто прорешать 200 задач с литкода. Нужно научиться быстро распознать паттерны, сходу писать оптимальный код, параллельно поясняя решение. Именно к этому готовят наши курсы. Как раз на семинарах и мок собесах мы учимся рассказывать решения вслух, получаем развернутый фидбэк и учимся действовать в сложных ситуация: что делать если не понимаешь условие, не можешь придумать решение или получил неожиданный вопрос. На наших курсах индивидуальный и структурированный подход, а не тупая алго дрочка. Записывайся и поступай с гарантией!
➡ Записаться
Подписаться: @algoses
+3Ты поступишь в ШАД
Старт набора на наши ШАДовские курсы: без воды и лишней теории, 3 месяца семинаров, пробников и лекций! За результат отвечаем ⭐️пройдешь курсы, но не поступишь в ШАД - вернем деньги⭐️ Программы и подробности:
⏩Алгоритмы
⏩Анализ данных
⏩Линейная алгебра
⏩Теория вероятностей
⏩Дискретная математика
⏩Математический анализ
Можно взять один курс, или комбо по спеццене! Даже все 6 сразу — программа выстроена так, что ты все успеешь. Не веришь — чекай отзывы наших выпускников!
Курсы для тебя, если ты:
🔵Только задумался о подготовке
🔵Уже готовился, но не уверен в себе
🔵Подзабыл математику, но хочешь в ШАД
🔵Хочешь совмещать подготовку с работой
🔵Готовишься к собесам в BigTech, АА и маги
Записи и материалы остаются навсегда, а сдать ДЗ, пробники, пройти мок-собес и получить фидбэк куратора можно после окончания курса!
Только у нас ты получишь:
🔵Онлайн-семинары, лекции, ДЗ и пробники с проверкой 🔵Разбор отбора 2027, саппорт с анкетой и мотивацией 🔵Доступ к закрытой базе знаний и протоколам ШАД 🔵Пробное тестирование, экзамен и собеседование 🔵Сборник всех задач ШАДа для самоподготовкиДля вопросов и записи пиши менджеру: @menshe_treh ▶️
Задача с собеседования в Zoho
Даны две строки: s и goal. Верните true, если можно поменять местами два символа в строке s так, чтобы в результате она стала равна строке goal. В противном случае верните false.
Под обменом символов понимается выбор двух индексов i и j (индексация начинается с 0) таких, что i != j, и перестановка символов s[i] и s[j] местами.
Например, обмен символов по индексам 0 и 2 в "abcd" даёт "cbad".
Пример 1:
Input: s = "ab", goal = "ba"
Output: true
Explanation: Вы можете поменять местами s[0] = "a" and s[1] = "b", чтобы получить "ba", что равно goal.
Пример 2:
Input: s = "ab", goal = "ab"
Output: false
Explanation: Единственные символы, которые можно поменять местами - это s[0] = "a" and s[1] = "b", в результате чего "ba" != goal.
Пример 3:
Input: s = "aa", goal = "aa"
Output: true
Explanation: Вы можете поменять местами s[0] = "a" and s[1] = "a", чтобы получить "aa", что равно goal.
Ограничения:
1 <= s.length, goal.length <= 2 * 10⁴
s и goal состоят из строчных букв.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Итак, нам нужно обменять ровно две позиции строки s, в которых s и goal различаются; остальные позиции должны совпадать сразу.
=> различий между строками должно быть либо 2 (так как один обмен исправляет только два различия), либо 0 (то есть строки уже эквивалентны).
Обрабатываем следующие случаи:
- Если длина s и goal различается:
False, так как обмен символов не изменит разницу в кол-ве символов.
- Если строки уже эквивалентны:
Необходимо наличие повторяющегося символа (проверяем, есть ли он, через сравнение строки со множеством), так как только обмен одинаковых символов не изменит строку s, уже равную goal. В этом случае возвращается true, иначе - false.
- Если строки разные:
Ищем две различающиеся позиции и проверяем, можно ли поменять два символа ровно одним обменом, чтобы получить goal.
diff - массив индексов, где s[i] != goal[i].
Проходим по строке s:
Если символ по текущему индексу в s отличается от символа по текущему индексу в goal:
- добавляем индекс в diff.
Если кол-во различающихся индексов становится больше 2:
- False, так как одного обмена, затрагивающего две позиции, недостаточно для исправления различий.
Если не нашли 2 различающихся индекса (len(diff) == 1):
- False, так как обмен меняет две позиции и не может покрыть одну позицию без создания нового различия в другой позиции.
Если нашли ровно 2 различающихся индекса:
- проверяем, можем ли перекрёстно поменять символы местами, чтобы получить goal.
Сложность
O(n) - по времени (в худшем случае (когда строки равны) делаем два линейных прохода)
O(1) - по памяти (diff хранит не более трёх индексов (на третьем - выход), set(s) хранит только уникальные символы, т.е. не более 26 эл-в)
Код
class Solution:
def buddyStrings(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
if s == goal:
return len(set(s)) < len(s)
diff = []
for i in range(len(s)):
if s[i] != goal[i]:
diff.append(i)
if len(diff) > 2:
return False
if len(diff) != 2:
return False
i, j = diff
return s[i] == goal[j] and s[j] == goal[i]
@algoses
Repost from Поступашки - ШАД, Стажировки и Магистратура
+3Ты поступишь в ШАД
Старт набора на наши ШАДовские курсы: без воды и лишней теории, 3 месяца семинаров, пробников и лекций! За результат отвечаем ⭐️пройдешь курсы, но не поступишь в ШАД - вернем деньги⭐️ Программы и подробности:
⏩Алгоритмы
⏩Анализ данных
⏩Линейная алгебра
⏩Теория вероятностей
⏩Дискретная математика
⏩Математический анализ
Можно взять один курс, или комбо по спеццене! Даже все 6 сразу — программа выстроена так, что ты все успеешь. Не веришь — чекай отзывы наших выпускников!
Курсы для тебя, если ты:
🔵Только задумался о подготовке
🔵Уже готовился, но не уверен в себе
🔵Подзабыл математику, но хочешь в ШАД
🔵Хочешь совмещать подготовку с работой
🔵Готовишься к собесам в BigTech, АА и маги
Записи и материалы остаются навсегда, а сдать ДЗ, пробники, пройти мок-собес и получить фидбэк куратора можно после окончания курса!
Только у нас ты получишь:
🔵Онлайн-семинары, лекции, ДЗ и пробники с проверкой 🔵Разбор отбора 2027, саппорт с анкетой и мотивацией 🔵Доступ к закрытой базе знаний и протоколам ШАД 🔵Пробное тестирование, экзамен и собеседование 🔵Сборник всех задач ШАДа для самоподготовкиОстались вопросы, или ты не уверен, что курс подойдет тебе? Пиши в личку менеджеру — поможем и объясним ▶️
Как залететь в хфт и стать миллионером, залутать сочную зумершку? Обсудим в новом ролике. Смотрим! Смотрим!
https://www.youtube.com/watch?v=zXQSoJjgQG8
Задача с собеседования в Zoho
Даны две строки s и t. Определите, являются ли они изоморфными.
Две строки s и t называют изоморфными, если символы в строке s можно заменить так, чтобы получить t.
Все вхождения определённого символа должны быть заменены другим символом с сохранением порядка следования символов. Никакие два разных символа не могут заменяться одним и тем же символом, однако, символ может быть заменён на самого себя.
Пример 1:
Input: s = "egg", t = "add"
Output: true
Explanation: Строки s и t можно сделать идентичными, если:
Заменить "e" на "a".
Заменить "g" на "d".
Пример 2:
Input: s = "f11", t = "b23"
Output: false
Explanation: Строки s и t невозможно сделать идентичными, так как символ "1" должен соответствовать одновременно и "2" и, "3".
Пример 3:
Input: s = "paper", t = "title"
Output: true
Ограничения:
1 <= s.length <= 5 * 10⁴
t.length == s.length
s и t состоят из любых допустимых символов ASCII.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Для изоморфности двух строк необходимо, чтобы обеспечивалось взаимно-однозначное соответствие:
- каждому эл-ту первой строки соответствует ровно один эл-т второй строки;
- и наоборот, каждый эл-т второй строки связан ровно с одним эл-том первой строки.
Создаём два словаря для двусторонней проверки соответствия:
s_to_t - гарантирует, что один и тот же символ из s не будет превращён в разные символы в t
t_to_s - гарантирует обратное условие: один и тот же символ из t не будет получаться из разных символов s
Проходим по двум строкам одновременно с помощью функции zip(), объединяющей эл-ты из двух строк в пары символов:
Если char_s уже встречался ранее и соответствовал другому символу, а не char_t ИЛИ
Если char_t уже был получен из другого символа строки s, а не из char_s:
- изоморфность нарушена => возвращаем False.
Иначе - записываем новые двухсторонние соответствия:
- в какой символ t превращается символ из s;
- из какого символа s получается символ t.
Если правила ни разу не нарушились, значит, строки изоморфны => возвращаем True.
Сложность
O(n) - по времени (проходим по строке один раз; операции со словарем - за O(1))
O(n) - по памяти (в худшем случае, когда все символы уникальные)
Код
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
s_to_t, t_to_s = {}, {}
for char_s, char_t in zip(s, t):
if (char_s in s_to_t and s_to_t[char_s] != char_t) or \
(char_t in t_to_s and t_to_s[char_t] != char_s):
return False
s_to_t[char_s] = char_t
t_to_s[char_t] = char_s
return True
@algoses
Как залететь в хфт и стать миллионером, залутать сочную зумершку? Обсудим в новом ролике. Смотрим! Смотрим!
https://www.youtube.com/watch?v=zXQSoJjgQG8
