Алгоритмы - Собеседования, Олимпиады, ШАД

Полный цикл отбора в Spectral на SWE (HFT)

Недавно рассказывали про отбор в Fast Forward на кванта, теперь расскажем как проходит отбор на SWE. Здесь уже намного меньше математики и ML, зато гораздо больше плюсов, алгоритмов, многопоточности, сетей и понимания того, как код работает непосредственно на железе. Полтора года назад наш выпускник проходил туда отбор, делимся как прошли этапы.

Условия (hr созвон)
Первый созвон был с hr, поспрашивали про опыт, проекты и достижения. Здесь, как и на кванта, стоит заранее подготовить нормальный рассказ про себя и мотивацию идти именно в HFT. Желательно уметь объяснить, почему вам интересна низкоуровневая разработка, оптимизация и работа с производительностью. Касательно зп назвали только диапазон (это было полтора года назад и вижу что вилки сильно уже изменились, тогда мне назвали 50-60к долларов)

Тестовое
На тестовое также лучше заранее выделить почти целый день. Здесь уже задача была ближе к разработке инфраструктуры для обработки биржевых данных. Нужно было реализовать обработку большого потока событий и поддерживать некоторое состояние системы. Сам алгоритм был достаточно простой, основной упор скорее был на качество реализации и производительность. Смотрели на количество аллокаций, копирований, выбор структур данных и в целом насколько человек понимает, где код может начать тормозить. То есть здесь опять же главное не намудрить с архитектурой, а написать достаточно простое и быстрое решение.

Первый тех собес
Первый тех собес был в основном посвящен C++ и низкоуровневой части. По времени примерно полтора часа, при этом ощущение опять же что жесткого тайминга особо нет. Очень много спрашивали по самому языку: работа памяти, object lifetime, move semantics, виртуальные методы, smart pointers, RAII, undefined behavior. Отдельно достаточно подробно проходились по STL и внутреннему устройству основных структур данных. Например могли спросить как устроены vector, map, unordered_map, чем они отличаются не только по асимптотике, но и по тому как лежат в памяти и как это влияет на производительность. Дальше достаточно быстро перешли к компьютерной архитектуре. Спрашивали про кэши процессора, cache lines, locality, branch prediction, virtual memory, page faults и TLB. Были небольшие устные кейсы, где нужно было объяснить почему два одинаковых по асимптотике куска кода могут работать с очень разной скоростью. Отдельный большой блок был по многопоточности: mutex, spinlock, atomics, data race, false sharing, memory ordering. Здесь скорее проверяли понимание, а не знание стандарта C++ наизусть. Также немного поспрашивали Linux: процессы, потоки, context switch, syscalls, профилирование и какие инструменты можно использовать чтобы искать bottleneck'и.

Второй тех собес
Второй тех собес уже был намного больше похож на классическое алгоритмическое интервью. Было несколько задач уровня выше хард литкода по сути со школьных олимпиад 1го уровня или всоша. Задачи в основном были на структуры данных, одну даже дали на разделяйку на дереве (центроиды) . Отдельно была задача на объединение нескольких потоков отсортированных данных и задача на реализацию кольцевого буфера. После решения обычно начинали задавать дополнительные вопросы: можно ли сделать быстрее, уменьшить память, убрать лишние аллокации или как решение изменится если оно будет использоваться из нескольких потоков. То есть здесь важно не только написать правильный алгоритм, но и уметь рассуждать о том, насколько хорошо он будет работать в реальной системе. Также немного погоняли по сетям: TCP/UDP, multicast, сокеты, blocking/non-blocking IO, почему в HFT часто используют UDP для market data и где вообще может появляться лишняя задержка.
Для подготовки советую наш курс алгоритмы про.
➡ Записаться.

System design
Отдельный кусок собеса был посвящен небольшому систем дизайну, но это не классические задачи из бигтеха в духе "спроектируйте Twitter". Здесь дали кейс вокруг обработки market data и отправки ордеров. Нужно было примерно рассказать как разбить систему на компоненты, где будут отдельные потоки, как передавать данные между ними и что делать если один компонент начинает работать медленнее остальных. В процессе в основном спрашивали про latency: где появятся копирования, блокировки, аллокации, системные вызовы и как это можно оптимизировать.

