Задача с собеседования в 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
👍3❤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
🔥6
Все алгозадачи с Яндекс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
🔥26👍2💅2❤1
Как и зачем тащить 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
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
Please open Telegram to view this post
VIEW IN TELEGRAM
❤8🔥2🗿2👍1
Как стать квантом
Сегодня многие талантливые амбициозные ребята хотят попасть в хфт и стать квантом. И это неудивительно, ведь хфт может предложить интересные задачи и вызовы, хороший доход, а также крутую команду и хорошие условия труда: в частности нередко удаленку.
Кто работает в хфт
На самом деле в фонде ровно такие же роли как и в других компаниях: аналитик, мл разработчик, дата инженер и так далее. Нередко роли размыты, а специалисты гибридны, потому что немало фондов - все таки стартапы со штатом в 50 сотрудников, где каждый должен уметь выполнять широкий пул задач. В силу специфики задач фондам нужны только умные ребята и в силу статуса стартапа они могут позволить себе проводить относительно жесткие собесы с алгоритмами, математикой и эскортницами.
Так как же стать квантом
Для начала нужно освоить какую-то специальность: аналитика, мл, разработчик, дата инженер. А также выучить математику и алгоритмы, чтобы проходить собесы и знать свою специальность на хорошем уровне. Еще нужно что-то иметь из следующего:
— относительно успешный олимпиадный опыт на международном уровне или уровне страны: хакатоны, соревнования, олимпиады по математике, программированию, ds/мл и так далее
— диплом ШАДа или учеба там (ОЧЕНЬ МНОГО РЕБЯТ ОТСЮДА)
— phd или быть в процессе его получения
— работа в лаборатории и статьи
— опыт работы по специальности
или другие сопоставимые достижения
Как готовиться к собесам
Для Quant-собеседований критически важна математика: теорвер, статистика, линейная алгебра, матан и логика - базовый минимум. В HFT-компаниях дополнительно могут спросить стохастические дифференциальные уравнения, диффуры и вариационное исчисление. Готовиться лучше через решение реальных задач с собесов: например, на Glassdoor или в подборках Quant Technical Interview Questions. Еще много прикольных книжек для америкосов по типу этих. Собесы часто идут на английском, поэтому нужно довести решение до автопилота.
Алгоритмы тоже обязательны, причём в HFT задачи сложнее: могут попасться динамическое программирование, деревья отрезков и т.п. Стоит купить подписку на LeetCode и посмотреть задачи от HFT-компаний, чтобы понять уровень.
Еще советую для подготовки наш курс алгоритмы про.
➡ Записаться.
Куда идти
Очень много компаний с русскими корнями, которые нанимают "понятных" для себя специалистов из СНГ. Можно пойти в FastFoward, где есть офис в Москве. Можно пойти в Teza, SWE, где много ШАДовцев и собесы вообще на русском. Офисы в Дубае, Армении и тд - наши слоны. Во все эти фонды собесы как в стартапы: Тестовое задание на денек➡️ Собесы ➡️ Разговор с руководителем.
Можно пойти пойти и во всякие Jane Street, Citadel, где уже меньше вайба стартапа и отборы более стандартизированы, и почилить в Азии, Эмиратах или вообще в Европе.
Путь кажется непростым и тернистым. Вам не кажется! Для этой специальности должен быть определенный характер: вы должны жаждать вызовов и непростых задач - быть психом короче, а не нормисом. Если характер у вас такой, то этот путь пройдется будто сам собой, с легкостью и удовольствием.
Подписаться: @chad_protocol
Сегодня многие талантливые амбициозные ребята хотят попасть в хфт и стать квантом. И это неудивительно, ведь хфт может предложить интересные задачи и вызовы, хороший доход, а также крутую команду и хорошие условия труда: в частности нередко удаленку.
Кто работает в хфт
На самом деле в фонде ровно такие же роли как и в других компаниях: аналитик, мл разработчик, дата инженер и так далее. Нередко роли размыты, а специалисты гибридны, потому что немало фондов - все таки стартапы со штатом в 50 сотрудников, где каждый должен уметь выполнять широкий пул задач. В силу специфики задач фондам нужны только умные ребята и в силу статуса стартапа они могут позволить себе проводить относительно жесткие собесы с алгоритмами, математикой и эскортницами.
Так как же стать квантом
Для начала нужно освоить какую-то специальность: аналитика, мл, разработчик, дата инженер. А также выучить математику и алгоритмы, чтобы проходить собесы и знать свою специальность на хорошем уровне. Еще нужно что-то иметь из следующего:
— относительно успешный олимпиадный опыт на международном уровне или уровне страны: хакатоны, соревнования, олимпиады по математике, программированию, ds/мл и так далее
— диплом ШАДа или учеба там (ОЧЕНЬ МНОГО РЕБЯТ ОТСЮДА)
— phd или быть в процессе его получения
— работа в лаборатории и статьи
— опыт работы по специальности
или другие сопоставимые достижения
Как готовиться к собесам
Для Quant-собеседований критически важна математика: теорвер, статистика, линейная алгебра, матан и логика - базовый минимум. В HFT-компаниях дополнительно могут спросить стохастические дифференциальные уравнения, диффуры и вариационное исчисление. Готовиться лучше через решение реальных задач с собесов: например, на Glassdoor или в подборках Quant Technical Interview Questions. Еще много прикольных книжек для америкосов по типу этих. Собесы часто идут на английском, поэтому нужно довести решение до автопилота.
Алгоритмы тоже обязательны, причём в HFT задачи сложнее: могут попасться динамическое программирование, деревья отрезков и т.п. Стоит купить подписку на LeetCode и посмотреть задачи от HFT-компаний, чтобы понять уровень.
Еще советую для подготовки наш курс алгоритмы про.
Куда идти
Очень много компаний с русскими корнями, которые нанимают "понятных" для себя специалистов из СНГ. Можно пойти в FastFoward, где есть офис в Москве. Можно пойти в Teza, SWE, где много ШАДовцев и собесы вообще на русском. Офисы в Дубае, Армении и тд - наши слоны. Во все эти фонды собесы как в стартапы: Тестовое задание на денек
Можно пойти пойти и во всякие Jane Street, Citadel, где уже меньше вайба стартапа и отборы более стандартизированы, и почилить в Азии, Эмиратах или вообще в Европе.
Путь кажется непростым и тернистым. Вам не кажется! Для этой специальности должен быть определенный характер: вы должны жаждать вызовов и непростых задач - быть психом короче, а не нормисом. Если характер у вас такой, то этот путь пройдется будто сам собой, с легкостью и удовольствием.
Подписаться: @chad_protocol
Please open Telegram to view this post
VIEW IN TELEGRAM
❤5🗿2
Задача с собеседования в 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
Зима близко! Во время соревнования ваша первая задача - спроектировать стандартный обогреватель с фиксированным радиусом обогрева, чтобы обогреть все дома.
Каждый дом может быть обогрет, если он находится в пределах радиуса действия обогревателя.
Даны позиции домов и обогревателей на горизонтальной прямой. Верните минимальный стандартный радиус обогревателей, чтобы они могли покрыть все дома.
Обратите внимание, что все обогреватели соответствуют вашему стандарту радиуса, и радиус зоны нагрева будет одинаковым.
Пример 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(1) - по памяти (без учёта сортировки; храним некоторое кол-во переменных)
Код
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
🔥3🤯1
This media is not supported in your browser
VIEW IN TELEGRAM
Залетаем с ноги в Яндекс: регистрация проходит до октября, а задания уже лежат тут.
А чтобы ты точно получил оффер, мы уже сделали разбор контеста и технических этапов, они доступны нашим студентам на наших курсах:
Помимо разборов, которые проходят все скрытые тесты на наличие ИИ в решениях, на наших курсах вы получаете:
🔽 Доступ к закрытой базе собесов и тестовых заданий🔽 Разбор стажировки ДС Авито (на МЛ ПРО и ИИ агенты ПРО)🔽 Курс по выходу на доход в валюте🔽 Гарантия оффера🔽 Рефералка в бигтех после защиты пет-проекта🔽 mock-собеседования с обратной связью
Успей написать администратору и не откладывай: задания могут скоро поменять!
Please open Telegram to view this post
VIEW IN TELEGRAM
Полный цикл отбора в 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
Недавно рассказывали про отбор в 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
Please open Telegram to view this post
VIEW IN TELEGRAM
👍3