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

Зачем нужны продвинутые алгоритмы Идет набор на наши курсы ПРО. Самое время обсудить, зачем нужен наш курс алгоритмы про. ➡️ Записаться Олимпиады и магистратуры Почти на любую школу/стажировку/магистратуру вы пишете контесты, уровень этих контестов меняется каждый год, уже в последнем контесте яндекса на стажировку вы можете увидеть продвинутые оптимизации ДП и MITM. Во всякие ШАДы и так понятно, что контесты требуют высокой подготовки и большой насмотренности по алгоритмам. А также всё чаще встречаются ивенты/олимпиады для студентов (например yandex cup/турниры от fonbet/чемпионат от мтс) и старше по олимпиадному программированию, за которые можно получать денежные призы/бви в магистратуры/ фасттреки в сильнейшие бигтехи или хфт конторы. FAANG+ В зарубежные компании куда сложнее отбор, зачастую там отбор состоит из 3-4 собеседований, а пару алгоритмических тем не хватит чтобы пройти эти собеседования. Там значительно объемнее алгоритмический багаж, который требуется для решения задач, и даже умения решать хард задачи на литкоде не хватит на проход. Например наш выпускник Максим (отзыв на сайте) прошел все этапы собеседования в гугл и уже окончил intern swe стажировку с зарплатой 8000$ в месяц. На самом собеседовании он как-раз решал задачу на битовый бор, который мы разбирали на первом уроке. Computer Science У многих компаний бигтеха есть свои лаборатории, в которые они направляют задачки, возникшие в процессе разработки в проде, которые не имеют решений в настоящее время. Например в т-банке есть лаборатория cs, где работает один из наших учеников Игорь. Что оптимизирует: курьеры получают на день некоторое количество заказов, а компания должна придумать сразу оптимальное разбиение всех заказов по курьерам и их маршруты так, чтобы минимальное количество топлива было затрачено на их сумму минимальных путей (почти что TSP задача). Лаборанты по большому счету работают там над теорией алгоритмов, придумывают эффективную идею и тестируют её на синтетических данных,

Задача с собеседования в 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]): - вычисляем ширину пары и обновляем результат на максимально возможный.

Задача с собеседования в 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 эл-м; эл-т, для которого счи

Задача с собеседования в 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. Теперь проверим, не стало ли пассажиров в какой-то момент больше, чем посадочных мест. Проходим по всем километрам, накапливая с

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

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

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

Полный цикл отбора в 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, чем они отличаются не только по асимптот

Задача с собеседования в Zoho Даны две строки s и t. Определите, являются ли они изоморфными. Две строки s и t называют изоморфными, если символы в строке s можно заменить так, чтобы получить t. Все вхождения определённого символа должны быть заменены другим символом с сохранением порядка следования символов. Никакие два разных символа не могут заменяться одним и тем же символом, однако, символ может быть заменён на самого себя. Пример 1: Input: s = "egg", t = "add" Output: true Explanation: Строки s и t можно сделать идентичными, если: Заменить "e" на "a". Заменить "g" на "d". Пример 2: Input: s = "f11", t = "b23" Output: false Explanation: Строки s и t невозможно сделать идентичными, так как символ "1" должен соответствовать одновременно и "2" и, "3". Пример 3: Input: s = "paper", t = "title" Output: true Ограничения: 1 <= s.length <= 5 * 10⁴ t.length == s.length s и t состоят из любых допустимых символов ASCII. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Для изоморфности двух строк необходимо, чтобы обеспечивалось взаимно-однозначное соответствие: - каждому эл-ту первой строки соответствует ровно один эл-т второй строки; - и наоборот, каждый эл-т второй строки связан ровно с одним эл-том первой строки. Создаём два словаря для двусторонней проверки соответствия: s_to_t - гарантирует, что один и тот же символ из s не будет превращён в разные символы в t t_to_s - гарантирует обратное условие: один и тот же символ из t не будет получаться из разных символов s Проходим по двум строкам одновременно с помощью функции zip(), объединяющей эл-ты из двух строк в пары символов: Если char_s уже встречался ранее и соответствовал другому символу, а не char_t ИЛИ Если char_t уже был получен из другого символа строки s, а не из char_s: - изоморфность нарушена => возвращаем False. Иначе - записываем новые двухсторонние соответствия: - в какой символ t превращается символ из s; - из какого символа s получается символ t. Если правила ни разу не нарушились, значит, строки изоморфны