Финал
На финале уже встречался с лидом в офисе. В начале была еще одна небольшая алгоритмическая задача (по ощущениям рейтинга 2к на кфе), ничего сильно сложного, скорее очередной брейнтизер чтобы посмотреть как человек рассуждает. После этого собеседование уже больше превратилось в разговор про опыт и интересы. Много спрашивали про проекты, где приходилось оптимизировать код, искать сложные баги, разбираться с многопоточностью или читать большой чужой код. Также, как и на квант позицию, достаточно сильно смотрят на достижения. Олимпиады, ICPC, Codeforces, сильные пет-проекты или open source будут большим плюсом, особенно если коммерческого опыта пока мало.

Отбор на SWE оказался не столько сложным по задачам, сколько очень широким по количеству тем. Алгоритмы там нужны все задачи были рейтинга от 1800 на кфе (запрашивали по сути достаточно высокий уровень алгоритмического аппарата) , а также очень важно хорошо понимать C++ и то, как программа работает непосредственно на компьютере: память, кэши, потоки, операционная система и сеть.

Подписаться: @postyapshki_old

❗️ Яндекс открыл Intern Week Offer на стажировку, где всего за неделю ты можешь получить оффер, а не растягивать процесс на месяца.

Залетаем с ноги в Яндекс: регистрация проходит до октября, а задания уже лежат тут.

А чтобы ты точно получил оффер, мы уже сделали разбор контеста и технических этапов, они доступны нашим студентам на наших курсах:

➡️ алгоритмы про ➡️ фронтенд и бэкенд
➡️ бэкенд разработка про➡️ бэкенд
➡️ машинное обучение про ➡️ МЛ
➡️ ИИ-агенты ПРО ➡️ МЛ

Помимо разборов, которые проходят все скрытые тесты на наличие ИИ в решениях, на наших курсах вы получаете:

🔽 Доступ к закрытой базе собесов и тестовых заданий
🔽 Разбор стажировки ДС Авито (на МЛ ПРО и ИИ агенты ПРО)
🔽 Курс по выходу на доход в валюте
🔽 Гарантия оффера
🔽 Рефералка в бигтех после защиты пет-проекта
🔽 mock-собеседования с обратной связью

Успей написать администратору и не откладывай: задания могут скоро поменять!

Задача с собеседования в Zeta

Зима близко! Во время соревнования ваша первая задача - спроектировать стандартный обогреватель с фиксированным радиусом обогрева, чтобы обогреть все дома.
Каждый дом может быть обогрет, если он находится в пределах радиуса действия обогревателя.
Даны позиции домов и обогревателей на горизонтальной прямой. Верните минимальный стандартный радиус обогревателей, чтобы они могли покрыть все дома.

Обратите внимание, что все обогреватели соответствуют вашему стандарту радиуса, и радиус зоны нагрева будет одинаковым.

Пример 1:
Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: Единственный обогреватель был установлен в позиции 2, и при использовании стандарта радиуса 1, все дома могут быть обогреты.

Пример 2:
Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: Два обогревателя были установлены в позициях 1 и 4. Нам нужно использовать стандарт радиуса 1, тогда все дома можно будет обогреть.

Пример 3:
Input: houses = [1,5], heaters = [2]
Output: 3

Ограничения:
1 <= houses.length, heaters.length <= 3 * 10⁴
1 <= houses[i], heaters[i] <= 10⁹

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Итак, каждый обогреватель греет на фиксированное расстояние слева и справа, нужно найти минимальный радиус, чтобы все дома могли быть согреты.

Сортируем массивы houses и heaters, чтобы использовать метод двух указателей. Так как дома отсортированы, индекс ближайшего обогревателя для следующего дома не будет меньше, чем индекс для предыдущего дома => указатель по обогревателям движется монотонно вправо.

Указатели:
pos - индекс текущего кандидата в ближайший обогреватель
house - неявный указатель по домам в цикле for

Проходим по массиву houses, ища ближайший обогреватель для каждого дома:
Пока следующий обогреватель находится ближе к дому, чем текущий, или на том же расстоянии:
- сдвигаем pos вправо, переходя к следующему обогревателю.
Используем abs(), так как heaters[pos] может быть как слева (в таком случае heaters[pos] - house будет иметь отрицательное значение, а нам нужна положительная величина для корректного вычисления расстояния), так и справа от дома.

