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❤2
Треш на алгоритмических собеседованиях на топовые офферы и магистратуры в 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
🔥5
Все алгозадачи с Яндексa.pdf
716.9 KB
Собрали все задачи с алгосекции в Яндексе в одном файле с разбором частых ошибок, все это закрывают наши курсы по алгоритмам. Сохраняй и делись с друзьями такой годнотой! 🔥
Кстати а контест со стажировки уже разобран на соответствующих наших курсах ПРО.
➡ Записаться.
Подписаться: @algoses
Кстати а контест со стажировки уже разобран на соответствующих наших курсах ПРО.
Подписаться: @algoses
Please open Telegram to view this post
VIEW IN TELEGRAM
❤4🔥1🤝1
Как попасть в 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
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
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥18👍2💅2❤1