Как залететь в хфт и стать миллионером, залутать сочную зумершку? Обсудим в новом ролике. Смотрим! Смотрим!
https://www.youtube.com/watch?v=zXQSoJjgQG8
https://www.youtube.com/watch?v=zXQSoJjgQG8
YouTube
Как стать quant resercher и попасть в HFT
Как реально попасть в HFT-фонд и стать квантом? В этом ролике — пошаговый разбор: какие роли есть в фондах, что нужно знать, какие достижения ценятся, как готовиться к собеседованиям и куда подаваться.
Внутри:
— кто такой «квант» в HFT и почему это не одна…
Внутри:
— кто такой «квант» в HFT и почему это не одна…
🔥3
Задача с собеседования в 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