После выхода из цикла while:
heaters[pos] - ближайший обогреватель к текущему дому.
Вычисляем расстояние до него и обновляем res, беря максимальное расстояние до ближайшего обогревателя по всем домам - это и будет минимальный радиус, покрывающий самый удалённый от своего ближайшего обогревателя дом.

Сложность
O(n log n + m log m) - по времени (сортируем массивы; проход двумя указателями - за O(n + m), где n - кол-во домов, а m - кол-во обогревателей)
O(1) - по памяти (без учёта сортировки; храним некоторое кол-во переменных)

Код
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()

m = len(heaters)
res = 0
pos = 0

for house in houses:
while pos < m - 1 and abs(heaters[pos + 1] - house) <= abs(heaters[pos] - house):
pos += 1

res = max(res, abs(heaters[pos] - house))

return res

@algoses

Как стать квантом

Сегодня многие талантливые амбициозные ребята хотят попасть в хфт и стать квантом. И это неудивительно, ведь хфт может предложить интересные задачи и вызовы, хороший доход, а также крутую команду и хорошие условия труда: в частности нередко удаленку.

Кто работает в хфт
На самом деле в фонде ровно такие же роли как и в других компаниях: аналитик, мл разработчик, дата инженер и так далее. Нередко роли размыты, а специалисты гибридны, потому что немало фондов - все таки стартапы со штатом в 50 сотрудников, где каждый должен уметь выполнять широкий пул задач. В силу специфики задач фондам нужны только умные ребята и в силу статуса стартапа они могут позволить себе проводить относительно жесткие собесы с алгоритмами, математикой и эскортницами.

Так как же стать квантом
Для начала нужно освоить какую-то специальность: аналитика, мл, разработчик, дата инженер. А также выучить математику и алгоритмы, чтобы проходить собесы и знать свою специальность на хорошем уровне. Еще нужно что-то иметь из следующего:
— относительно успешный олимпиадный опыт на международном уровне или уровне страны: хакатоны, соревнования, олимпиады по математике, программированию, ds/мл и так далее
— диплом ШАДа или учеба там (ОЧЕНЬ МНОГО РЕБЯТ ОТСЮДА)
— phd или быть в процессе его получения
— работа в лаборатории и статьи
— опыт работы по специальности
или другие сопоставимые достижения

Как готовиться к собесам
Для Quant-собеседований критически важна математика: теорвер, статистика, линейная алгебра, матан и логика - базовый минимум. В HFT-компаниях дополнительно могут спросить стохастические дифференциальные уравнения, диффуры и вариационное исчисление. Готовиться лучше через решение реальных задач с собесов: например, на Glassdoor или в подборках Quant Technical Interview Questions. Еще много прикольных книжек для америкосов по типу этих. Собесы часто идут на английском, поэтому нужно довести решение до автопилота.

Алгоритмы тоже обязательны, причём в HFT задачи сложнее: могут попасться динамическое программирование, деревья отрезков и т.п. Стоит купить подписку на LeetCode и посмотреть задачи от HFT-компаний, чтобы понять уровень.
Еще советую для подготовки наш курс алгоритмы про.
➡ Записаться.

Куда идти
Очень много компаний с русскими корнями, которые нанимают "понятных" для себя специалистов из СНГ. Можно пойти в FastFoward, где есть офис в Москве. Можно пойти в Teza, SWE, где много ШАДовцев и собесы вообще на русском. Офисы в Дубае, Армении и тд - наши слоны. Во все эти фонды собесы как в стартапы: Тестовое задание на денек ➡️ Собесы ➡️ Разговор с руководителем.

Можно пойти пойти и во всякие Jane Street, Citadel, где уже меньше вайба стартапа и отборы более стандартизированы, и почилить в Азии, Эмиратах или вообще в Европе.

Путь кажется непростым и тернистым. Вам не кажется! Для этой специальности должен быть определенный характер: вы должны жаждать вызовов и непростых задач - быть психом короче, а не нормисом. Если характер у вас такой, то этот путь пройдется будто сам собой, с легкостью и удовольствием.

Подписаться: @chad_protocol

