Задача с собеседования в Persistent Systems
Инвертирование бита числа x - это выбор какого-либо бита в двоичном представлении числа x и изменение его значения с 0 на 1 или с 1 на 0.
Например, для x = 7 двоичное представление - 111, и мы можем выбрать любой бит (включая ведущие нули, которые не показаны) и инвертировать его. Мы можем инвертировать первый бит справа, чтобы получить 110, инвертировать второй бит справа, чтобы получить 101, инвертировать пятый бит справа (ведущий ноль), чтобы получить 10111, и так далее.
Даны два целых числа start и goal. Верните минимальное количество инвертирований битов, чтобы преобразовать start в goal.
Пример 1:
Input: start = 10, goal = 7
Output: 3
Explanation: Двоичное представление 10 и 7 - это 1010 и 0111, соответственно. Мы можем преобразовать 10 в 7 за 3 шага:
- Инвертировать первый бит справа: 1010 -> 1011.
- Инвертировать третий бит справа: 1011 -> 1111.
- Инвертировать четвёртый бит справа: 1111 -> 0111.
Можно показать, что преобразовать 10 в 7 менее чем за 3 шага невозможно. Следовательно, возвращаем 3.
Пример 2:
Input: start = 3, goal = 4
Output: 3
Explanation: Бинарное представление 3 и 4 - это 011 и 100, соответственно. Мы можем преобразовать 3 в 4 за 3 шага:
- Инвертировать первый бит справа: 011 -> 010.
- Инвертировать второй бит справа: 010 -> 000.
- Инвертировать третий бит справа: 000 -> 100.
Можно показать, что преобразовать 3 в 4 менее чем за 3 шага невозможно. Следовательно, возвращаем 3.
Ограничения:
0 <= start, goal <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
И вновь задачка на побитовые манипуляции.
Итак, каждый бит принимает одно значение: 1 или 0. Чтобы преобразовать число start в goal, необходимо инвертировать все различающиеся в одной и той же позиции биты, а совпадающие - оставить на месте. То есть минимальное кол-во инвертирований для преобразования исходного числа в целевое = кол-ву позиций (count), в которых биты двоичных представлений этих чисел различаются.
Чтобы определить различающиеся позиции, применяем оператор XOR (исключающее ИЛИ), сравнивающий два бита:
- если биты одинаковые -> 0
- если биты разные -> 1
start ^ goal даёт значение, в котором единицы стоят в тех позициях, где биты различаются.
Теперь посчитаем кол-во единиц в значении xor, используя побитовый И:
- только если оба бита равны 1 -> 1
- иначе -> 0
Пока xor больше 0 (есть хотя бы одна единица):
- xor & (xor - 1):
При (xor - 1) получаем новое число, в котором самая правая единица инвертируется в ноль, все нули справа от неё - в единицы, а биты слева - не изменяются.
Затем при операции побитового И(&) между этим новым значением и исходным числом:
Биты слева не меняются, так как одинаковы в обоих числах;
Самая правая единица обнуляется;
Все биты справа остаются нулями.
Таким образом, удаляется ровно одна правая единица.
- на каждой итерации увеличиваем count (кол-во единиц в xor) на 1.
Возвращаем count, хранящее кол-во единиц в xor, а значит, минимальное кол-во инвертирований битов.
Сложность
O(k) - по времени (где k - кол-во единиц в xor)
O(1) - по памяти (храним переменные count и xor)
Код
class Solution:
def minBitFlips(self, start: int, goal: int) -> int:
count = 0
xor = start ^ goal
while xor:
xor = xor & (xor - 1)
count += 1
return count
@algoses
Инвертирование бита числа x - это выбор какого-либо бита в двоичном представлении числа x и изменение его значения с 0 на 1 или с 1 на 0.
Например, для x = 7 двоичное представление - 111, и мы можем выбрать любой бит (включая ведущие нули, которые не показаны) и инвертировать его. Мы можем инвертировать первый бит справа, чтобы получить 110, инвертировать второй бит справа, чтобы получить 101, инвертировать пятый бит справа (ведущий ноль), чтобы получить 10111, и так далее.
Даны два целых числа start и goal. Верните минимальное количество инвертирований битов, чтобы преобразовать start в goal.
Пример 1:
Input: start = 10, goal = 7
Output: 3
Explanation: Двоичное представление 10 и 7 - это 1010 и 0111, соответственно. Мы можем преобразовать 10 в 7 за 3 шага:
- Инвертировать первый бит справа: 1010 -> 1011.
- Инвертировать третий бит справа: 1011 -> 1111.
- Инвертировать четвёртый бит справа: 1111 -> 0111.
Можно показать, что преобразовать 10 в 7 менее чем за 3 шага невозможно. Следовательно, возвращаем 3.
Пример 2:
Input: start = 3, goal = 4
Output: 3
Explanation: Бинарное представление 3 и 4 - это 011 и 100, соответственно. Мы можем преобразовать 3 в 4 за 3 шага:
- Инвертировать первый бит справа: 011 -> 010.
- Инвертировать второй бит справа: 010 -> 000.
- Инвертировать третий бит справа: 000 -> 100.
Можно показать, что преобразовать 3 в 4 менее чем за 3 шага невозможно. Следовательно, возвращаем 3.
Ограничения:
0 <= start, goal <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
И вновь задачка на побитовые манипуляции.
Итак, каждый бит принимает одно значение: 1 или 0. Чтобы преобразовать число start в goal, необходимо инвертировать все различающиеся в одной и той же позиции биты, а совпадающие - оставить на месте. То есть минимальное кол-во инвертирований для преобразования исходного числа в целевое = кол-ву позиций (count), в которых биты двоичных представлений этих чисел различаются.
Чтобы определить различающиеся позиции, применяем оператор XOR (исключающее ИЛИ), сравнивающий два бита:
- если биты одинаковые -> 0
- если биты разные -> 1
start ^ goal даёт значение, в котором единицы стоят в тех позициях, где биты различаются.
Теперь посчитаем кол-во единиц в значении xor, используя побитовый И:
- только если оба бита равны 1 -> 1
- иначе -> 0
Пока xor больше 0 (есть хотя бы одна единица):
- xor & (xor - 1):
При (xor - 1) получаем новое число, в котором самая правая единица инвертируется в ноль, все нули справа от неё - в единицы, а биты слева - не изменяются.
Затем при операции побитового И(&) между этим новым значением и исходным числом:
Биты слева не меняются, так как одинаковы в обоих числах;
Самая правая единица обнуляется;
Все биты справа остаются нулями.
Таким образом, удаляется ровно одна правая единица.
- на каждой итерации увеличиваем count (кол-во единиц в xor) на 1.
Возвращаем count, хранящее кол-во единиц в xor, а значит, минимальное кол-во инвертирований битов.
Сложность
O(k) - по времени (где k - кол-во единиц в xor)
O(1) - по памяти (храним переменные count и xor)
Код
class Solution:
def minBitFlips(self, start: int, goal: int) -> int:
count = 0
xor = start ^ goal
while xor:
xor = xor & (xor - 1)
count += 1
return count
@algoses
🔥3
Зачем нужны продвинутые алгоритмы
Идет набор на наши курсы ПРО. Самое время обсудить, зачем нужен наш курс алгоритмы про.
➡️ Записаться
Олимпиады и магистратуры
Почти на любую школу/стажировку/магистратуру вы пишете контесты, уровень этих контестов меняется каждый год, уже в последнем контесте яндекса на стажировку вы можете увидеть продвинутые оптимизации ДП и MITM. Во всякие ШАДы и так понятно, что контесты требуют высокой подготовки и большой насмотренности по алгоритмам. А также всё чаще встречаются ивенты/олимпиады для студентов (например yandex cup/турниры от fonbet/чемпионат от мтс) и старше по олимпиадному программированию, за которые можно получать денежные призы/бви в магистратуры/ фасттреки в сильнейшие бигтехи или хфт конторы.
FAANG+
В зарубежные компании куда сложнее отбор, зачастую там отбор состоит из 3-4 собеседований, а пару алгоритмических тем не хватит чтобы пройти эти собеседования. Там значительно объемнее алгоритмический багаж, который требуется для решения задач, и даже умения решать хард задачи на литкоде не хватит на проход. Например наш выпускник Максим (отзыв на сайте) прошел все этапы собеседования в гугл и уже окончил intern swe стажировку с зарплатой 8000$ в месяц. На самом собеседовании он как-раз решал задачу на битовый бор, который мы разбирали на первом уроке.
Computer Science
У многих компаний бигтеха есть свои лаборатории, в которые они направляют задачки, возникшие в процессе разработки в проде, которые не имеют решений в настоящее время. Например в т-банке есть лаборатория cs, где работает один из наших учеников Игорь. Что оптимизирует: курьеры получают на день некоторое количество заказов, а компания должна придумать сразу оптимальное разбиение всех заказов по курьерам и их маршруты так, чтобы минимальное количество топлива было затрачено на их сумму минимальных путей (почти что TSP задача). Лаборанты по большому счету работают там над теорией алгоритмов, придумывают эффективную идею и тестируют её на синтетических данных, а уже потом предложенную идею отправляют в прод. Здесь полноценный ресерч, вы должны не просто уметь хорошо решать задачи, но и должны знать большое количество алгоритмов и идей.
HFT
Даже в фонды среднячки нужна серьезная алгоритмическая подготовка, недавно мы узнали, что наш ученик Артем (смотрите на сайте), как раз устроился через пару месяцев после курса по алгосам в Fast Forward. А ранее ему дали задачу на собеседовании в Spectral рейтинга 2000 на кфе, и эту секцию он легко прошел. В хфт есть несколько направлений SWE, QR и Trader. На каждое из этих направлений нужны очень сильные алгоритмы. Отчасти стэк технологий трейдера и задачи его покрывают qr и swe, поэтому рассмотрим потребность в алгоритмах от его лица. Всё сказанное про ML и Бэк верно и для него, но только требуется еще более глубокое понимание всего. Например здесь же уже нужно понимать как реализованы внутри модели, какие структуры они используют, как их оптимизировать, а также и сами нюансы внутренние у реализаций библиотек. Здесь также и требуется иметь навыки бэкендера, но тут уже нужно глубокое понимание языка (чаще всего плюсов) на уровне количества инструкций в той или иной среде для какой-либо операции, а также нужно отлично знать алгоритмы и уметь их применять (последнее вдвойне ценится). Тут уже зачастую недостаточно придумать асимптотически наилучшее решение, нужно искать кучу неасимптотических оптимизаций для частных случаев данных.
Подписаться: @algoses
Идет набор на наши курсы ПРО. Самое время обсудить, зачем нужен наш курс алгоритмы про.
Олимпиады и магистратуры
Почти на любую школу/стажировку/магистратуру вы пишете контесты, уровень этих контестов меняется каждый год, уже в последнем контесте яндекса на стажировку вы можете увидеть продвинутые оптимизации ДП и MITM. Во всякие ШАДы и так понятно, что контесты требуют высокой подготовки и большой насмотренности по алгоритмам. А также всё чаще встречаются ивенты/олимпиады для студентов (например yandex cup/турниры от fonbet/чемпионат от мтс) и старше по олимпиадному программированию, за которые можно получать денежные призы/бви в магистратуры/ фасттреки в сильнейшие бигтехи или хфт конторы.
FAANG+
В зарубежные компании куда сложнее отбор, зачастую там отбор состоит из 3-4 собеседований, а пару алгоритмических тем не хватит чтобы пройти эти собеседования. Там значительно объемнее алгоритмический багаж, который требуется для решения задач, и даже умения решать хард задачи на литкоде не хватит на проход. Например наш выпускник Максим (отзыв на сайте) прошел все этапы собеседования в гугл и уже окончил intern swe стажировку с зарплатой 8000$ в месяц. На самом собеседовании он как-раз решал задачу на битовый бор, который мы разбирали на первом уроке.
Computer Science
У многих компаний бигтеха есть свои лаборатории, в которые они направляют задачки, возникшие в процессе разработки в проде, которые не имеют решений в настоящее время. Например в т-банке есть лаборатория cs, где работает один из наших учеников Игорь. Что оптимизирует: курьеры получают на день некоторое количество заказов, а компания должна придумать сразу оптимальное разбиение всех заказов по курьерам и их маршруты так, чтобы минимальное количество топлива было затрачено на их сумму минимальных путей (почти что TSP задача). Лаборанты по большому счету работают там над теорией алгоритмов, придумывают эффективную идею и тестируют её на синтетических данных, а уже потом предложенную идею отправляют в прод. Здесь полноценный ресерч, вы должны не просто уметь хорошо решать задачи, но и должны знать большое количество алгоритмов и идей.
HFT
Даже в фонды среднячки нужна серьезная алгоритмическая подготовка, недавно мы узнали, что наш ученик Артем (смотрите на сайте), как раз устроился через пару месяцев после курса по алгосам в Fast Forward. А ранее ему дали задачу на собеседовании в Spectral рейтинга 2000 на кфе, и эту секцию он легко прошел. В хфт есть несколько направлений SWE, QR и Trader. На каждое из этих направлений нужны очень сильные алгоритмы. Отчасти стэк технологий трейдера и задачи его покрывают qr и swe, поэтому рассмотрим потребность в алгоритмах от его лица. Всё сказанное про ML и Бэк верно и для него, но только требуется еще более глубокое понимание всего. Например здесь же уже нужно понимать как реализованы внутри модели, какие структуры они используют, как их оптимизировать, а также и сами нюансы внутренние у реализаций библиотек. Здесь также и требуется иметь навыки бэкендера, но тут уже нужно глубокое понимание языка (чаще всего плюсов) на уровне количества инструкций в той или иной среде для какой-либо операции, а также нужно отлично знать алгоритмы и уметь их применять (последнее вдвойне ценится). Тут уже зачастую недостаточно придумать асимптотически наилучшее решение, нужно искать кучу неасимптотических оптимизаций для частных случаев данных.
Подписаться: @algoses
Please open Telegram to view this post
VIEW IN TELEGRAM
❤6🔥2
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Выходим на новый уровень с линейкой 1️⃣ 1️⃣ 1️⃣
Товарищи, если база уже есть, то следующий шаг — углубиться в специализацию, закрыть пробелы, освоить новые инструменты и стать сильнее как специалист.
Для этого мы запускаем ПРО — углублённые карьерные курсы для тех, кто хочет качать карьеру и заработок! Для записи и вопросов — пишите менеджеру
📎 Курсы ПРО подойдут тем, кто:
— уже знает основы и хочет глубже разобраться в своей специализации
— хочет перейти с junior на middle и расти дальше
— готовится к собеседованиям на более сильные позиции
— хочет сменить роль и добрать недостающие навыки
— уже на старте имеет сильную базу и хочет целиться выше стажёрских и junior-позиций
➡️ Действует гарантия: прошел курс, выполнил все рекомендации, но не получил оффер — вернем деньги
➡️ Курс длится 6 недель: теория, практика, домашние задания и пет-проект. Всё это время рядом преподаватель и куратор.
Открываем сразу 5 направлений:
➡️ Аналитика ПРО
➡️ ML ПРО
➡️ Backend ПРО
➡️ Алгоритмы ПРО
➡️ ИИ-агенты ПРО
В программу всех курсов войдет:
🔵 закрытый банк вопросов с интервью топовых бигтехов
🔵 разбор ближайшей стажировки в Т-банк и Яндекс
🔵 mock-собеседования с обратной связью
🔵 рефералка в бигтех после защиты пет-проекта
🔵 карьерная стратегия: резюме, поиск вакансий, подготовка к HR секциям
💰 Бонус для всех записавшихся до 23.08 — курс про поиск валютной удалёнки и работы за рубежом в подарок
Товарищи, если база уже есть, то следующий шаг — углубиться в специализацию, закрыть пробелы, освоить новые инструменты и стать сильнее как специалист.
Для этого мы запускаем ПРО — углублённые карьерные курсы для тех, кто хочет качать карьеру и заработок! Для записи и вопросов — пишите менеджеру
— уже знает основы и хочет глубже разобраться в своей специализации
— хочет перейти с junior на middle и расти дальше
— готовится к собеседованиям на более сильные позиции
— хочет сменить роль и добрать недостающие навыки
— уже на старте имеет сильную базу и хочет целиться выше стажёрских и junior-позиций
Открываем сразу 5 направлений:
Продвинутый SQL, A/B-тесты, эконометрика, Causal Inference и ML.
Вывод модели в прод, MLOps, рекомендательные системы, ранжирование, uplift и динамическое преобразование.
Многопоточка, System Desgin, Микросервисы, базы данных, кеширование, мониторинг и распределённые системы.
Продвинутые алгоритмы и задачи для сложных технических интервью в hft фонды, faang+, для олимпиад и контестов.
Будем разбираться не просто в LLM. Вы научитесь проектировать полноценные агентные системы и за курс соберём 5 собственных AI-агентов и пройдём весь путь от архитектуры и инструментов до работы с RAG, multi-agent системами, MCP, evals и деплоем.
В программу всех курсов войдет:
Please open Telegram to view this post
VIEW IN TELEGRAM
❤2
Яндекс приглашает школьников на бесплатные Кружки по математике, программированию и ИИ
Кружки открыты для школьников 5–11 классов, а занятия ведут преподаватели с опытом участия в олимпиадах, работы в жюри и подготовки сборных. Программа рассчитана на учебный год (с сентября по май) и построена на сочетании лекций, семинаров, тематических контестов, пробных олимпиад и зачётов и дистанционных туров.
Всего три направления:
🔸Олимпиадное программирование (6–11 классы). Углублённое изучение алгоритмов и структур данных. 5 параллелей с разными уровнями сложности — для начинающих и продвинутых олимпиадников. Регистрация уже заканчивается.
🔸Олимпиадная математика (5–11 классы). Программа включает алгебру, геометрию, комбинаторику, теорию чисел. Есть базовый трек для уверенного освоения и профильный для подготовки к заключительным этапам ВсОШ и перечневым олимпиадам.
🔸Искусственный интеллект (8–11 классы). В курсе: Python, анализ данных, нейросети, большие языковые модели и подготовка к профилю ВсОШ по искусственному интеллекту.
Обучение бесплатное. Успейте подать заявки: до 30 августа — на олимпиадное программирование, до 6 сентября — на Кружок по ИИ и олимпиадную математику.
Кружки открыты для школьников 5–11 классов, а занятия ведут преподаватели с опытом участия в олимпиадах, работы в жюри и подготовки сборных. Программа рассчитана на учебный год (с сентября по май) и построена на сочетании лекций, семинаров, тематических контестов, пробных олимпиад и зачётов и дистанционных туров.
Всего три направления:
🔸Олимпиадное программирование (6–11 классы). Углублённое изучение алгоритмов и структур данных. 5 параллелей с разными уровнями сложности — для начинающих и продвинутых олимпиадников. Регистрация уже заканчивается.
🔸Олимпиадная математика (5–11 классы). Программа включает алгебру, геометрию, комбинаторику, теорию чисел. Есть базовый трек для уверенного освоения и профильный для подготовки к заключительным этапам ВсОШ и перечневым олимпиадам.
🔸Искусственный интеллект (8–11 классы). В курсе: Python, анализ данных, нейросети, большие языковые модели и подготовка к профилю ВсОШ по искусственному интеллекту.
Обучение бесплатное. Успейте подать заявки: до 30 августа — на олимпиадное программирование, до 6 сентября — на Кружок по ИИ и олимпиадную математику.
❤🔥3
Задача с собеседования в Josh Technology
Дан целочисленный массив nums. Ramp в массиве nums - это пара (i, j), для которой i < j и nums[i] <= nums[j]. Ширина такого ramp равна j - i.
Верните максимальную ширину ramp в nums. Если в nums нет ramp, верните 0.
Пример 1:
Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: Максимальная ширина ramp достигается при (i, j) = (1, 5): nums[1] = 0 и nums[5] = 5.
Пример 2:
Input: nums = [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: Максимальная ширина ramp достигается при (i, j) = (2, 9): nums[2] = 1 и nums[9] = 1.
Ограничения:
2 <= nums.length <= 5 * 10⁴
0 <= nums[i] <= 5 * 10⁴
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Необходимо найти такую пару индексов (i, j), где i < j и nums[i] <= nums[j], при этом индексы должны быть максимально удалены друг от друга.
Для решения используем монотонный стек (стек, элементы которого хранятся в строго возрастающем или строго убывающем порядке) и два прохода по массиву. В данном случае стек будет хранить индексы, упорядоченные по значениям nums[i]: значения по индексам в стеке будут образовывать строго убывающую последовательность. При добавлении нового эл-та алгоритм будет сравнивать его с вершиной стека.
В результате двух проходов:
- Первый проход (слева направо): находим кандидатов на левую границу (i).
- Второй проход (справа налево): для каждого кандидата ищем максимально удалённую правую границу (j).
Пройдем по алгоритму:
stack - стек для хранения индексов-кандидатов на левую границу (ищем максимально "низкие" значения).
Итерируемся по nums слева направо:
Если стек пуст или текущее значение меньше значения на вершине стека:
- добавляем индекс текущего эл-та в стек.
Ищем правую границу, идя от конца массива к началу, чтобы максимизировать расстояние между парами. Для каждого j проверяем, подходит ли он для левых кандидатов из стека:
Пока стек не пуст и левая граница <= правой границы (из условия: nums[i] <= nums[j]):
- вычисляем ширину пары и обновляем результат на максимально возможный.
Возвращаем res.
Сложность
O(n) - по времени (каждый индекс может быть добавлен в стек не более одного раза и удалён не более одного раза)
O(n) - по памяти (в худшем случае стек будет содержать все n индексов).
Код
class Solution:
def maxWidthRamp(self, nums: List[int]) -> int:
stack = []
res = 0
n = len(nums)
for i, num in enumerate(nums):
if not stack or nums[stack[-1]] > num:
stack.append(i)
for j in range(n)[::-1]:
while stack and nums[stack[-1]] <= nums[j]:
res = max(res, j - stack.pop())
return res
@algoses
Дан целочисленный массив nums. Ramp в массиве nums - это пара (i, j), для которой i < j и nums[i] <= nums[j]. Ширина такого ramp равна j - i.
Верните максимальную ширину ramp в nums. Если в nums нет ramp, верните 0.
Пример 1:
Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: Максимальная ширина ramp достигается при (i, j) = (1, 5): nums[1] = 0 и nums[5] = 5.
Пример 2:
Input: nums = [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: Максимальная ширина ramp достигается при (i, j) = (2, 9): nums[2] = 1 и nums[9] = 1.
Ограничения:
2 <= nums.length <= 5 * 10⁴
0 <= nums[i] <= 5 * 10⁴
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Для решения используем монотонный стек (стек, элементы которого хранятся в строго возрастающем или строго убывающем порядке) и два прохода по массиву. В данном случае стек будет хранить индексы, упорядоченные по значениям nums[i]: значения по индексам в стеке будут образовывать строго убывающую последовательность. При добавлении нового эл-та алгоритм будет сравнивать его с вершиной стека.
В результате двух проходов:
- Первый проход (слева направо): находим кандидатов на левую границу (i).
- Второй проход (справа налево): для каждого кандидата ищем максимально удалённую правую границу (j).
Пройдем по алгоритму:
stack - стек для хранения индексов-кандидатов на левую границу (ищем максимально "низкие" значения).
Итерируемся по nums слева направо:
Если стек пуст или текущее значение меньше значения на вершине стека:
- добавляем индекс текущего эл-та в стек.
Ищем правую границу, идя от конца массива к началу, чтобы максимизировать расстояние между парами. Для каждого j проверяем, подходит ли он для левых кандидатов из стека:
Пока стек не пуст и левая граница <= правой границы (из условия: nums[i] <= nums[j]):
- вычисляем ширину пары и обновляем результат на максимально возможный.
Возвращаем res.
Сложность
O(n) - по памяти (в худшем случае стек будет содержать все n индексов).
Код
def maxWidthRamp(self, nums: List[int]) -> int:
stack = []
res = 0
n = len(nums)
for i, num in enumerate(nums):
if not stack or nums[stack[-1]] > num:
stack.append(i)
for j in range(n)[::-1]:
while stack and nums[stack[-1]] <= nums[j]:
res = max(res, j - stack.pop())
return res
@algoses
❤2👍2💘1
This media is not supported in your browser
VIEW IN TELEGRAM
Открылся отбор на стажировку в Т-Банк
Задачи уже выложены в нашем чате (тут).
Специально для участников курсов про уже мы уже выложили разбор соответствующих экзаменов. В разборе мы покажем подход к решению задач и как оформить ответ, чтобы получить высокий балл.
Также на курсах будет доступно:
📌 Вопросы и запись — менеджеру
Задачи уже выложены в нашем чате (тут).
Специально для участников курсов про уже мы уже выложили разбор соответствующих экзаменов. В разборе мы покажем подход к решению задач и как оформить ответ, чтобы получить высокий балл.
Также на курсах будет доступно:
🔽 Курс по выходу на доход в валюте🔽 Разбор текущей стажировки Яндекса🔽 Гарантия оффера🔽 Огромный банк технических вопросов🔽 Рефералка в бигтех после защиты пет-проекта🔽 mock-собеседования с обратной связью
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥2
Задача с собеседования в OpenText
У тебя есть бомба, которую нужно обезвредить, и времени остаётся всё меньше! Твой информатор передаст тебе круговой массив code длиной n и ключ k.
Чтобы расшифровать код, необходимо заменить каждое число. Все числа заменяются одновременно.
- если k > 0, замени i-е число суммой следующих k чисел.
- если k < 0, замени i-е число суммой предыдущих -k чисел.
- если k == 0, замени i-е число на 0.
Так как массив круговой, следующий элемент после code[n-1] - это code[0], а предыдущий элемент после code[0] - это code[n-1].
Даны круговой массив и целое число k. Верни расшифрованный код, чтобы обезвредить бомбу!
Пример 1:
Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Каждое число заменяется суммой следующих трёх чисел. Расшифрованный код: [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Обрати внимание, что числа берутся по кругу.
Пример 2:
Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: Когда k равно нулю, все числа заменяются на 0.
Пример 3:
Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: Расшифрованный код: [3+9, 2+3, 4+2, 9+4]. Обрати внимание, что числа снова идут по кругу. Если k - отрицательное, сумма берётся от предыдущих чисел.
Ограничения:
n == code.length
1 <= n <= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
При наивном решении мы бы проходили циклом по массиву, суммируя k следующих или предыдущих соседей каждого эл-та.
Для оптимального решения за O(n) - используем алгоритм "скользящего окна" с двумя указателями. Размер окна (window_size) равен abs(k).
Окно двигается вправо: добавляем правый эл-т, и если размер окна превысил window_size - сдвигаем левую границу, удаляя левый эл-т.
Так как массив круговой, для нахождения корректного индекса используем операцию взятия по модулю (% n), что позволит вернуться в начало при выходе за правую границу или перейти в конец при выходе за левую границу.
Если k > 0: окно равно следующим k эл-м; эл-т, для которого считаем сумму, стоит слева от окна.
Если k < 0: окно равно предыдущим |k| эл-м; эл-т, для которого считаем сумму, стоит справа от окна.
Инициализируем массив res для хранения результата и заполняем нулями.
window_sum - сумма внутри окна
l - левая граница окна
r - правая граница окна
Если k равен нулю:
- возвращаем res (все эл-ты уже равны 0).
Двигаем окно правым указателем, проходя n + window_size - 1 итераций (где первые window_size итераций строим окно нужного размера, и на последней из них записываем первый ответ, а оставшиеся n - 1 итераций - сдвигаем окно, записывая ответы для остальных эл-в):
- Добавляем правый эл-т в окно.
- Если окно переполнилось (достигло window_size + 1):
- убираем один эл-т слева;
- сдвигаем l вправо.
- Если окно достигло размера window_size, записываем ответ:
- если k положительный: окно начинается с l => записываем ответ для индекса (l-1) % n
- если k отрицательный: окно заканчивается на r => ответ для индекса (r+1) % n
Возвращаем res.
Сложность
O(n) - по времени (проходим по массиву один раз)
O(n) - по памяти (храним некоторое кол-во переменных и массив res, равный длине входного массива)
Код
class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
n = len(code)
res = [0] * n
if k == 0:
return res
window_size = abs(k)
l = 0
window_sum = 0
for r in range(n + window_size - 1):
window_sum += code[r % n]
if r - l + 1 > window_size:
window_sum -= code[l % n]
l = (l + 1) % n
if r - l + 1 == window_size:
if k > 0:
res[(l - 1) % n] = window_sum
if k < 0:
res[(r + 1) % n] = window_sum
return res
@algoses
У тебя есть бомба, которую нужно обезвредить, и времени остаётся всё меньше! Твой информатор передаст тебе круговой массив code длиной n и ключ k.
Чтобы расшифровать код, необходимо заменить каждое число. Все числа заменяются одновременно.
- если k > 0, замени i-е число суммой следующих k чисел.
- если k < 0, замени i-е число суммой предыдущих -k чисел.
- если k == 0, замени i-е число на 0.
Так как массив круговой, следующий элемент после code[n-1] - это code[0], а предыдущий элемент после code[0] - это code[n-1].
Даны круговой массив и целое число k. Верни расшифрованный код, чтобы обезвредить бомбу!
Пример 1:
Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Каждое число заменяется суммой следующих трёх чисел. Расшифрованный код: [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Обрати внимание, что числа берутся по кругу.
Пример 2:
Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: Когда k равно нулю, все числа заменяются на 0.
Пример 3:
Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: Расшифрованный код: [3+9, 2+3, 4+2, 9+4]. Обрати внимание, что числа снова идут по кругу. Если k - отрицательное, сумма берётся от предыдущих чисел.
Ограничения:
n == code.length
1 <= n <= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Для оптимального решения за O(n) - используем алгоритм "скользящего окна" с двумя указателями. Размер окна (window_size) равен abs(k).
Окно двигается вправо: добавляем правый эл-т, и если размер окна превысил window_size - сдвигаем левую границу, удаляя левый эл-т.
Так как массив круговой, для нахождения корректного индекса используем операцию взятия по модулю (% n), что позволит вернуться в начало при выходе за правую границу или перейти в конец при выходе за левую границу.
Если k > 0: окно равно следующим k эл-м; эл-т, для которого считаем сумму, стоит слева от окна.
Если k < 0: окно равно предыдущим |k| эл-м; эл-т, для которого считаем сумму, стоит справа от окна.
Инициализируем массив res для хранения результата и заполняем нулями.
window_sum - сумма внутри окна
l - левая граница окна
r - правая граница окна
Если k равен нулю:
- возвращаем res (все эл-ты уже равны 0).
Двигаем окно правым указателем, проходя n + window_size - 1 итераций (где первые window_size итераций строим окно нужного размера, и на последней из них записываем первый ответ, а оставшиеся n - 1 итераций - сдвигаем окно, записывая ответы для остальных эл-в):
- Добавляем правый эл-т в окно.
- Если окно переполнилось (достигло window_size + 1):
- убираем один эл-т слева;
- сдвигаем l вправо.
- Если окно достигло размера window_size, записываем ответ:
- если k положительный: окно начинается с l => записываем ответ для индекса (l-1) % n
- если k отрицательный: окно заканчивается на r => ответ для индекса (r+1) % n
Возвращаем res.
Сложность
O(n) - по памяти (храним некоторое кол-во переменных и массив res, равный длине входного массива)
Код
def decrypt(self, code: List[int], k: int) -> List[int]:
n = len(code)
res = [0] * n
if k == 0:
return res
window_size = abs(k)
l = 0
window_sum = 0
for r in range(n + window_size - 1):
window_sum += code[r % n]
if r - l + 1 > window_size:
window_sum -= code[l % n]
l = (l + 1) % n
if r - l + 1 == window_size:
if k > 0:
res[(l - 1) % n] = window_sum
if k < 0:
res[(r + 1) % n] = window_sum
return res
@algoses
👍2❤1🔥1👏1
Хочешь начать карьеру в ИТ или уже сделал первый шаг и планируешь расти дальше? МТС True Tech Champ 2026 — хорошая точка ускорения
Это один из крупнейших ИТ-чемпионатов России, где ежегодно собираются студенты и разработчики со всей страны. Здесь ты попадаешь в поле зрения ИТ-команд.
Алгоритмический трек — это прокачка структур данных и алгоритмов на задачах уровня технических собеседований. По сути, прямая подготовка к интервью в сильные компании.
Трек программирования роботов — командная работа над реальным проектом: писать код, тестировать, дорабатывать под новые условия. Такой опыт заметно усиливает резюме.
Что ты получаешь для старта:
✔️сертификат участника, который добавишь в портфолио;
✔️практику живых соревнований и знакомство с ИТ-сообществом из разных городов;
✔️шанс, что тебя заметят рекрутеры и крупные ИТ-компании.
Зарегистрируйся на алгоритмический трек до 27 сентября, а на программирование роботов — до 13 сентября, и сделай следующий шаг в ИТ вместе с True Tech Champ 2026.
Это один из крупнейших ИТ-чемпионатов России, где ежегодно собираются студенты и разработчики со всей страны. Здесь ты попадаешь в поле зрения ИТ-команд.
Алгоритмический трек — это прокачка структур данных и алгоритмов на задачах уровня технических собеседований. По сути, прямая подготовка к интервью в сильные компании.
Трек программирования роботов — командная работа над реальным проектом: писать код, тестировать, дорабатывать под новые условия. Такой опыт заметно усиливает резюме.
Что ты получаешь для старта:
✔️сертификат участника, который добавишь в портфолио;
✔️практику живых соревнований и знакомство с ИТ-сообществом из разных городов;
✔️шанс, что тебя заметят рекрутеры и крупные ИТ-компании.
Зарегистрируйся на алгоритмический трек до 27 сентября, а на программирование роботов — до 13 сентября, и сделай следующий шаг в ИТ вместе с True Tech Champ 2026.
Задача с собеседования в Zepto
Есть автомобиль с определённым количеством посадочных мест (capacity). Автомобиль движется только на восток (т.е. он не может развернуться и поехать на запад).
Даны целое число capacity и массив trips, где trips[i] = [numPassengersᵢ, fromᵢ, toᵢ] означает, что для i-ой поездки нужно забрать numPassengersᵢ пассажиров в точке fromᵢ и высадить их в точке toᵢ, соответственно. Координаты указаны в километрах к востоку от начального положения автомобиля.
Верните true, если возможно забрать и высадить всех пассажиров для всех данных поездок, иначе верните false.
Пример 1:
Input: trips = [ [2,1,5], [3,3,7] ], capacity = 4
Output: false
Пример 2:
Input: trips = [ [2,1,5], [3,3,7] ], capacity = 5
Output: true
Ограничения:
1 <= trips.length <= 1000
trips[i].length == 3
1 <= numPassengersᵢ <= 100
0 <= fromᵢ < toᵢ <= 1000
1 <= capacity <= 10⁵
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
С учётом ограничений (0 <= fromᵢ < toᵢ <= 1000) можем использовать массив разностей и префиксную сумму для оптимального решения за O(n + k), где n - кол-во поездок, а k - максимальная координата.
Нам не нужно хранить загрузку автомобиля на каждом километре, а только её изменения в точках посадки и высадки (так как между этими точками кол-во пассажиров не меняется) в массиве разностей. Затем пройдём по массиву, накапливая сумму изменений, которая и показывает текущую загрузку. Останется проверить, не превысила ли она вместимость автомобиля.
Находим самую дальнюю точку маршрута (max_location) и создаём массив passenger_changes, размер которого равен max_location + 1, где passenger_changes[i] - значение, на сколько изменится загрузка автомобиля на i-м километре от начальной точки.
Проходим по массиву trips, записывая изменения загрузки:
- добавляем пассажиров при посадке в точке start;
- уменьшаем численность пассажиров при высадке в точке end.
Теперь проверим, не стало ли пассажиров в какой-то момент больше, чем посадочных мест.
Проходим по всем километрам, накапливая сумму:
- если на каком-то километре загрузка (current_load) превысила capacity: возвращаем False.
Если прошли все километры без превышения лимита: возвращаем True.
Сложность
O(n + k) - по времени (где n - кол-во поездок, а k - максимальная координата)
O(k) - по памяти (создаём массив passenger_changes размером k+1)
Код
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
max_location = 0
for _, _, end in trips:
max_location = max(max_location, end)
passenger_changes = [0] * (max_location + 1)
for passengers, start, end in trips:
passenger_changes[start] += passengers
passenger_changes[end] -= passengers
current_load = 0
for change in passenger_changes:
current_load += change
if current_load > capacity:
return False
return True
@algoses
Есть автомобиль с определённым количеством посадочных мест (capacity). Автомобиль движется только на восток (т.е. он не может развернуться и поехать на запад).
Даны целое число capacity и массив trips, где trips[i] = [numPassengersᵢ, fromᵢ, toᵢ] означает, что для i-ой поездки нужно забрать numPassengersᵢ пассажиров в точке fromᵢ и высадить их в точке toᵢ, соответственно. Координаты указаны в километрах к востоку от начального положения автомобиля.
Верните true, если возможно забрать и высадить всех пассажиров для всех данных поездок, иначе верните false.
Пример 1:
Input: trips = [ [2,1,5], [3,3,7] ], capacity = 4
Output: false
Пример 2:
Input: trips = [ [2,1,5], [3,3,7] ], capacity = 5
Output: true
Ограничения:
1 <= trips.length <= 1000
trips[i].length == 3
1 <= numPassengersᵢ <= 100
0 <= fromᵢ < toᵢ <= 1000
1 <= capacity <= 10⁵
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Нам не нужно хранить загрузку автомобиля на каждом километре, а только её изменения в точках посадки и высадки (так как между этими точками кол-во пассажиров не меняется) в массиве разностей. Затем пройдём по массиву, накапливая сумму изменений, которая и показывает текущую загрузку. Останется проверить, не превысила ли она вместимость автомобиля.
Находим самую дальнюю точку маршрута (max_location) и создаём массив passenger_changes, размер которого равен max_location + 1, где passenger_changes[i] - значение, на сколько изменится загрузка автомобиля на i-м километре от начальной точки.
Проходим по массиву trips, записывая изменения загрузки:
- добавляем пассажиров при посадке в точке start;
- уменьшаем численность пассажиров при высадке в точке end.
Теперь проверим, не стало ли пассажиров в какой-то момент больше, чем посадочных мест.
Проходим по всем километрам, накапливая сумму:
- если на каком-то километре загрузка (current_load) превысила capacity: возвращаем False.
Если прошли все километры без превышения лимита: возвращаем True.
Сложность
O(k) - по памяти (создаём массив passenger_changes размером k+1)
Код
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
max_location = 0
for _, _, end in trips:
max_location = max(max_location, end)
passenger_changes = [0] * (max_location + 1)
for passengers, start, end in trips:
passenger_changes[start] += passengers
passenger_changes[end] -= passengers
current_load = 0
for change in passenger_changes:
current_load += change
if current_load > capacity:
return False
return True
@algoses
👍3❤1
Треш на алгоритмических собеседованиях на топовые офферы и магистратуры в CS
Мы опросили наших выпускников программы алгоритмы про, что им встречалось по каждому направлению отсюда. И вот что из этого вышло.
Задача Андрея (4 курс БГУ ФПМИ) на собеседовании в магистратуру СКН.
Условие: Даны n исходных строк и m строк-запросов. Для каждой строки-запроса s нужно определить, существует ли среди исходных строк строка t, такая что: len(t) = len(s) и t отличается от s ровно в одной позиции. Строки состоят только из символов a, b, c. На каждый запрос выведите YES, если такая строка существует, иначе NO. Ограничения: n, m <= 3e5, суммарная длина всех строк не превышает 6e5
Идея решения:
Для каждого запроса идём по бору слева направо и храним два состояния: сколько несовпадений уже было - 0 или 1. На каждой позиции: можно пойти по ребру с тем же символом:
1) если ошибка ещё не использована, можно попробовать перейти по одному из двух других символов и отметить, что одно несовпадение уже есть.
2) если ошибка ещё не использована, можно попробовать перейти по одному из двух других символов и отметить, что одно несовпадение уже есть.
Код с решением задачи.
Задача на собеседование в GOOGLE на позицию SWE разработчика с зп 8000$
Условие: Дана перестановка чисел от 1 до n. Из неё удалили два элемента, после чего оставшиеся n - 2 чисел разделили на две непустые части.
Программа запускается два раза. При первом запуске дана левая часть последовательности. Нужно вывести строку-памятку длиной не более 1000 символов. При втором запуске дана эта памятка и правая часть последовательности. Нужно определить два числа от 1 до n, которых нет ни в левой, ни в правой части.
Ограничение: 4 <= n <= 3e5.
Идея решения:
Каждому числу i сопоставляем случайный 64- битный хеш (можно просто рандом число назначить mt19937 например) h(i).
На первом запуске считаем:
H_left = sum(h(x)) по всем x из левой части и сохраняем H_left в памятку.
На втором запуске считаем:
H_missing = sum(h(i)) для i от 1 до n - H_left - sum(h(x)) по правой части
Тогда:
H_missing = h(a) + h(b), где a и b - два пропавших числа.
Дальше перебираем a и проверяем, существует ли число b с хешем:
h(b) = H_missing - h(a).
Все хеши можно заранее хранить в unordered_map. Сложность - O(n)
Код с решением задачи.
Задача из собеседования в hft Sspectral technologies которую дали Артёму на SWE позицию с зп 70 000$ в год
Условие: Дано дерево из n вершин. В одной из вершин находится скрытая вершина x, которую нужно определить. Можно делать запросы вида:
? v
В ответ интерактор сообщает:
0, если v = x
номер соседа вершины v, который является первым на пути из v в x.
Когда скрытая вершина найдена, нужно вывести:
! x
Разрешается сделать не более log2(n) + 1 запросов.
Идея решения
Рассматриваем множество вершин, в котором сейчас может находиться x. Находим центроид этого поддерева и спрашиваем его. Если ответ 0, вершина найдена. Иначе интерактор возвращает соседа u. После удаления центроида дерево распадается на компоненты, и x гарантированно находится в компоненте, содержащей u. Оставляем только эту компоненту и повторяем процесс. Так как центроид делит дерево на компоненты размера не более половины текущего дерева, количество возможных вершин уменьшается каждый раз в два раза. Поэтому потребуется O(log n) запросов.
Это полный аналог бинарного поиска: в массиве выбираем середину и оставляем одну половину, а в дереве выбираем центроид и оставляем одну из компонент после его удаления.
Код с решением
Подписаться: @algoses
Мы опросили наших выпускников программы алгоритмы про, что им встречалось по каждому направлению отсюда. И вот что из этого вышло.
Задача Андрея (4 курс БГУ ФПМИ) на собеседовании в магистратуру СКН.
Условие: Даны n исходных строк и m строк-запросов. Для каждой строки-запроса s нужно определить, существует ли среди исходных строк строка t, такая что: len(t) = len(s) и t отличается от s ровно в одной позиции. Строки состоят только из символов a, b, c. На каждый запрос выведите YES, если такая строка существует, иначе NO. Ограничения: n, m <= 3e5, суммарная длина всех строк не превышает 6e5
Идея решения:
Для каждого запроса идём по бору слева направо и храним два состояния: сколько несовпадений уже было - 0 или 1. На каждой позиции: можно пойти по ребру с тем же символом:
1) если ошибка ещё не использована, можно попробовать перейти по одному из двух других символов и отметить, что одно несовпадение уже есть.
2) если ошибка ещё не использована, можно попробовать перейти по одному из двух других символов и отметить, что одно несовпадение уже есть.
Код с решением задачи.
Задача на собеседование в GOOGLE на позицию SWE разработчика с зп 8000$
Условие: Дана перестановка чисел от 1 до n. Из неё удалили два элемента, после чего оставшиеся n - 2 чисел разделили на две непустые части.
Программа запускается два раза. При первом запуске дана левая часть последовательности. Нужно вывести строку-памятку длиной не более 1000 символов. При втором запуске дана эта памятка и правая часть последовательности. Нужно определить два числа от 1 до n, которых нет ни в левой, ни в правой части.
Ограничение: 4 <= n <= 3e5.
Идея решения:
Каждому числу i сопоставляем случайный 64- битный хеш (можно просто рандом число назначить mt19937 например) h(i).
На первом запуске считаем:
H_left = sum(h(x)) по всем x из левой части и сохраняем H_left в памятку.
На втором запуске считаем:
H_missing = sum(h(i)) для i от 1 до n - H_left - sum(h(x)) по правой части
Тогда:
H_missing = h(a) + h(b), где a и b - два пропавших числа.
Дальше перебираем a и проверяем, существует ли число b с хешем:
h(b) = H_missing - h(a).
Все хеши можно заранее хранить в unordered_map. Сложность - O(n)
Код с решением задачи.
Задача из собеседования в hft Sspectral technologies которую дали Артёму на SWE позицию с зп 70 000$ в год
Условие: Дано дерево из n вершин. В одной из вершин находится скрытая вершина x, которую нужно определить. Можно делать запросы вида:
? v
В ответ интерактор сообщает:
0, если v = x
номер соседа вершины v, который является первым на пути из v в x.
Когда скрытая вершина найдена, нужно вывести:
! x
Разрешается сделать не более log2(n) + 1 запросов.
Идея решения
Это полный аналог бинарного поиска: в массиве выбираем середину и оставляем одну половину, а в дереве выбираем центроид и оставляем одну из компонент после его удаления.
Код с решением
Подписаться: @algoses
🔥4
Все алгозадачи с Яндексa.pdf
716.9 KB
Собрали все задачи с алгосекции в Яндексе в одном файле с разбором частых ошибок, все это закрывают наши курсы по алгоритмам. Сохраняй и делись с друзьями такой годнотой! 🔥
Кстати а контест со стажировки уже разобран на соответствующих наших курсах ПРО.
➡ Записаться.
Подписаться: @algoses
Кстати а контест со стажировки уже разобран на соответствующих наших курсах ПРО.
Подписаться: @algoses
Please open Telegram to view this post
VIEW IN TELEGRAM
❤3🔥1