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

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

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

Олимпиады и магистратуры
Почти на любую школу/стажировку/магистратуру вы пишете контесты, уровень этих контестов меняется каждый год, уже в последнем контесте яндекса на стажировку вы можете увидеть продвинутые оптимизации ДП и MITM. Во всякие ШАДы и так понятно, что контесты требуют высокой подготовки и большой насмотренности по алгоритмам. А также всё чаще встречаются ивенты/олимпиады для студентов (например yandex cup/турниры от fonbet/чемпионат от мтс) и старше по олимпиадному программированию, за которые можно получать денежные призы/бви в магистратуры/ фасттреки в сильнейшие бигтехи или хфт конторы.

FAANG+
В зарубежные компании куда сложнее отбор, зачастую там отбор состоит из 3-4 собеседований, а пару алгоритмических тем не хватит чтобы пройти эти собеседования. Там значительно объемнее алгоритмический багаж, который требуется для решения задач, и даже умения решать хард задачи на литкоде не хватит на проход. Например наш выпускник Максим (отзыв на сайте) прошел все этапы собеседования в гугл и уже окончил intern swe стажировку с зарплатой 8000$ в месяц. На самом собеседовании он как-раз решал задачу на битовый бор, который мы разбирали на первом уроке.

Computer Science
У многих компаний бигтеха есть свои лаборатории, в которые они направляют задачки, возникшие в процессе разработки в проде, которые не имеют решений в настоящее время. Например в т-банке есть лаборатория cs, где работает один из наших учеников Игорь. Что оптимизирует: курьеры получают на день некоторое количество заказов, а компания должна придумать сразу оптимальное разбиение всех заказов по курьерам и их маршруты так, чтобы минимальное количество топлива было затрачено на их сумму минимальных путей (почти что TSP задача). Лаборанты по большому счету работают там над теорией алгоритмов, придумывают эффективную идею и тестируют её на синтетических данных, а уже потом предложенную идею отправляют в прод. Здесь полноценный ресерч, вы должны не просто уметь хорошо решать задачи, но и должны знать большое количество алгоритмов и идей.

HFT
Даже в фонды среднячки нужна серьезная алгоритмическая подготовка, недавно мы узнали, что наш ученик Артем (смотрите на сайте), как раз устроился через пару месяцев после курса по алгосам в Fast Forward. А ранее ему дали задачу на собеседовании в Spectral рейтинга 2000 на кфе, и эту секцию он легко прошел. В хфт есть несколько направлений SWE, QR и Trader. На каждое из этих направлений нужны очень сильные алгоритмы. Отчасти стэк технологий трейдера и задачи его покрывают qr и swe, поэтому рассмотрим потребность в алгоритмах от его лица. Всё сказанное про ML и Бэк верно и для него, но только требуется еще более глубокое понимание всего. Например здесь же уже нужно понимать как реализованы внутри модели, какие структуры они используют, как их оптимизировать, а также и сами нюансы внутренние у реализаций библиотек. Здесь также и требуется иметь навыки бэкендера, но тут уже нужно глубокое понимание языка (чаще всего плюсов) на уровне количества инструкций в той или иной среде для какой-либо операции, а также нужно отлично знать алгоритмы и уметь их применять (последнее вдвойне ценится). Тут уже зачастую недостаточно придумать асимптотически наилучшее решение, нужно искать кучу неасимптотических оптимизаций для частных случаев данных.

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

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

Инвертирование бита числа x - это выбор какого-либо бита в двоичном представлении числа x и изменение его значения с 0 на 1 или с 1 на 0.
Например, для x = 7 двоичное представление - 111, и мы можем выбрать любой бит (включая ведущие нули, которые не показаны) и инвертировать его. Мы можем инвертировать первый бит справа, чтобы получить 110, инвертировать второй бит справа, чтобы получить 101, инвертировать пятый бит справа (ведущий ноль), чтобы получить 10111, и так далее.
Даны два целых числа start и goal. Верните минимальное количество инвертирований битов, чтобы преобразовать start в goal.

Пример 1:
Input: start = 10, goal = 7
Output: 3
Explanation: Двоичное представление 10 и 7 - это 1010 и 0111, соответственно. Мы можем преобразовать 10 в 7 за 3 шага:
- Инвертировать первый бит справа: 1010 -> 1011.
- Инвертировать третий бит справа: 1011 -> 1111.
- Инвертировать четвёртый бит справа: 1111 -> 0111.
Можно показать, что преобразовать 10 в 7 менее чем за 3 шага невозможно. Следовательно, возвращаем 3.

Пример 2:
Input: start = 3, goal = 4
Output: 3
Explanation: Бинарное представление 3 и 4 - это 011 и 100, соответственно. Мы можем преобразовать 3 в 4 за 3 шага:
- Инвертировать первый бит справа: 011 -> 010.
- Инвертировать второй бит справа: 010 -> 000.
- Инвертировать третий бит справа: 000 -> 100.
Можно показать, что преобразовать 3 в 4 менее чем за 3 шага невозможно. Следовательно, возвращаем 3.