Как и зачем тащить ICPC

ICPC в большинстве регионов проходит в 4 этапа. Даты зависят от региона, но квалификация (если есть) проходит в октябре, региональный этап — в ноябре, всероссийский+СНГ — в середине декабря, мировой финал — осенью. Поэтому подготовку лучше начинать уже сейчас.
Участвовать стоит как минимум потому что олимпиадникам намного легче найти работу. Например, успешные олимпиадники могут пройти на стажировку в Т-банк, Яндекс по фаст-треку или вообще устроиться в HFT на начальную зарплату $120k в год, рекрутеры сами стучаться в лс. Конечно, этот путь только для тех, кому нравиться решать задачи по алгоритмам, иначе быстро выгорите.

Поиск команды
Для команды вам нужно найти еще двух человек из вашего университета. С этими людьми вы будете регулярно тренироваться как в бойцовском клубе. Для начала поспрашивайте среди ваших знакомых, особенно среди тех, кто когда-то занимался олимпиадами. Затем поспрашивайте в чатах вуза и посмотрите топ рейтинга на codeforces для вашего универа (там кстати есть возможность писать людям). Если в вашем универе есть клуб по олимпиадам — сходите туда и познакомьтесь с другими его участниками. Так за 1-2 месяца вы скорее всего собререте команду. В потенциальных сокомандниках смотрите главным образом на мотивацию, а не на текущий уровень. При очень большом желание за 4 года можно с нуля получить хоть золото на мировом финале, а при его отсутствие не получится пройти пройти даже в полуфинал.

Индивидуальная подготовка
Главным образом решайте задачи с архива codeforces с рейтингом примерно на 200 выше вашего и участвуйте в контестах, стараясь их вообще не пропускать. После каждого контеста дорешивайте 1-2 задачи, которые не смогли решить во время него. Если нужно — читайте editorial. Именно в момент решения этих задач вы прокачиваетесь и узнаете новые идеи, поэтому эту часть пропускать нельзя.
Помимо кф, вам нужно будет знать большинство классических тем вроде динамики, DFS/BFS, теории игр и т.д. Для их изучения отлично подходят cses.fi и cp-algorithms.com (попродвинутнее). Если только начинаете, то можете полностью прочитать книгу с первого сайта (в интернете есть копия и на русском) и решать задачи с него же.
В подготовке ИИ лучше не использовать совсем. Иначе вы отдаете часть своего мыслительного процесса на аутсорс и рискуете недополучить необходимые навыки.

Командная подготовка
Кроме индивидуальной подготовки, вам будет необходима и командная. Раз в неделю вам нужно вместе прорешивать командный контест на 4-5 часов. В первую очередь прорешайте четверть и полуфиналы ICPC вашего региона. Их можно найти на том же codeforces во вкладке "Тренировки". После контеста так же дорешивайте нерешенные задания. Не нужно недооценивать важность работы в команде. Например, в прошлом году команда нашего выпусника со средним рейтингом на кф ~1600 заняла практически такое же место, что и другая команда из того же вуза, со средним рейтингом ~2000. Сделать это удалось исключительно благодаря отлаженной командной работе, по его словам.

Буткемпы
Участие в буткемпах — один из лучших способов быстро прокачаться в спортивном программирование. По своему опыту, после каждого такого кемпа я получал примерно +100-150 рейтинга на кф в течение месяца. На них вы каждый день будете решать командный контест, возможно, на определенную тему и слушать разборы задач от топовых тренеров (иногда буквально дважды золотых медалистов ICPC). Также очень часто ваш вуз будет готов полностью оплатить такие кемпы вместе с дорогой. Самые известные: Петрозаводский кемп, Саратовский кемп, кемп от Яндекса (только для прошедших в мировой финал), Osijek camp.

Что нужно для призера полуфинала и для выхода в финал
Можно сказать "крутой уровень", начинается с призерства в полуфинале. Если вам повезло и в вашем университете не слишком много сильных олимпиадников, то для получения диплома на полуфинале вам нужно будет уметь решить задачу уровня 2000+ рейтинга кф. Это вполне достижимая цель за 1-2 года при должных усилиях даже с нуля. Если же вы хотите выйти в мировой финал, то тут нужно будет решить задачу уровня 2400+ рейтинга кф. Это уже намного сложнее, но тоже выполнимо при должном желании.

