Задача с собеседования в 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
Даны две строки: 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 состоят из строчных букв.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
=> различий между строками должно быть либо 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(1) - по памяти (diff хранит не более трёх индексов (на третьем - выход), set(s) хранит только уникальные символы, т.е. не более 26 эл-в)
Код
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
🔥4❤2
Ты поступишь в ШАД
Старт набора на наши ШАДовские курсы: без воды и лишней теории, 3 месяца семинаров, пробников и лекций! За результат отвечаем⭐️ пройдешь курсы, но не поступишь в ШАД - вернем деньги⭐️ Программы и подробности:
⏩ Алгоритмы
⏩ Анализ данных
⏩ Линейная алгебра
⏩ Теория вероятностей
⏩ Дискретная математика
⏩ Математический анализ
Можно взять один курс, или комбо по спеццене! Даже все 6 сразу — программа выстроена так, что ты все успеешь. Не веришь — чекай отзывы наших выпускников!
Курсы для тебя, если ты:
🔵 Только задумался о подготовке
🔵 Уже готовился, но не уверен в себе
🔵 Подзабыл математику, но хочешь в ШАД
🔵 Хочешь совмещать подготовку с работой
🔵 Готовишься к собесам в BigTech, АА и маги
Записи и материалы остаются навсегда, а сдать ДЗ, пробники, пройти мок-собес и получить фидбэк куратора можно после окончания курса!
Только у нас ты получишь:
Для вопросов и записи пиши менджеру: @menshe_treh▶️
Старт набора на наши ШАДовские курсы: без воды и лишней теории, 3 месяца семинаров, пробников и лекций! За результат отвечаем
Можно взять один курс, или комбо по спеццене! Даже все 6 сразу — программа выстроена так, что ты все успеешь. Не веришь — чекай отзывы наших выпускников!
Курсы для тебя, если ты:
Записи и материалы остаются навсегда, а сдать ДЗ, пробники, пройти мок-собес и получить фидбэк куратора можно после окончания курса!
Только у нас ты получишь:
🔵 Онлайн-семинары, лекции, ДЗ и пробники с проверкой🔵 Разбор отбора 2027, саппорт с анкетой и мотивацией🔵 Доступ к закрытой базе знаний и протоколам ШАД🔵 Пробное тестирование, экзамен и собеседование🔵 Сборник всех задач ШАДа для самоподготовки
Для вопросов и записи пиши менджеру: @menshe_treh
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥1
Собеседование по алгоритмам в ШАД 2026
На прикрепленном фото задачи, которые спрашивали в этом году. Если хотите добавить задачу с вашего собеседования пишите @vice22821. Взамен могу провести консультацию по любым вопросам или поделиться своими материалами.
Никаких изменений с форматом в этом году почти не было, все также одна задача на полчаса, нужно решение и код, могли быть доп вопросы и как бонус предлагался чужой код на оценку.
Но формат достаточно интенсивный и для подготовки мало просто прорешать 200 задач с литкода. Нужно научиться быстро распознать паттерны, сходу писать оптимальный код, параллельно поясняя решение. Именно к этому готовят наши курсы. Как раз на семинарах и мок собесах мы учимся рассказывать решения вслух, получаем развернутый фидбэк и учимся действовать в сложных ситуация: что делать если не понимаешь условие, не можешь придумать решение или получил неожиданный вопрос. На наших курсах индивидуальный и структурированный подход, а не тупая алго дрочка. Записывайся и поступай с гарантией!
➡ Записаться
Подписаться: @algoses
На прикрепленном фото задачи, которые спрашивали в этом году. Если хотите добавить задачу с вашего собеседования пишите @vice22821. Взамен могу провести консультацию по любым вопросам или поделиться своими материалами.
Никаких изменений с форматом в этом году почти не было, все также одна задача на полчаса, нужно решение и код, могли быть доп вопросы и как бонус предлагался чужой код на оценку.
Но формат достаточно интенсивный и для подготовки мало просто прорешать 200 задач с литкода. Нужно научиться быстро распознать паттерны, сходу писать оптимальный код, параллельно поясняя решение. Именно к этому готовят наши курсы. Как раз на семинарах и мок собесах мы учимся рассказывать решения вслух, получаем развернутый фидбэк и учимся действовать в сложных ситуация: что делать если не понимаешь условие, не можешь придумать решение или получил неожиданный вопрос. На наших курсах индивидуальный и структурированный подход, а не тупая алго дрочка. Записывайся и поступай с гарантией!
Подписаться: @algoses
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥4
Задача с собеседования в 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
Обмен определяется как выбор двух различных позиций в массиве и перестановка их значений местами.
Круговой массив определяется как массив, в котором первый и последний элементы считаются соседними.
Дан бинарный круговой массив 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 - размер окна (определяем методом count())
window_ones - счётчик единиц в текущем окне
max_window_ones - лучший результат по кол-ву единиц в окне
l - левая граница окна
r - правая граница окна
Если общее кол-во единиц в массиве равно 1 или 0:
- возвращаем 0, так как группировать нечего.
Для корректной обработки окон в циклическом массиве - проходим 2n итераций, беря индексы по модулю (% n), что позволит вернуться в начало при выходе за правую границу.
Проходим по массиву правым указателем:
- Добавляем правый эл-т в окно.
- Если длина окна превысила total_ones:
- убираем один эл-т слева;
- сдвигаем l вправо.
- Обновляем max_window_ones.
Возвращаем ответ как разность между общим кол-вом единиц и кол-вом единиц в наиболее «единичном» окне.
Сложность
O(1) - по памяти (храним некоторое кол-во переменных)
Код
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
🔥3❤1
ШАД 2026 Собеседование.pdf
123.6 KB
Собеседование ШАД 2026 года
В прикрепленном файле задачи, которые спрашивали в этом году. Если хотите добавить задачу с вашего собеседования пишите @vice22821. Взамен могу провести консультацию по любым вопросам или поделиться своими материалами. Еще больше материалов на наших курсах.
Математика
Раньше было 10-15 простых задач на минуту, затем предлагали на 15 минут 3 задачи посложнее на матан, линал, теорве вер. Сейчас же предлагали только 4 задачи посложнее на 25 минут: матан, линал, теор вер, дискретная математика, анализ данных. Нужно выбрать 2 задачи и рассказать их решение, ответить на доп вопросы.
Алгоритмы
Секция алгоритмов осталась той же: одна задача аля leetcode на 30 минут. Нужно рассказать решение, сделать оценку сложности и написать код. А также ответить на доп вопросы интервьюера.
Собеседование — это главная отсечка тех, кто реально готовился. Потому что формат очень необычный и к нему лучше готовиться заранее. На этом этапе валятся даже сильные ребята из топовых ВУЗов. Потому что все таки в классический академических курсах не учат решать задачи на идею: обычно это просто изучение абстрактной теории и нарешка стандартных задач на алгоритм. Да и собесы там проходить тоже не учат.
На наших же курсах основной упор делается именно на решение идейных задач, вся теория в лекциях разбирается на задачах. Мы тренируемся решать задачу вслух как на реальном собеседовании, учимся отвечать на злые вопросы интервьюера без паники за счет живых семинаров, консультаций и мок собесов. Мы настолько уверены в своем подходе, что даем гарантию поступления.
➡ Записаться
Подписаться: @matesha_shad
В прикрепленном файле задачи, которые спрашивали в этом году. Если хотите добавить задачу с вашего собеседования пишите @vice22821. Взамен могу провести консультацию по любым вопросам или поделиться своими материалами. Еще больше материалов на наших курсах.
Математика
Раньше было 10-15 простых задач на минуту, затем предлагали на 15 минут 3 задачи посложнее на матан, линал, теорве вер. Сейчас же предлагали только 4 задачи посложнее на 25 минут: матан, линал, теор вер, дискретная математика, анализ данных. Нужно выбрать 2 задачи и рассказать их решение, ответить на доп вопросы.
Алгоритмы
Секция алгоритмов осталась той же: одна задача аля leetcode на 30 минут. Нужно рассказать решение, сделать оценку сложности и написать код. А также ответить на доп вопросы интервьюера.
Собеседование — это главная отсечка тех, кто реально готовился. Потому что формат очень необычный и к нему лучше готовиться заранее. На этом этапе валятся даже сильные ребята из топовых ВУЗов. Потому что все таки в классический академических курсах не учат решать задачи на идею: обычно это просто изучение абстрактной теории и нарешка стандартных задач на алгоритм. Да и собесы там проходить тоже не учат.
На наших же курсах основной упор делается именно на решение идейных задач, вся теория в лекциях разбирается на задачах. Мы тренируемся решать задачу вслух как на реальном собеседовании, учимся отвечать на злые вопросы интервьюера без паники за счет живых семинаров, консультаций и мок собесов. Мы настолько уверены в своем подходе, что даем гарантию поступления.
Подписаться: @matesha_shad
Please open Telegram to view this post
VIEW IN TELEGRAM
❤5
Задача с собеседования в 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
Дано целое положительное число 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 не меняется. Соответственно, когда встречаем следующую единицу, она является ближайшей (т.е. соседней) к последней встреченной.
Заводим переменные:
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(1) - по памяти (храним некоторое кол-во переменных)
Код
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
❤4🔥1
Самая большая и последняя распродажа карьерных курсов СТАРТ И ПРО в этом году, где тебя 100% доведут до оффера по 5 направлениям:
⏩ Аналитика
⏩ Machine Learning
⏩ Backend
⏩ Алгоритмы
⏩ AI-агенты
Как выбрать уровень?
➡️ СТАРТ — если только начинаешь карьеру, меняешь направление или нужно укрепить базу. Собираем системный фундамент и готовим к стажировкам и первой работе
➡️ ПРО — если база уже есть и хочется быть сильнее других кандидатов: углубляем знания, разбираем сложные задачи и помогаем двигаться от junior к senior
Подробная программа
Всем участникам доступны:
А еще мы гарантируем результат
Проходишь курсы, выполняешь рекомендации, но не получаешь оффер — вернём деньги
Отзывы
🔊 Распродажа закончится 18 октября в 23:59.
И это последний набор в этом году, когда можно попасть на эти карьерные курсы с проверкой ДЗ, мок-собесами и и карьерной поддержкой. Дальше такой возможности в этом году уже не будет.
⭐ ЗАПИСАТЬСЯ НА КУРС⭐️
Как выбрать уровень?
Подробная программа
Всем участникам доступны:
🔵 разборы контестов в Яндекс (стажировка, IWO), Т-Банк (донабор), Kaspersky (GO, Python) и другие программы🔵 закрытая база собесов и тестовых заданий Бигтехов: Яндекс, Т-банк, Ozon, Cбер и так далее🔵 ДЗ и пет-проекты проверкой, помощь с резюме, рефералками в бигтех🔵 mock-собеседования HR/технических собесов с обратной связью🔵 курс по выходу на доход в валюте: LinkedIn, валютные вакансии, позиционирование и прохождение интервью.
А еще мы гарантируем результат
Проходишь курсы, выполняешь рекомендации, но не получаешь оффер — вернём деньги
Отзывы
И это последний набор в этом году, когда можно попасть на эти карьерные курсы с проверкой ДЗ, мок-собесами и и карьерной поддержкой. Дальше такой возможности в этом году уже не будет.
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
Стажировки отменили? Диплом теперь будут проверять?
С 1 марта 2027 года в России меняются правила стажировок.
Теперь «стажировка в сфере труда» будет официально привязана к вашему образованию или полученной квалификации.
То есть стажироваться можно будет по профессии, специальности или направлению, которое вы осваиваете или уже освоили, либо по новой квалификации, которую получили через профессиональное обучение / переподготовку.
И ещё два новых ограничения:
➡️ договор о стажировке можно заключить не позднее года после соответствующего обучения
➡️ сама стажировка может длиться максимум 6 месяцев
Ничего непонятно? Сейчас объясним
Допустим, вы учитесь на лингвиста, экономиста или химика, но в последнее время думаете:
«Когда-нибудь попробую себя аналитиком».
Или сначала хотите сходить на стажировку в аналитику, потом попробовать ML, а потом решить, что вам вообще ближе.
Так вот, товарищи, с 2027 года рассчитывать на стажировку как на универсальный способ «просто попробовать любую профессию» станет сложнее. Для стажировки направление должно быть связано с вашим образованием или новой квалификацией.
Поэтому если вы давно хотели попробовать себя в аналитике, ML, backend или другом IT-направлении, рекомендуем использовать ближайшие отборы и стажировки, ибо в следующем году это будет сделать сложнее.
В этом вам помогут наши карьерные курсы СТАРТ и ПРО мы как раз готовим к стажировкам, упаковываем ваш опыт и даем конкретный план, как действовать с учетом новых правил.
До 18 октября 23:59 все курсы доступны с большой скидкой, идут последние часы, торопитесь присоединиться!
➡️ Записаться
С 1 марта 2027 года в России меняются правила стажировок.
Теперь «стажировка в сфере труда» будет официально привязана к вашему образованию или полученной квалификации.
То есть стажироваться можно будет по профессии, специальности или направлению, которое вы осваиваете или уже освоили, либо по новой квалификации, которую получили через профессиональное обучение / переподготовку.
И ещё два новых ограничения:
Ничего непонятно? Сейчас объясним
Допустим, вы учитесь на лингвиста, экономиста или химика, но в последнее время думаете:
«Когда-нибудь попробую себя аналитиком».
Или сначала хотите сходить на стажировку в аналитику, потом попробовать ML, а потом решить, что вам вообще ближе.
Так вот, товарищи, с 2027 года рассчитывать на стажировку как на универсальный способ «просто попробовать любую профессию» станет сложнее. Для стажировки направление должно быть связано с вашим образованием или новой квалификацией.
Поэтому если вы давно хотели попробовать себя в аналитике, ML, backend или другом IT-направлении, рекомендуем использовать ближайшие отборы и стажировки, ибо в следующем году это будет сделать сложнее.
В этом вам помогут наши карьерные курсы СТАРТ и ПРО мы как раз готовим к стажировкам, упаковываем ваш опыт и даем конкретный план, как действовать с учетом новых правил.
До 18 октября 23:59 все курсы доступны с большой скидкой, идут последние часы, торопитесь присоединиться!
Please open Telegram to view this post
VIEW IN TELEGRAM
👀17🗿3🔥2👏2😁1
Рынок пока жив, и мы это видим
Последнее время вокруг IT много разговоров, что рынок сдулся, вакансий нет, компании фризят найм.
Несмотря на всю ситуации, наших студентов приглашают на интервью, и они собирают офферы💰
Кто-то пришёл на СТАРТ летом, кто-то подключился к ПРО в сентябре. И сейчас мы уже видим результаты!
Почему у них получается? Потому что после курсов ребята выходят на рынок осознанно и готовыми ко всему пути до оффера. Этим и выигрывают на фоне тех, кто бездумно откликается, валит собесы и винит во всем рынок.
Как вас ведем до оффера:
➡️ Сначала закрываем техническую часть: теория, много практики, ДЗ и пет-проекты с проверкой, реальные задачи и вопросы с собеседований, подготовка к техническим секциям
➡️ Далее преподаватели помогают собрать карьерную стратегию: понять, куда подаваться, как упаковать опыт, оформить резюме и LinkedIn, писать сопроводительные и выстроить стратегию откликов так, чтобы повышать шанс попасть на собеседование
➡️ Отрабатываем на практике: mock-собеседования, где в условиях, приближенным к реальному собеседованию, вы проходите техническую секцию и мотивационную
К моменту выхода на рынок у вас уже собрана вся подготовка:
харды + проекты + резюме + упакованный опыт + стратегия откликов + навык проходить собеседования
Лучшим студентам мы помогаем с рефералками и рекомендуем их в компании.
А если вы прошли курсы, выполнили рекомендации, но оффер не получили — вернём деньги.
Через 4 часа распродажа закрывается.
➡️ Любой курс СТАРТ или ПРО — 8 350 ₽
➡️ Комбо: СТАРТ + ПРО — 14 950 ₽
➡️ Ультра-комбо: СТАРТ+ПРО+Алгоритмы СТАРТ — 20 950 ₽, а Алгоритмы ПРО получаешь в подарок
И это последнее понижение цен на курсы СТАРТ и ПРО в этом году.
⭐ ЗАПИСАТЬСЯ НА КУРС⭐️
Последнее время вокруг IT много разговоров, что рынок сдулся, вакансий нет, компании фризят найм.
Несмотря на всю ситуации, наших студентов приглашают на интервью, и они собирают офферы
Кто-то пришёл на СТАРТ летом, кто-то подключился к ПРО в сентябре. И сейчас мы уже видим результаты!
Почему у них получается? Потому что после курсов ребята выходят на рынок осознанно и готовыми ко всему пути до оффера. Этим и выигрывают на фоне тех, кто бездумно откликается, валит собесы и винит во всем рынок.
Как вас ведем до оффера:
К моменту выхода на рынок у вас уже собрана вся подготовка:
харды + проекты + резюме + упакованный опыт + стратегия откликов + навык проходить собеседования
Лучшим студентам мы помогаем с рефералками и рекомендуем их в компании.
А если вы прошли курсы, выполнили рекомендации, но оффер не получили — вернём деньги.
Через 4 часа распродажа закрывается.
И это последнее понижение цен на курсы СТАРТ и ПРО в этом году.
Please open Telegram to view this post
VIEW IN TELEGRAM