Ограничения:
0 1
start ^ goal даёт значение, в котором единицы стоят в тех позициях, где биты различаются.

Теперь посчитаем кол-во единиц в значении xor, используя побитовый И:
- только если оба бита равны 1 -> 1
- иначе -> 0

Пока xor больше 0 (есть хотя бы одна единица):
- xor & (xor - 1):
При (xor - 1) получаем новое число, в котором самая правая единица инвертируется в ноль, все нули справа от неё - в единицы, а биты слева - не изменяются.
Затем при операции побитового И(&) между этим новым значением и исходным числом:
Биты слева не меняются, так как одинаковы в обоих числах;
Самая правая единица обнуляется;
Все биты справа остаются нулями.
Таким образом, удаляется ровно одна правая единица.

- на каждой итерации увеличиваем count (кол-во единиц в xor) на 1.

Возвращаем count, хранящее кол-во единиц в xor, а значит, минимальное кол-во инвертирований битов.

Сложность
O(k) - по времени (где k - кол-во единиц в xor)
O(1) - по памяти (храним переменные count и xor)

Код
class Solution:
def minBitFlips(self, start: int, goal: int) -> int:
count = 0
xor = start ^ goal

while xor:
xor = xor & (xor - 1)
count += 1

return count

@algoses

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

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

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

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

Ограничения:
1

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

Дан целочисленный массив nums, индексированный с 0, и целое число p. Найдите p пар индексов массива nums так, чтобы максимальная разность среди всех этих пар была минимальна. Гарантируется, что ни один индекс не используется более одного раза среди всех p пар.
Обратите внимание, что для пары элементов с индексами i и j разность этой пары равна |nums[i] - nums[j]|, где |x| обозначает абсолютное значение x.
Верните минимально возможное значение максимальной разницы среди всех p пар.
Максимум пустого множества считается равным 0.

Пример 1:
Input: nums = [10,1,2,7,1,3], p = 2
Output: 1
Explanation: Первая пара образована индексами 1 и 4, вторая - индексами 2 и 5. Максимальная разность составляет max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Следовательно, возвращаем 1.

Пример 2:
Input: nums = [4,2,1,2], p = 1
Output: 0
Explanation: Пусть индексы 1 и 3 формируют пару. Разность для этой пары равна |2 - 2| = 0, что является минимально возможным значением.

Ограничения:
1

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

Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно два раза. Найдите два элемента, которые появляются только один раз. Вы можете вернуть ответ в любом порядке.
Вы должны написать алгоритм, который работает за линейное время и использует только константное дополнительное пространство.

Пример 1:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] - также валидный ответ.

Пример 2:
Input: nums = [-1,0]
Output: [-1,0]

Пример 3:
Input: nums = [0,1]
Output: [1,0]

Ограничения:
2 нужный бит найден - второй разряд справа.

Также для нахождения младшего единичного бита-разделителя можно было бы использовать формулу: diff_bit = xor & -xor (рекомендую почитать о «дополнительном коде»).

Таким образом, зная разделяющий бит, можем использовать его для распределения чисел по двум группам.
Проходим по массиву nums, проверяя для каждого числа:
- если diff_bit & текущее число не равно нулю => у числа стоит 1 в том же разряде, что и у diff_bit;
- иначе => стоит 0.
Уникальные числа a и b различаются в выбранном бите, а значит, попадут в разные группы. Парные же числа, имея одинаковые биты, попадут в одну и ту же группу и «обнулятся» при операции XOR. В каждой группе останется одно искомое число.

Выводим найденные числа в виде массива.

Сложность
O(n) - по времени (проходим двумя циклами по n элементам)
O(1) - по памяти (храним целочисленные переменные xor, diff_bit, a, b)

Код
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for n in nums:
xor ^= n

diff_bit = 1
while not(xor & diff_bit):
diff_bit = diff_bit

Нужны ли алгоритмы сейчас, в эпоху ИИ, на собесах

До 2025 года из каждого утюга вы слышали про эти "алгособесы". Любой отбор в школы, на стажировки или штатные позиции обязательно выглядел как школьная олимпиада по программированию. А основная подготовка к выходу на работу заключалась в нарешивании Литкода.

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

1. рассказ про опыт и свои харды;
2. решение брейн-тизеров и алгоритмических задач.

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

А что сейчас
Некоторые компании отказались от отдельных алгособесов, но оставили задачки в других секциях (livecoding). Однако в крупных бигтехах алгосекция все так же существует. Более того, в зарубежных вакансиях алгоритмические секции сейчас, наоборот, снова в тренде.