Если хотите открыть для себя мир олимпиад и соревнований по алгоритмам, то отличным стартом будет наш курс Алгоритмы ПРО.
➡️ Записаться.

Подписаться: @algoses

Как попасть в HFT компанию

HFT компании зарабатывают на небольших изменениях цен, осуществляя тысячи или даже миллионы транзакций в день. В этих компаниях работают не только разработчики, но и много других специалистов с разной квалификацией. Один из выпускников наших курсов не первый год работает в этой сфере на позициях Quantitative Researcher и ML Researcher, специально для вас, товарищи, попросил его поделиться своим опытом. Далее идет оригинальный текст.

Существует два вида HFT компаний. Одни зарабатывают много, а другие по меркам HFT достаточно мало, например это может быть компании, которые зарабатывают на крипте. В основном HFT компаний, которые находятся на территории РФ считаются не такими сильными, и платят там мало в рамках HFT, но сильно больше чем остальным на рынке it. Большинство топовых компаний находятся в штатах и Европе. В топовые компании отобраться конечно же сложнее. Также вам нужно помнить, что в большинстве HFT компаниях сильные переработки, сотрудники там надолго не задерживаются, отбор кандидатов может быть как и очень жестким, так и на уровне остальных IT компаний.

Перечислим парочку HFT компаниям, в которые весьма реально попасть гражданину РФ.
1. Pinely: Активно спонсирует разные олимпиады в духе ICPC. Очень много русскоговорящих сотрудников, по моим наблюдениям их большинство. Там работают такие легенды как Михаил Тихомиров, Михаил Ипатов (чемпионы мира по ICPC и не только). Компания определенно считается хорошей и скажу так, что весьма реально туда устроиться, например через стажировки. Кстати там много выпускников ШАДа, потому можно и рефералку пробить через знакомых.
2. Teza: Вообще компания американская, но есть филиал в Ереване, компания в целом неплохая, платят достойные деньги, переработок сильных нет, собесы адекватные. Но скорее всего вы там реально большие деньги зарабатывать не будете.
3. Àlber Blanc: Пожалуй самая успешная русскоговорящая компания, платят кстати достаточно хорошо, но отбор непростой и скорее всего придется переехать в Европу, но однозначно советую эту компанию.

С остальными компаниями, где много русскоговорящих вы можете ознакомиться тут.
Также есть Fast Forward и SPECTRAL в эти компании относительно легче попасть (собесы на русском).
Конечно, есть и всякие акулы рынка, куда тоже можно попробовать податься.

Подготовка
Очень важно знать математику. Фундамент как всегда теор вер, статистика, линейная алгебра, матан, много задач на логику. Также к акулам понадобятся слупы, диффуры и вариационное исчисление. Поэтому для начала ботаем дисциплины в ВУЗе или на курсах. Потом, чтобы привыкнуть к формату, отдельно прорешиваем задачи с собесов, например, отсюда.

Простой поиск Quant Technical Interview Questions позволяет найти много задач по математике с разбором на форумах, которые попадались на собесах. Но лично мне не хватало структуры и терпения во всем этом капаться, поэтому я просто взял курсы Поступашек и на своем примере могу сказать, что мне более чем всего хватило)
Еще собесы могут быть на английском, нужно научиться решать на автопилоте.

Также необходимо знать алгоритмы. Обычно в HFT компаниях задачи по алгосам сложнее, чем в остальных компаниях. Здесь вам с легкостью может попасться задача на ДО, ДП и тд. В целом вы можете на литкоде купить подписку и посмотреть задачи от нескольких HFT компаний, чтобы сориентироваться в уровне. Немало таких задач с разбором выкладывается здесь. Еще советую для подготовки наш курс алгоритмы про.
➡ Записаться.

Дальше по классике, хорошо бы знать жесткие плюсы, разбираться в МЛ и распределенных системах. Ждем 500 огоньков и пишем разбор по подготовке математике, С++, МЛ в HFT.

Бонус для тех кто дочитал до конца.
Открываем гит и вводим в поиск Quantitative и сможете увидеть потенциально большой список HFT компаний, которые как и нанимают сотрудников, так и проводят стажировка на 2027 год!