Как залететь в хфт и стать миллионером, залутать сочную зумершку? Обсудим в новом ролике. Смотрим! Смотрим! https://www.youtube.com/watch?v=zXQSoJjgQG8

Задача с собеседования в Zoho Даны две строки: s и goal. Верните true, если можно поменять местами два символа в строке s так, чтобы в результате она стала равна строке goal. В противном случае верните false. Под обменом символов понимается выбор двух индексов i и j (индексация начинается с 0) таких, что i != j, и перестановка символов s[i] и s[j] местами. Например, обмен символов по индексам 0 и 2 в "abcd" даёт "cbad". Пример 1: Input: s = "ab", goal = "ba" Output: true Explanation: Вы можете поменять местами s[0] = "a" and s[1] = "b", чтобы получить "ba", что равно goal. Пример 2: Input: s = "ab", goal = "ab" Output: false Explanation: Единственные символы, которые можно поменять местами - это s[0] = "a" and s[1] = "b", в результате чего "ba" != goal. Пример 3: Input: s = "aa", goal = "aa" Output: true Explanation: Вы можете поменять местами s[0] = "a" and s[1] = "a", чтобы получить "aa", что равно goal. Ограничения: 1 <= s.length, goal.length <= 2 * 10⁴ s и goal состоят из строчных букв. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Итак, нам нужно обменять ровно две позиции строки s, в которых s и goal различаются; остальные позиции должны совпадать сразу. => различий между строками должно быть либо 2 (так как один обмен исправляет только два различия), либо 0 (то есть строки уже эквивалентны). Обрабатываем следующие случаи: - Если длина s и goal различается: False, так как обмен символов не изменит разницу в кол-ве символов. - Если строки уже эквивалентны: Необходимо наличие повторяющегося символа (проверяем, есть ли он, через сравнение строки со множеством), так как только обмен одинаковых символов не изменит строку s, уже равную goal. В этом случае возвращается true, иначе - false. - Если строки разные: Ищем две различающиеся позиции и проверяем, можно ли поменять два символа ровно одним обменом, чтобы получить goal. diff - массив индексов, где s[i] != goal[i]. Проходим по строке s: Если символ по текущему индексу в s отличается от символа по текущему индексу

Задача с собеседования в Josh Technology Обмен определяется как выбор двух различных позиций в массиве и перестановка их значений местами. Круговой массив определяется как массив, в котором первый и последний элементы считаются соседними. Дан бинарный круговой массив nums. Верните минимальное количество обменов, необходимых для того, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте. Пример 1: Input: nums = [0,1,0,1,1,0,0] Output: 1 Explanation: Есть несколько способов сгруппировать все 1 вместе: [0,0,1,1,1,0,0] с использованием 1 обмена. [0,1,1,1,0,0,0] с использованием 1 обмена. [1,1,0,0,0,0,1] с использованием 2 обменов (используя круговое свойство массива). Не существует способа сгруппировать все 1 вместе, не выполнив ни одного обмена. Таким образом, минимальное необходимое количество обменов - 1. Пример 2: Input: nums = [0,1,1,1,0,0,1,1,0] Output: 2 Explanation: Есть несколько способов сгруппировать все 1 вместе: [1,1,1,0,0,0,0,1,1] с использованием 2 обменов (используя круговое свойство массива). [1,1,1,1,1,0,0,0,0] с использованием 2 обменов. Не существует способа сгруппировать все 1 вместе с использованием 0 или 1 обменов. Таким образом, минимальное необходимое количество обменов - 2. Пример 3: Input: nums = [1,1,0,0,1] Output: 0 Explanation: Все 1 уже сгруппированы вместе, учитывая круговое свойство массива. Таким образом, минимальное количество обменов - 0. Ограничения: 1 <= nums.length <= 10⁵ nums[i] равно 0 или 1. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Обратим внимание, что кол-во единиц, которые нужно сгруппировать, фиксировано и равняется общему кол-ву единиц в массиве (total_ones). Так как единицы могут быть разбросаны по массиву, необходимо проверить каждый подмассив длиной total_ones и определить среди них тот, в котором уже находится максимальное кол-во единиц (а следовательно потребуется меньше обменов). => Кол-во необходимых обменов равняется кол-ву нулей в подмассиве с максимумом единиц (кол-во нулей = total_ones - макси