Чем обусловлен небольшой спад тренда? Компании перегрели кандидатов: на секциях стали спрашивать слишком простые задачки, которые при хорошей подготовке никак не отражают объективно твое умение строить алгоритмы. По сути, их можно просто "зарешать" количеством, и на собесе ты решишь задачу не потому, что придумал решение, а потому что встречал похожую идею раньше.
Но альтернативу алгосам так и не придумали. Давать математический брейн-тизер бэкендеру странно, а усложнить алгозадачу до уровня, где нельзя натренировать типовые паттерны - перебор, ведь это лишь метод проверки мышления, спрашивать вкатуна систем дизайн- ту мач.

Главный вывод.
Алгоритмический аппарат в эпоху LLM станет как никогда актуальным. Ваша задача на работе будет сводиться к тому, чтобы быстро валидировать код, написанный нейросеткой. Это значит, что вам нужно моментально разбираться в чужом коде и видеть узкие места. Именно такие навыки и тренируют алгоритмические задачки.

Поэтому не стоит надеяться, что алгосы пропадут с рынка. В будущем это будет наиболее актуальный и надежный инструмент проверки твоего инженерного мышления.

Что с этим делать и как подготовиться
Если вы готовитесь к собеседованиям, важно понимать: алгоритмы - это не про запоминание 500 задач, а про тренировку шаблонов мышления. Чтобы решать задачи за 20 минут, нужно не заучивать код, а видеть структуру задачи сходу.

Но просто читать про это недостаточно. Чтобы выйти на алгособес уверенно, нужна системная практика с разбором реальных кейсов.
Если хотите оставаться в тренде IT-рынка и его жестких требований, советую наши курсы «Старт». У нас есть отдельный курс по алгоритмам, разбор реальных задач с собеседований в топ-компаниях и подходы, которые учат именно думать, а не зубрить.

Специально для подписчиков канала мы продлили финальные скидки на обучение на 24 часа. Если давно хотели прокачать свой алгоритмический аппарат до уровня топ-компаний, сейчас лучший момент. Это последний шанс взять комбо: алгоритмы + любой курс по специальности по хорошей цене и уже осенью залутать оффер!
➡️ Записаться

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

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

Дана строка num, представляющая собой большое целое число. Число считается "хорошим", если оно удовлетворяет следующим условиям:
- оно является подстрокой длиной 3 в строке num
- все три цифры в числе одинаковы
Верните максимальное "хорошее" число в виде строки или пустую строку "", если такого числа не существует.
Обратите внимание, что строка num или "хорошее" число могут содержать ведущие нули.

Пример 1:
Input: num = "6777133339"
Output: "777"
Explanation: в строке содержатся два "хороших" числа: "777" и "333".
"777" больше, возвращаем "777".

Пример 2:
Input: num = "2300019"
Output: "000"
Explanation: "000"- единственное "хорошее" число.

Пример 3:
Input: num = "42352338"
Output: ""
Explanation: строка не содержит подстроку из трёх одинаковых цифр. Следовательно, "хорошего" числа не существует.

Ограничения:
3

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

Дан массив nums, состоящий из различных чисел в диапазоне от 0 до n. Верните единственное число из диапазона, отсутствующее в массиве.

Follow up: можете ли вы реализовать решение с использованием лишь O(1) дополнительной памяти и временной сложностью O(n)?

Пример 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n=3, так как в массиве три числа; таким образом, все числа находятся в диапазоне [0, 3]. Число 2 отсутствует в этом диапазоне, поскольку его нет в массиве nums.

Пример 2:
Input: nums = [0,1]
Output: 2
Explanation: n=2, так как в массиве 2 числа; таким образом, все числа находятся в диапазоне [0, 2]. Число 2 отсутствует в этом диапазоне, поскольку его нет в массиве nums.

Пример 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n=9, так как в массиве 9 чисел; таким образом, все числа находятся в диапазоне [0, 9]. Число 8 отсутствует в этом диапазоне, поскольку его нет в массиве nums.

Ограничения:
n == nums.length
1

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

Дана строка s, верните true, если возможно разделить её на 3 непустые палиндромные подстроки. В противном случае верните false.
Строка называется палиндромом, если в перевёрнутом виде она остаётся той же самой строкой.

Пример 1:
Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", все три подстроки являются палиндромами.

Пример 2:
Input: s = "bcbddxy"
Output: false
Explanation: s нельзя разделить на 3 палиндрома.

Ограничения:
3 можно разбить на 3 палиндрома => возвращаем True.
Иначе возвращаем False.

Сложность
O(n^2) - по времени (строим дп-таблицу за n^2, перебираем разрезы за n^2)
O(n^2) - по памяти (храним дп-таблицу)

Код
class Solution:
def checkPartitioning(self, s: str) -> bool:
n = len(s)

dp = [[False] * n for _ in range(n)]

for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j]:
dp[i][j] = (j - i