Подписаться: @chad_protocol

Собрали все задачи с алгосекции в Яндексе в одном файле с разбором частых ошибок, все это закрывают наши курсы по алгоритмам. Сохраняй и делись с друзьями такой годнотой! 🔥

Кстати а контест со стажировки уже разобран на соответствующих наших курсах ПРО.
➡ Записаться.

Подписаться: @algoses

Треш на алгоритмических собеседованиях на топовые офферы и магистратуры в 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

Задача с собеседования в 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

Хочешь начать карьеру в ИТ или уже сделал первый шаг и планируешь расти дальше? МТС True Tech Champ 2026 — хорошая точка ускорения

Это один из крупнейших ИТ-чемпионатов России, где ежегодно собираются студенты и разработчики со всей страны. Здесь ты попадаешь в поле зрения ИТ-команд.

Алгоритмический трек — это прокачка структур данных и алгоритмов на задачах уровня технических собеседований. По сути, прямая подготовка к интервью в сильные компании.

Трек программирования роботов — командная работа над реальным проектом: писать код, тестировать, дорабатывать под новые условия. Такой опыт заметно усиливает резюме.

Что ты получаешь для старта:
✔️сертификат участника, который добавишь в портфолио;
✔️практику живых соревнований и знакомство с ИТ-сообществом из разных городов;
✔️шанс, что тебя заметят рекрутеры и крупные ИТ-компании.

Зарегистрируйся на алгоритмический трек до 27 сентября, а на программирование роботов — до 13 сентября, и сделай следующий шаг в ИТ вместе с True Tech Champ 2026.

Задача с собеседования в 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

Открылся отбор на стажировку в Т-Банк

Задачи уже выложены в нашем чате (тут).

Специально для участников курсов про уже мы уже выложили разбор соответствующих экзаменов. В разборе мы покажем подход к решению задач и как оформить ответ, чтобы получить высокий балл.

Также на курсах будет доступно:

🔽 Курс по выходу на доход в валюте
🔽 Разбор текущей стажировки Яндекса
🔽 Гарантия оффера
🔽 Огромный банк технических вопросов
🔽 Рефералка в бигтех после защиты пет-проекта
🔽 mock-собеседования с обратной связью

📌 Вопросы и запись — менеджеру

Задача с собеседования в 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

Алгоритмы - Собеседования, Олимпиады, ШАД pinned a photo

Яндекс приглашает школьников на бесплатные Кружки по математике, программированию и ИИ

Кружки открыты для школьников 5–11 классов, а занятия ведут преподаватели с опытом участия в олимпиадах, работы в жюри и подготовки сборных. Программа рассчитана на учебный год (с сентября по май) и построена на сочетании лекций, семинаров, тематических контестов, пробных олимпиад и зачётов и дистанционных туров.

Всего три направления:

🔸Олимпиадное программирование (6–11 классы). Углублённое изучение алгоритмов и структур данных. 5 параллелей с разными уровнями сложности — для начинающих и продвинутых олимпиадников. Регистрация уже заканчивается.
🔸Олимпиадная математика (5–11 классы). Программа включает алгебру, геометрию, комбинаторику, теорию чисел. Есть базовый трек для уверенного освоения и профильный для подготовки к заключительным этапам ВсОШ и перечневым олимпиадам.
🔸Искусственный интеллект (8–11 классы). В курсе: Python, анализ данных, нейросети, большие языковые модели и подготовка к профилю ВсОШ по искусственному интеллекту.

Обучение бесплатное. Успейте подать заявки: до 30 августа — на олимпиадное программирование, до 6 сентября — на Кружок по ИИ и олимпиадную математику.

Выходим на новый уровень с линейкой 1️⃣1️⃣1️⃣

Товарищи, если база уже есть, то следующий шаг — углубиться в специализацию, закрыть пробелы, освоить новые инструменты и стать сильнее как специалист.

Для этого мы запускаем ПРО — углублённые карьерные курсы для тех, кто хочет качать карьеру и заработок! Для записи и вопросов — пишите менеджеру

📎Курсы ПРО подойдут тем, кто:

— уже знает основы и хочет глубже разобраться в своей специализации
— хочет перейти с junior на middle и расти дальше
— готовится к собеседованиям на более сильные позиции
— хочет сменить роль и добрать недостающие навыки
— уже на старте имеет сильную базу и хочет целиться выше стажёрских и junior-позиций

➡️Действует гарантия: прошел курс, выполнил все рекомендации, но не получил оффер — вернем деньги
➡️Курс длится 6 недель: теория, практика, домашние задания и пет-проект. Всё это время рядом преподаватель и куратор.

Открываем сразу 5 направлений:

➡️Аналитика ПРО

Продвинутый SQL, A/B-тесты, эконометрика, Causal Inference и ML.

➡️ML ПРО

Вывод модели в прод, MLOps, рекомендательные системы, ранжирование, uplift и динамическое преобразование.

➡️Backend ПРО

Многопоточка, System Desgin, Микросервисы, базы данных, кеширование, мониторинг и распределённые системы.

➡️Алгоритмы ПРО

Продвинутые алгоритмы и задачи для сложных технических интервью в hft фонды, faang+, для олимпиад и контестов.

➡️ИИ-агенты ПРО

Будем разбираться не просто в LLM. Вы научитесь проектировать полноценные агентные системы и за курс соберём 5 собственных AI-агентов и пройдём весь путь от архитектуры и инструментов до работы с RAG, multi-agent системами, MCP, evals и деплоем.

В программу всех курсов войдет:
🔵закрытый банк вопросов с интервью топовых бигтехов
🔵разбор ближайшей стажировки в Т-банк и Яндекс
🔵mock-собеседования с обратной связью
🔵рефералка в бигтех после защиты пет-проекта
🔵карьерная стратегия: резюме, поиск вакансий, подготовка к HR секциям

💰Бонус для всех записавшихся до 23.08 — курс про поиск валютной удалёнки и работы за рубежом в подарок

Зачем нужны продвинутые алгоритмы

Идет набор на наши курсы ПРО. Самое время обсудить, зачем нужен наш курс алгоритмы про.
➡️ Записаться

Олимпиады и магистратуры
Почти на любую школу/стажировку/магистратуру вы пишете контесты, уровень этих контестов меняется каждый год, уже в последнем контесте яндекса на стажировку вы можете увидеть продвинутые оптимизации ДП и 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

Задача с собеседования в 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

Успейте подать заявку на E-CUP 2026 Students от Ozon Tech до 30 августа 🎓

В этом сезоне — только для студентов. Будет интересно тем, кто изучает ML / DS / big data / аналитику данных.

Сможете ускорить модель по поиску дубликатов на 20%? Получится создать классификатор для модерации товаров? Сумеете предсказать поведение покупателя?

Как минимум — попробуете и получите фидбэк от тех, кто делает это в Ozon Tech каждый день. Как максимум — разделите призовой фонд в 7 200 000 ₽ в торжественной атмосфере конференции E-CODE.

Нетривиальные задачи, нетворк с ведущими специалистами индустрии, кастомный мерч и шанс масштабно усилить портфолио — это про E-CUP 2026 Students.
Больше подробностей и регистрация ↩️

Задача с собеседования в OYO

Напишите функцию для поиска наибольшего общего префикса среди массива строк. Если общего префикса нет, верните пустую строку "".

Пример 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"

Пример 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: У входных строк отсутствует общий префикс.

Ограничения:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] состоит только из строчных английских букв, если эта строка не пуста.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Основная идея: общий префикс не может быть длиннее самой короткой строки. Находим её через функцию min.
shortest - самая короткая строка.

Внешним циклом проходим по индексам и символам shortest, внутренним циклом - по строкам массива, проверяя, что у всех строк на этой же позиции стоит тот же символ:
Если встречаем несовпадение: выходим из цикла и возвращаем срез shortest[:i], состоящий из накопленного с прошлых итераций префикса;
Если все символы совпали: возвращаем shortest целиком, как общий префикс.

Сложность
O(n * m) - по времени (где n - кол-во строк в массиве, а m - длина самой короткой)
O(1) - по памяти (храним переменную shortest)

Код
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""

shortest = min(strs, key=len)

for i, char in enumerate(shortest):
for word in strs:
if word[i] != char:
return shortest[:i]

return shortest

@algoses