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

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

Дан целочисленный массив nums, индексированный с 0. Пара целых чисел x и y называется сильной парой, если она удовлетворяет следующему условию:
|x - y| <= min(x, y)

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

Обратите внимание, что для формирования пары вы можете выбрать одно и то же целое число дважды.

Пример 1:
Input: nums = [1,2,3,4,5]
Output: 7
Explanation: В nums есть 11 сильных пар: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) и (5, 5).
Максимальный XOR, который можно получить из этих пар, - это 3 XOR 4 = 7.

Пример 2:
Input: nums = [10,100]
Output: 0
Explanation: В nums есть 2 сильные пары: (10, 10) и (100, 100).
Максимальный XOR, который можно получить из пар, - это 10 XOR 10 = 0, так как пара (100, 100) также даёт 100 XOR 100 = 0.

Пример 3:
Input: nums = [5,6,25,30]
Output: 7
Explanation: В nums есть 6 сильных пар: (5, 5), (5, 6), (6, 6), (25, 25), (25, 30) и (30, 30).
Максимальный XOR, который можно получить из пар, - это 25 XOR 30 = 7, так как единственное другое ненулевое значение XOR равно 5 XOR 6 = 3.

Ограничения:
1 <= nums.length <= 50
1 <= nums[i] <= 100

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Итак, у нас есть условие формирования сильной пары: |x - y| <= min(x, y). Относительно x и y условие симметрично, мы можем поменять их местами, и |x - y| не изменится, так же, как и min(x, y). Получается, для проверки пары нет разницы, в каком порядке брать числа.
Однако, для упрощения выражения будет удобнее, если обозначим, какое число меньше, а какое больше.
Допустим, x - меньшее число, а y - большее. Следовательно:
min(x, y) = x
|x - y| = y - x

Если отсортировать массив, то для x и y выполняется x <= y (где i < j, x = nums[i], y = nums[j] и nums[i] <= nums[j]).

Таким образом, |x - y| <= min(x, y) =>
y - x <= x =>
y <= 2x
Условие сильной пары: большее число не более чем в два раза превышает меньшее.

Для решения оптимально использовать алгоритм "скользящего окна" с двумя указателями:
Если зафиксировать больший (правый, nums[right]) эл-т в отсортированном массиве, то для формирования сильной пары необходимо найти все nums[i] слева от него, для которых nums[right] <= 2 * nums[i].
Учитывая, что массив отсортирован, при движении влево - nums[i] уменьшается. => Если nums[right] <= 2 * nums[left], то для любого k в диапазоне [left, right] будет выполняться nums[right] <= 2 * nums[k]. Этот диапазон [left, right] - и есть окно.
left движется только вперёд, так как при возрастании right порог 2 * nums[left] растёт.
Ограничения в задаче маленькие, поэтому можно обойтись без оптимизации перебора внутри окна.

Алгоритм:
Сортируем массив nums.

Переменные:
res - текущий максимальный XOR среди сильных пар.
left - левая граница окна.

Двигаем правый указатель right по массиву:
Пока условие сильной пары нарушается - nums[right] > 2 * nums[left]:
- сдвигаем left вправо, сужая окно, пока nums[right] не образует валидную пару с nums[left].

После того, как все эл-ты в диапазоне [left, right] формируют сильные пары с nums[right], перебираем эл-ты [left, right]:
- обновляем максимальный res (res = max(res, nums[i] ^ nums[right])).

Возвращаем res с максимальным значением XOR среди всех сильных пар.

Сложность
O(n^2) - по времени (в худшем случае, когда все эл-ты равны, внутренний цикл: окно не сужается, для каждого right перебираются все left <= right; в лучшем случае - O(n log n) - сортировка)
O(1) - по памяти (храним переменные; без учёта сортировки)

Код
class Solution:
def maximumStrongPairXor(self, nums: List[int]) -> int:
nums.sort()
res = 0
left = 0

for right in range(len(nums)):
while nums[right] > 2 * nums[left]:
left += 1

for i in range(left, right + 1):
res = max(res, nums[i] ^ nums[right])

return res

@algoses

Полный цикл отбора в Касперский (Бэкенд)

От выпускника нашего курса "Бэкенд Про". Там же уже выложен разбор направлений GO, Pythonнабора на стажировку Касперского Safeboard.
➡️ Записаться

Вступительный тест
Подавался на бэкенд С++, тест был на платформе типа stepik, включал пару десятков вопросов типа тестовых и пару задач контестного типа, в которых требуется написать код. Были вопросы по языку и общим техническим темам (сети, общие практики разработки, Linux). Задачи несложные, просто знания алгоритмов и языка, но были случаи вида "исправьте уязвимости в данном коде".

