Алгоритмы - Собеседования, Олимпиады, ШАД
Kanalga Telegram’da o‘tish
Номер заявления регистрацию в РКН: № 5731053751 Чат: @algoses_chat По всем вопросам: @vice22821
Ko'proq ko'rsatish
Tarmoq:📈 Telegram kanali Алгоритмы - Собеседования, Олимпиады, ШАД analitikasi
Алгоритмы - Собеседования, Олимпиады, ШАД (@algoses) Rus til segmentidagi kanali faol ishtirokchi. Hozirda hamjamiyat 12 167 obunachidan iborat bo'lib, Taʼlim toifasida 16 649-o'rinni va Rossiya mintaqasida 52 903-o'rinni egallagan.
📊 Auditoriya ko‘rsatkichlari va dinamika
невідомо sanasidan buyon loyiha tez o‘sib, 12 167 obunachiga ega bo‘ldi.
21 Oktabr, 2026 dagi oxirgi ma’lumotlarga ko‘ra kanal barqaror faollikka ega. Oxirgi 30 kunda obunachilar soni 86 ga, so‘nggi 24 soatda esa -5 ga o‘zgardi va umumiy qamrov yuqori darajada qolmoqda.
- Tasdiqlash holati: Tasdiqlanmagan
- Jalb etish (ER): Auditoriya o‘rtacha 19.18% darajada jalb etiladi. Nashrdan keyingi dastlabki 24 soatda kontent odatda umumiy obunachilar sonining 11.13% ini tashkil etuvchi reaksiyalarni to‘playdi.
- Post qamrovi: Har bir post o‘rtacha 2 334 marta ko‘riladi; birinchi sutkada odatda 1 354 ta ko‘rish yig‘iladi.
- Reaksiyalar va o‘zaro ta’sir: Auditoriya faol: har bir postga o‘rtacha 4 ta reaksiya keladi.
- Tematik yo‘nalishlar: Kontent строка, собеседование, foo, delete, o(n kabi asosiy mavzularga jamlangan.
📝 Tavsif va kontent siyosati
Muallif resursni shaxsiy fikrni ifoda etish maydoni sifatida ta’riflaydi:
“Номер заявления регистрацию в РКН: № 5731053751
Чат: @algoses_chat
По всем вопросам: @vice22821”
Yuqori yangilanish chastotasi (oxirgi ma’lumot 22 Oktabr, 2026 da olingan) sababli kanal doimo dolzarb va katta qamrovli bo‘lib qoladi. Analitika auditoriya kontent bilan faol hamkorlik qilishini, uni Taʼlim toifasidagi muhim ta’sir nuqtasiga aylantirishini ko‘rsatadi.
12 167
Obunachilar
-524 soatlar
+17 kun
+8630 kun
Postlar arxiv
Задача с собеседования в 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
