tgindex

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

описание

Номер заявления регистрацию в РКН: № 5731053751 Чат: @algoses_chat По всем вопросам: @vice22821

← к каналу@algoses
11 979
подписчиков
Охват к подписчикам
21,9%
ERR
Реакции к просмотрам
0,29%
166 на 21 постов
Пересылки к просмотрам
0,60%
341
Постов в день
0,6
всего 22

Где отзываются чаще

доля реакций к просмотрам
  • 10 авг.без подписи2,39%
  • 13 авг.Студенты, новость для вас: Т-технологии создали гайд для работы с крупнейшим открытым датасет T-ECD На одной из крупнейших конференций уровня A* по машинному обучению и анализу данных исследователи из Т-Технологий представили техрепорт T-ECD — обезличенного датасета, приближенного к реальным данным бизнеса е-ком. Отчет разослали руководителям академических программ и преподавателям ведущих ИТ-вузов России вместе с инструкцией и примерами использования в исследованиях и учебных проектах. В датасете 135 млрд обезличенных взаимодействий, но есть и компактная версия — с ней можно работать без мощной GPU-инфраструктуры, а для серьёзных экспериментов предусмотрены сценарии вплоть до 8 H100. Это позволит студентам тренировать модели рекомендательных систем на данных, близких к реальным бизнес-сценариям.1,94%
  • 11 авг.Задача с собеседования в 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 <= nums.length <= 3 * 10⁴ -2³¹ <= nums[i] <= 2³¹ - 1 Каждое число в nums встретится два раза, только два числа встретятся один раз. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Более сложный вариант задачи на использование побитового оператора XOR (исключающего ИЛИ), сравнивающего два бита: - если биты одинаковые -> 0 - если биты разные -> 1 Применяем XOR для "обнуления" всех чисел в массиве, которые встречаются два раза, используя свойства: a ^ a = 0 и a ^ 0 = a. Предварительная сортировка не требуется, так как a ^ b = b ^ a. - проходим по массиву nums, накапливая XOR всех эл-в. Таким образом, получим XOR = a ^ b, где a и b - искомые числа. Теперь у нас есть некоторое значение XOR, хранящееся в двоичном виде. Предлагаю разобрать подробнее на примере 1: после первого прохода XOR = 3 ^ 5 = 6. В двоичном виде это выглядит следующим образом: 3 = 0 1 1 5 = 1 0 1 6 = 1 1 0 Единицы находятся в тех разрядах, где биты у a и b различаются => можем использовать какой-либо из этих разрядов в качестве разделителя. Найдём самый младший единичный бит с помощью цикла while: Пока XOR & diff_bit равно нулю: - ищем единичный бит, перебирая битовые позиции справа налево с помощью переменной diff_bit, сдвигая единицу из младшего разряда в старший. На примере XOR = 6 (110): diff_bit = 1 (001): 110 & 001 = 0 diff_bit = 2 (010): 110 & 010 = 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 << 1 a, b = 0, 0 for n in nums: if diff_bit & n: a = a ^ n else: b = b ^ n return [a, b] @algoses0,73%
  • 12 авг.Задача с собеседования в 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 <= nums.length <= 10⁵ 0 <= nums[i] <= 10⁹ 0 <= p <= (nums.length) / 2 НАШ ЧАТ АЛГОРИТМИСТОВ Решение Необходимо найти минимальный x, при котором можно сформировать p пар с разностью <= x. Свойство монотонно: если можно составить p пар с максимальной разностью x, то можно и с любой разностью > x (ограничение слабее). Если нельзя с x, то нельзя и с меньшей разностью (ограничение жёстче). Существует граница между значениями, где условие выполнено, и где это невозможно. Границу можно найти бинарным поиском: будем перебирать значение x (максимально допустимую разность) в диапазоне от 0 до максимально возможной разности в массиве. Для проверки конкретного значения создаём функцию can_form_pairs(max_diff), где max_diff - текущий кандидат на максимально допустимую разность в паре. Используя жадный алгоритм, проверяем, можно ли сформировать p пар. pairs - счётчик пар i - текущий индекс Проходим по массиву: - Если разность между соседними числами (i и i+1) <= max_diff: засчитываем пару и пропускаем использованный эл-т: i += 2; - Иначе: пропускаем текущий эл-т: i += 1. Жадный выбор оптимален: - Если разность подходит: если не взять пару (i, i+1), nums[i] не сможет образовать пару с кем-либо ещё - эл-ты правее i+1 дадут разность больше. Формируя пару (i, i+1), i+1 теперь не сможет составить пару с i+2, но разность в этой паре была бы не меньше текущей. Значит, общее кол-во возможных пар не уменьшается. - Если разность не подходит: nums[i] не сможет сформировать пару - разность с любым последующим эл-м ещё больше. Если сформировали p пар - max_diff допустим: True. Иначе: False. Применяем бинпоиск на предварительно отсортированном массиве. В отсортированном массиве оптимальные пары всегда состоят из соседних эл-в. Диапазон: от left = 0 до right = nums[-1] - nums[0] Пока left < right: - вычисляем середину; - проверяем середину с помощью функции can_form_pairs(mid): если True: текущее ограничение выполнимо, пробуем уменьшить: right = mid. иначе: слишком маленькое, left = mid + 1. Возвращаем left со значением искомого минимума. Сложность O(n log n + n log m) - по времени (сортировка - O(n log n), бинпоиск - O(log m) итераций (где m - разность между максимумом и минимумом), на каждой - проверка за O(n)) O(1) - по памяти (храним некоторое кол-во переменных) Код class Solution: def minimizeMax(self, nums: List[int], p: int) -> int: def can_form_pairs(max_diff: int) -> bool: pairs = 0 i = 0 while i < len(nums) - 1 and pairs < p: if nums[i+1] - nums[i] <= max_diff: pairs += 1 i += 2 else: i += 1 return pairs >= p nums.sort() left = 0 right = nums[-1] - nums[0] while left < right: mid = (left + right) // 2 if can_form_pairs(mid): right = mid else: left = mid + 1 return left @algoses0,65%
  • 4 авг.C какими айтишницами стоит строить отношения, а какие - ред флаг? В новом ролике разобрал все бигтехи по фактам: Яндекс, ВК, Т-банк, Озон, Сбер. Смотрим! Смотрим! И не говорите потом, что не предупреждал! https://www.youtube.com/shorts/d_lUVE5oo7A0,52%
  • 8 авг.Школьная сборная России третий год подряд стала абсолютным чемпионом на Международной олимпиаде по искусственному интеллекту IOAI-2026 Команда завоевала 8 медалей — 7 золотых и 1 бронзовую — и вновь доказала, что талант и знания открывают путь к большим победам. Отбор проходил в СберУниверситете, а к турниру IOAI ребят готовили эксперты Альянса в сфере ИИ и Центрального университета. В этом году конкуренция выросла кратно, но наши ребята снова оказались сильнейшими среди участников из более 100 стран в решении задач на самом фронтире технологий. Поздравляем победителей!0,46%
  • 8 авг.Осенний найм уже на старте! Осенью запускаются стажировки, открываются вакансии и поэтому август — лучшее время для подготовки: понять, что спрашивают на отборах, оценить свой уровень и закрыть пробелы до начала учебы! Поэтому не упусти финальную распродажу курсов «СТАРТ» — любой курс всего за 6 490 ₽ ➡Аналитика ➡Алгоритмы ➡Backend ➡Machine Learning Почему сейчас лучшее время присоединиться: ✔️Гибкий старт: все лекции по техническим темам уже выложены и доступны — проходите в своём темпе, а куратор остается на связи и проверит дз и проекты. ✔️Карьерный блок: онлайн-семинарам по софтам. Напишете резюме, которое пройдет скрининг, даже если нет опыта, отработаете самопрезенатицию, пройдёте mock-собеседование с обратной связью. ✔️Закрытый банк вопросов с реальных интервью Яндекса, Т-Банка, Ozon, WB, Авито и других топ-компаний. ✔️Разбор текущего отбора на стажировок Яндекса. ✔️ Реферальная рекомендация в бигтех после успешной защиты пет-проекта. Выгодное комбо: ➡️Алгоритмы + любой курс всего за 9 990 ₽⬅️ Берите Backend, ML или Аналитику и параллельно ботайте алгоритмы — они встречаются везде, без хороших алгосов не пройти отбор в хорошую компанию. 🔊 Распродажа только 8-9 августа. Подробную программу смотрите на сайте 📌Для вопросов и записи на курс напишите менеджеру0,45%
  • 4 авг.Задача с собеседования в 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 <= n <= 10⁴ 0 <= nums[i] <= n Все числа в nums уникальны. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Задача может быть решена арифметическим способом: подсчитываем сумму всех чисел диапазона от 0 до n и вычитаем из неё сумму эл-тов входного массива - разница равняется отсутствующему числу. Предлагаю разобрать более интересный вариант решения с помощью побитового оператора XOR (исключающего ИЛИ), сравнивающего два бита: - если биты одинаковые -> 0 - если биты разные -> 1 Применяем XOR для "обнуления" повторяющихся значений из массива nums и полного набора чисел диапазона от 0 до n, используя свойство: a ^ a = 0. Отсутствующее число встретится только один раз и останется в результате по свойству a ^ 0 = a. Предварительная сортировка массива не требуется, так как a ^ b = b ^ a. - проходим циклом по числам от 0 до n, накапливая XOR в res; - проходим циклом по массиву nums, также накапливая XOR; - возвращаем res. Сложность O(n) - по времени (проходим двумя циклами по n элементам) O(1) - по памяти (храним только одну переменную res) Код class Solution: def missingNumber(self, nums: List[int]) -> int: n = len(nums) res = 0 for i in range(n + 1): res ^= i for num in nums: res ^= num return res @algoses0,44%
  • 31 июл.Уточнил у кандидата работал ли он со скоринговыми моделями как "Ясасу Бибу" и "Цист Яна". Ответ убил. https://youtube.com/shorts/ccNWpP5grzg0,25%
  • 28 июл.Задача с собеседования в TCS Дан целочисленный массив nums. Изначально вы находитесь на первом индексе массива, а каждый элемент массива представляет максимальную длину прыжка из этой позиции. Верните true, если вы можете достичь последнего индекса, или false в противном случае. Пример 1: Input: nums = [2,3,1,1,4] Output: true Explanation: Прыгаем на 1 шаг с индекса 0 на 1, а затем — на 3 шага к последнему индексу. Пример 2: Input: nums = [3,2,1,0,4] Output: false Explanation: Вы всегда будете оказываться на индексе 3. Максимальная длина прыжка равно 0, из-за чего добраться до последнего индекса невозможно. Ограничения: 1 <= nums.length <= 10⁴ 0 <= nums[i] <= 10⁵ НАШ ЧАТ АЛГОРИТМИСТОВ Решение Используем жадный алгоритм: максимальная достижимая позиция является локальным оптимумом; нам не нужно выбирать, на сколько позиций стоит прыгнуть, а только знать - какой самый дальний индекс можем достичь на текущей итерации. max_reach - самый дальний индекс, до которого можем допрыгнуть; инициализируем, как 0, так как начинаем с индекса 0. Проходим по массиву nums (i - индекс, на который хотим прыгнуть на текущей итерации): - Если i больше значения max_reach: мы застряли и не можем достичь проверяемой позиции -> достичь конца массива невозможно, возвращаем False; - Иначе, если можем достичь индекса i: из текущей позиции можно прыгнуть на nums[i] шагов, то есть возможно достичь индекса (i + nums[i]). Сравниваем прошлый максимум доступной нам дальности с новым, обновляя max_reach. Если удалось пройти от начала до конца массива, возвращаем True. Сложность O(n) - по времени (один раз проходим по массиву длиной n) O(1) - по памяти (храним только одну переменную max_reach) Код class Solution: def canJump(self, nums: List[int]) -> bool: max_reach = 0 for i in range(len(nums)): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) return True @algoses0,23%
  • 23 июл.Задача с собеседования в TCS Дан целочисленный массив nums, передвиньте все чётные числа в начало массива, а за ними — все нечётные. Верните любой массив, удовлетворяющий этому условию. Пример 1: Input: nums = [3,1,2,4] Output: [2,4,3,1] Explanation: результаты [4,2,3,1], [2,4,1,3] и [4,2,1,3] также были бы приняты. Пример 2: Input: nums = [0] Output: [0] Ограничения: 1 <= nums.length <= 5000 0 <= nums[i] <= 5000 НАШ ЧАТ АЛГОРИТМИСТОВ Решение Используем метод двух указателей, движущихся в одном направлении (в этом случае сохранится относительный порядок чётных чисел в массиве): left - индекс, указывающий, куда нужно записать следующее чётное число; right - указатель, который проходит по массиву и последовательно проверяет каждый эл-т на чётность. Вначале оба указателя указывают на первый эл-т. Проходим указателем right по массиву nums: - если число чётное: меняем его местами с числом на позиции left; - сдвигаем указатель left вправо. В конце возвращаем изменённый массив nums. Сложность O(n) - по времени (проходим по массиву длиной n) O(1) - по памяти (храним две переменные, меняем эл-ты in-place) Код class Solution: def sortArrayByParity(self, nums: List[int]) -> List[int]: left = 0 for right in range(len(nums)): if nums[right] % 2 == 0: nums[left], nums[right] = nums[right], nums[left] left += 1 return nums @algoses0,22%
  • 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 <= s.length <= 2000 s состоит только из строчных английских букв. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Задача помечена тегом "Dynamic Programming". Реализуем восходящее dp для проверки подстроки на палиндромность: заполняем таблицу от коротких подстрок к длинным, используя результаты для маленьких подстрок при вычислении больших. Запоминаем булево значение для каждой пары (i, j) и используем для получения ответа за O(1): - Создаём таблицу размером n * n, заполненную False, где dp[i][j] - ответ, является ли подстрока от индекса i до j палиндромом; - Заполняем таблицу вложенным циклом, двигаясь переменной i от конца строки к началу, а переменной j - от i вправо, строя подстроки по возрастанию длины. Таким образом, направление i и j гарантирует, что когда вычисляем dp[i][j], ответ для середины подстроки (dp[i+1][j-1]) уже готов. - Проверяем подстроку на палиндромность: Если крайние символы равны (s[i] == s[j]), то подстрока является палиндромом при выполнении хотя бы одного из двух условий: - подстрока состоит из одного или двух символов (j - i <= 1) => подстрока - палиндром; - внутренняя часть подстроки (dp[i+1][j-1]) - палиндром => вся подстрока - палиндром, так как крайние символы равны. Теперь имея результаты табличных вычислений, перебираем две точки разреза, которые делят строку на три части: s[0..i] + s[i+1..j] + s[j+1..n-1] i - индекс конца первого палиндрома j - индекс конца второго палиндрома Проходим внешним циклом i от 0, оставляя как минимум по одному символу для второго и третьего палиндромов: - если префикс (dp[0][i]) - палиндром, переходим ко внутреннему циклу от i+1 до предпоследнего индекса (оставляем хотя бы один символ для третьего палиндрома): - если второй отрезок - палиндром и третий отрезок - палиндром => можно разбить на 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 <= 1) or dp[i+1][j-1] for i in range(n - 2): if dp[0][i]: for j in range(i + 1, n - 1): if dp[i + 1][j] and dp[j + 1][n - 1]: return True return False @algoses0,14%