После прохождения пришло письмо с тестовым и видеоинтервью.

Тестовое задание
Разработка аналогов популярных и не очень утилит Unix или утилит в их стиле. Примеры здесь. В моём случае это был частный случай утилиты find с поддержкой рекурсивного поиска и регулярных выражений. Как я понял не нужно пытаться написать код "на максималках", но документация с тем же Doxygen, тесты и нормальная инфра вокруг решения будут плюсом.

Видеоинтервью
Нужно было записать ответы на десяток вопросов по 2-3 минуты в среднем. Вопросы были как из разряда "какой свой проект вы считаете самым интересным и почему", так и глубоко техническими вроде продвинутых механизмов языка, принципов работы операционных систем или, например, сетевых протоколов. Примеры здесь.

Приходит рекрутер с обратной связью. Говорит, что прошёл на следующий этап и назначает собеседование на 1 час с каждой заинтересованной во мне командой.

Собеседование
Обсуждали как мотивацию и опыт, так и технические темы. Были вопросы на более-менее математические темы вроде свойств хеш-функций, средства языка и устройство вычислительных системы (osdev и немного о железе).
Задача 1: корректным образом посчитать ненулевые биты в int с учётом отрицательных чисел и переносимости.
Задача 2: развернуть строку на языке C.
Задача 3: развернуть строку по словам (то есть условно "один два три" переходит в "три два один").
Все задачи нетрудные и постоянно разбираются здесь.

Рекрутер пришел с оффером.

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

В IT всегда есть что изучить. Найти бы на всё время.

Python, фронтенд, нейросети, бэкенд — хочется разобраться во всём, но лучше начать с того, что интересно именно вам.

Собрали каналы по разным IT-направлениям, чтобы было проще выбрать:

👉 Журнал об IT

🖥 Фронтенд разработка

🖥 Data Science | Machinelearning

🖥 Node js | Backend

👩‍💻 Вёрстка

🖥 Python | Backend

🖥 QA

Уже работаете в IT? Загляните в своё направление.
Присматриваетесь к профессии? Посмотрите, что вам ближе.

Выберите канал и подписывайтесь.

Как школьнику попасть в IT ещё до университета

Стартовала регистрация на Всероссийскую олимпиаду по программированию «Технокубок», организованную МФТИ, МГТУ имени Н. Э. Баумана и компанией VK. В этом году к школьникам 8–11 классов впервые присоединились студенты колледжей.

Олимпиада — это не только возможность проверить свои навыки, но и способ заработать бонусы при поступлении. У «Технокубка» первый уровень в перечне РСОШ, поэтому победители и призёры могут поступить в вуз без вступительных испытаний или получить 100 баллов за ЕГЭ по информатике. Диплом действует четыре года.

Задания олимпиады связаны с алгоритмами и структурами данных. Решать их можно на разных языках программирования — от Python и C++ до JavaScript и Kotlin. Кроме стандартных задач, будут специальные задания от команд VK с дополнительными призами.

Отборочные онлайн-этапы пройдут 8 ноября и 6 декабря, очный отбор — 30 января, финал в Москве — 12–14 марта. Регистрация открыта до 6 декабря на платформе All Cups.

Помимо подарков от организаторов, победителей ждут персональные профориентационные консультации с экспертами VK. Участие в олимпиаде — возможность не только побороться за поступление в технический вуз, но и познакомиться с реальными задачами из мира разработки.

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

Дана строка s, проверьте, можно ли составить её, взяв какую-либо её подстроку и повторив её два или более раз подряд.

Пример 1:
Input: s = "abab"
Output: true
Explanation: Это подстрока "ab", повторяющаяся дважды.


Пример 2:
Input: s = "aba"
Output: false

Пример 3:
Input: s = "abcabcabcabc"
Output: true
Explanation: Это подстрока "abc", повторяющаяся четыре раза, или подстрока "abcabc", повторяющаяся дважды.

Ограничения:
1 <= s.length <= 10⁴
s состоит из строчных английских букв.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Если s состоит из повторяющихся подстрок, то у неё есть длинный собственный префикс, равный её суффиксу.
Классический метод решения задачи - префикс-функция из алгоритма Кнута-Морриса-Пратта.
Префикс-функция даёт длины наибольших бордеров для всех префиксов.
Бордер - собственный префикс строки, являющийся одновременно её суффиксом. Необходимо проверить, образует ли бордер период всей строки.

