Алгоритмы - Чат

Всем привет, подскажите пж эффективный план изучения алгоритмов для собесов

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

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

Как попасть в 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 задачи слож

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

Полный цикл отбора в 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 - макси