Создаем массив lps (longest prefix-suffix), где lps[i] хранит длину наибольшего собственного префикса подстроки s[0..i], который одновременно является её суффиксом.
Если при вычислении префикс-функции символы не совпадают, длина префикса (k) не сбрасывается в ноль, а "откатывается" к уже вычисленному значению для более короткого префикса.

Идём по строке слева направо, храня k - длину текущего совпавшего префикса:
Пока k > 0 (префикс непустой) и s[i] != s[k] (символы не совпали):
- "откатываемся" к наибольшему валидному бордеру меньшей длины: k = lps[k - 1] (если префикс s[0..k-1] равен суффиксу s[i-k..i-1], то любой бордер строки s[0..k-1] также является бордером и для s[0..i-1]. Наибольший такой бордер имеет длину lps[k - 1]).
Если s[i] == s[k]:
- продлеваем совпавший префикс текущим символом (k += 1).
Записываем результат: lps[i] = k.

Разберем на примере 1, где s = "abab":
- Подстрока "a" (i = 0): собственных префиксов нет => lps[0] = 0.
- Подстрока "ab" (i = 1): префикс "a" != суффикс "b" => lps[1] = 0.
- Подстрока "aba" (i = 2): префикс "a" == суффикс "a" => lps[2] = 1.
- Подстрока "abab" (i = 3): префикс "ab" == суффикс "ab" => lps[3] = 2.
Получившийся массив lps: [0, 0, 1, 2]

L (длина бордера всей строки) = lps[n - 1]. Если L > 0, то префикс длины L совпадает с суффиксом длины L: s[0..L-1] == s[n-L..n-1].
Суффикс начинается с индекса n - L, т.е. для любого индекса j от 0 до L-1 будет выполняться s[j] == s[j + (n - L)]. Таким образом, строка сдвигается сама на себя с шагом p = n - L.
p - кандидат на длину минимального периода.

Чтобы строка состояла из точных повторов этого периода, должны выполняться следующие два условия:
- L > 0 (иначе p = n и n % n == 0 даст true для любой строки, к примеру, "abcd")
- n % p == 0 (общая длина строки должна нацело делиться на длину периода. К примеру, для "ababa", где n = 5, L = 3, p = 2 и 5 % 2 != 0).

Сложность
O(n) - по времени (k увеличивается не более чем на 1 за каждую итерацию внешнего цикла for, в цикле while - k только уменьшается. Таким образом, суммарное число итераций while не превышает n)
O(n) - по памяти (строим массив lps)

Код
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
lps = [0] * n

for i in range(1, n):
k = lps[i - 1]

while k > 0 and s[i] != s[k]:
k = lps[k - 1]

if s[i] == s[k]:
k += 1

lps[i] = k

L = lps[n - 1]
p = n - L

return L > 0 and n % p == 0

@algoses

Что делать с данными? 💬

Строить отчёты. А ещё, например:
✅находить закономерности в больших массивах;
⬜️предсказывать поведение пользователей;
⬜️строить рекомендательные системы;
⬜️обучать и улучшать ML-модели;
⬜️создавать продукты и помогать бизнесу расти.

В Школе аналитиков данных МТС учатся решать такие задачи на практике.
В программе — SQL и Python, математика и статистика, анализ данных, машинное обучение и большие данные, а также нейросети и рекомендательные системы.

Занятия ведут действующие эксперты Центра BigData MWS. Теория чередуется с практикой, а преподаватели дают обратную связь по работам и помогают отслеживать прогресс.

Это будет интересно:
➡️студентам последних курсов и выпускникам технических вузов
➡️алитикам данных, которые хотят погружаться в исследования
➡️ИТ-специалистам, которые хотят перейти в новое для себя направление

Обучение продлится 10 месяцев и будет полностью бесплатным.

⚡️ Сейчас — последний шанс подать заявку, так как прием закрывается 25 октября. Для поступления кандидатам предстоит заполнить анкету, написать мотивационное письмо и пройти отборочное тестирование.

Отправить заявку ↗️

Стажировка в BigTech или ШАД? Будь готов, что спросят про LLM.

На собесах в ML всё чаще говорят про агентов, RAG и свежие модели. Пока ты решаешь матан, индустрия уже ушла туда.

Каждый день разбираем коротко, с кодом и ссылками на статьи. Чтобы на собесе было что рассказать.

🎁 А для своих собрали папку для подготовки-: матан, бесплатные книги по ИИ и стажировки.

Читай до собеса, а не после: telemetr.me/data_analysis_ml