Задача с собеседования в 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
@algoses
Дана строка 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 состоит только из строчных английских букв.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
- Создаём таблицу размером 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) - по памяти (храним дп-таблицу)
Код
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
@algoses
🔥4❤2
Разбор контеста на стажировку в Яндекс за подписку!
Чтобы получить разбор:
➡️ Подпишитесь на нас в запрещенной странице тут
➡️ Поставьте «+» в комментариях под последней каруселью тут
➡️ После этого бот пришлёт вам материал в директ
Внутри будет разбор контеста и заданий, которые помогут подготовиться к отбору в Яндекс
Чтобы получить разбор:
Внутри будет разбор контеста и заданий, которые помогут подготовиться к отбору в Яндекс
Please open Telegram to view this post
VIEW IN TELEGRAM
😨1
Задача с собеседования в 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
@algoses
Дан массив 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
- если биты разные -> 1
Применяем XOR для "обнуления" повторяющихся значений из массива nums и полного набора чисел диапазона от 0 до n, используя свойство: a ^ a = 0. Отсутствующее число встретится только один раз и останется в результате по свойству a ^ 0 = a. Предварительная сортировка массива не требуется, так как a ^ b = b ^ a.
- проходим циклом по числам от 0 до n, накапливая XOR в res;
- проходим циклом по массиву nums, также накапливая XOR;
- возвращаем res.
Сложность
O(1) - по памяти (храним только одну переменную res)
Код
n = len(nums)
res = 0
for i in range(n + 1):
res ^= i
for num in nums:
res ^= num
return res
@algoses
❤12
C какими айтишницами стоит строить отношения, а какие - ред флаг? В новом ролике разобрал все бигтехи по фактам: Яндекс, ВК, Т-банк, Озон, Сбер. Смотрим! Смотрим! И не говорите потом, что не предупреждал!
https://www.youtube.com/shorts/d_lUVE5oo7A
https://www.youtube.com/shorts/d_lUVE5oo7A
YouTube
Я сходил на сотню свиданий с девушками из бигтехов и вот, что я понял..
#shorts #свидание #bigtech #айтишники #яндекс #тбанк #сбер #сбер #...
🤣16
Задача с собеседования в 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 <= num.length <= 1000
Строка num состоит только из цифр.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Проходим по строке окном фиксированного размера 3, проверяя на каждой позиции, состоит ли окно из трёх одинаковых символов. Выбираем максимальное из валидных окон путём лексикографического сравнения.
Инициализируем переменную res, в которой будем хранить максимальную найденную подстроку, как пустую строку (первая же "хорошая" подстрока обновит res).
Проходим по строке num до len(num) - 2, проверяя все возможные начальные позиции трёхсимвольной подстроки (последняя валидная позиция, с которой может начаться подстрока - len(num) - 3):
Если текущий эл-т идентичен двум последующим:
- обновляем res, если найденная подстрока из трёх символов (берём срез строки с индексами i, i+1 и i+2) больше текущего значения res.
Возвращаем значение res.
Сложность
O(n) - по времени (проходим n-2 итераций, где n = len(num))
O(1) - по памяти (храним только одну переменную res)
Код
class Solution:
def largestGoodInteger(self, num: str) -> str:
res = ""
for i in range(len(num) - 2):
if num[i] == num[i+1] == num[i+2]:
res = max(res, num[i:i+3])
return res
@algoses
Дана строка 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 <= num.length <= 1000
Строка num состоит только из цифр.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Инициализируем переменную res, в которой будем хранить максимальную найденную подстроку, как пустую строку (первая же "хорошая" подстрока обновит res).
Проходим по строке num до len(num) - 2, проверяя все возможные начальные позиции трёхсимвольной подстроки (последняя валидная позиция, с которой может начаться подстрока - len(num) - 3):
Если текущий эл-т идентичен двум последующим:
- обновляем res, если найденная подстрока из трёх символов (берём срез строки с индексами i, i+1 и i+2) больше текущего значения res.
Возвращаем значение res.
Сложность
O(1) - по памяти (храним только одну переменную res)
Код
def largestGoodInteger(self, num: str) -> str:
res = ""
for i in range(len(num) - 2):
if num[i] == num[i+1] == num[i+2]:
res = max(res, num[i:i+3])
return res
@algoses
❤3
Школьная сборная России третий год подряд стала абсолютным чемпионом на Международной олимпиаде по искусственному интеллекту IOAI-2026
Команда завоевала 8 медалей — 7 золотых и 1 бронзовую — и вновь доказала, что талант и знания открывают путь к большим победам.
Отбор проходил в СберУниверситете, а к турниру IOAI ребят готовили эксперты Альянса в сфере ИИ и Центрального университета.
В этом году конкуренция выросла кратно, но наши ребята снова оказались сильнейшими среди участников из более 100 стран в решении задач на самом фронтире технологий.
Поздравляем победителей!
Команда завоевала 8 медалей — 7 золотых и 1 бронзовую — и вновь доказала, что талант и знания открывают путь к большим победам.
Отбор проходил в СберУниверситете, а к турниру IOAI ребят готовили эксперты Альянса в сфере ИИ и Центрального университета.
В этом году конкуренция выросла кратно, но наши ребята снова оказались сильнейшими среди участников из более 100 стран в решении задач на самом фронтире технологий.
Поздравляем победителей!
❤14❤🔥3🔥3👏2
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Осенний найм уже на старте!
Осенью запускаются стажировки, открываются вакансии и поэтому август — лучшее время для подготовки: понять, что спрашивают на отборах, оценить свой уровень и закрыть пробелы до начала учебы!
Поэтому не упусти финальную распродажу курсов «СТАРТ» — любой курс всего за 6 490 ₽
➡ Аналитика
➡ Алгоритмы
➡ Backend
➡ Machine Learning
Почему сейчас лучшее время присоединиться:
Выгодное комбо:
➡️ Алгоритмы + любой курс всего за 9 990 ₽⬅️
Берите Backend, ML или Аналитику и параллельно ботайте алгоритмы — они встречаются везде, без хороших алгосов не пройти отбор в хорошую компанию.
🔊 Распродажа только 8-9 августа.
Подробную программу смотрите на сайте
📌 Для вопросов и записи на курс напишите менеджеру
Осенью запускаются стажировки, открываются вакансии и поэтому август — лучшее время для подготовки: понять, что спрашивают на отборах, оценить свой уровень и закрыть пробелы до начала учебы!
Поэтому не упусти финальную распродажу курсов «СТАРТ» — любой курс всего за 6 490 ₽
Почему сейчас лучшее время присоединиться:
✔️ Гибкий старт: все лекции по техническим темам уже выложены и доступны — проходите в своём темпе, а куратор остается на связи и проверит дз и проекты.
✔️ Карьерный блок: онлайн-семинарам по софтам. Напишете резюме, которое пройдет скрининг, даже если нет опыта, отработаете самопрезенатицию, пройдёте mock-собеседование с обратной связью.
✔️ Закрытый банк вопросов с реальных интервью Яндекса, Т-Банка, Ozon, WB, Авито и других топ-компаний.
✔️ Разбор текущего отбора на стажировок Яндекса.
✔️ Реферальная рекомендация в бигтех после успешной защиты пет-проекта.
Выгодное комбо:
Берите Backend, ML или Аналитику и параллельно ботайте алгоритмы — они встречаются везде, без хороших алгосов не пройти отбор в хорошую компанию.
Подробную программу смотрите на сайте
Please open Telegram to view this post
VIEW IN TELEGRAM
❤4🔥1
Нужны ли алгоритмы сейчас, в эпоху ИИ, на собесах
До 2025 года из каждого утюга вы слышали про эти "алгособесы". Любой отбор в школы, на стажировки или штатные позиции обязательно выглядел как школьная олимпиада по программированию. А основная подготовка к выходу на работу заключалась в нарешивании Литкода.
Почему так происходило
Оценить весь огромный стек технологий за часовое собеседование - нереально. Почти любая рабочая задача в бигтехе, которая проверяет твой реальный уровень, занимает минимум неделю работы. Очевидно, в часовой формат такое не укладывается, поэтому для оценки кандидата пошли по иному пути:
1. рассказ про опыт и свои харды;
2. решение брейн-тизеров и алгоритмических задач.
По первому пункту кандидат, конечно, может обмануть, если хорошо проработает легенду. Но обычно таких ребят быстро ловят - им не хватает скиллов, чтобы придумать качественную и непротиворечивую историю. А вот вторым пунктом выступили алгоритмы, которые идеально подходят сразу для аналитики, ML и бэкенда. Во всех этих направлениях так или иначе присутствует написание кода, а алгоритмический аппарат дает незаменимый навык быстро рефакторить код и видеть его структуру.
А что сейчас
Некоторые компании отказались от отдельных алгособесов, но оставили задачки в других секциях (livecoding). Однако в крупных бигтехах алгосекция все так же существует. Более того, в зарубежных вакансиях алгоритмические секции сейчас, наоборот, снова в тренде.
Чем обусловлен небольшой спад тренда? Компании перегрели кандидатов: на секциях стали спрашивать слишком простые задачки, которые при хорошей подготовке никак не отражают объективно твое умение строить алгоритмы. По сути, их можно просто "зарешать" количеством, и на собесе ты решишь задачу не потому, что придумал решение, а потому что встречал похожую идею раньше.
Но альтернативу алгосам так и не придумали. Давать математический брейн-тизер бэкендеру странно, а усложнить алгозадачу до уровня, где нельзя натренировать типовые паттерны - перебор, ведь это лишь метод проверки мышления, спрашивать вкатуна систем дизайн- ту мач.
Главный вывод.
Алгоритмический аппарат в эпоху LLM станет как никогда актуальным. Ваша задача на работе будет сводиться к тому, чтобы быстро валидировать код, написанный нейросеткой. Это значит, что вам нужно моментально разбираться в чужом коде и видеть узкие места. Именно такие навыки и тренируют алгоритмические задачки.
Поэтому не стоит надеяться, что алгосы пропадут с рынка. В будущем это будет наиболее актуальный и надежный инструмент проверки твоего инженерного мышления.
Что с этим делать и как подготовиться
Если вы готовитесь к собеседованиям, важно понимать: алгоритмы - это не про запоминание 500 задач, а про тренировку шаблонов мышления. Чтобы решать задачи за 20 минут, нужно не заучивать код, а видеть структуру задачи сходу.
Но просто читать про это недостаточно. Чтобы выйти на алгособес уверенно, нужна системная практика с разбором реальных кейсов.
Если хотите оставаться в тренде IT-рынка и его жестких требований, советую наши курсы «Старт». У нас есть отдельный курс по алгоритмам, разбор реальных задач с собеседований в топ-компаниях и подходы, которые учат именно думать, а не зубрить.
Специально для подписчиков канала мы продлили финальные скидки на обучение на 24 часа. Если давно хотели прокачать свой алгоритмический аппарат до уровня топ-компаний, сейчас лучший момент. Это последний шанс взять комбо: алгоритмы + любой курс по специальности по хорошей цене и уже осенью залутать оффер!
➡️ Записаться
Подписаться: @algoses
До 2025 года из каждого утюга вы слышали про эти "алгособесы". Любой отбор в школы, на стажировки или штатные позиции обязательно выглядел как школьная олимпиада по программированию. А основная подготовка к выходу на работу заключалась в нарешивании Литкода.
Почему так происходило
Оценить весь огромный стек технологий за часовое собеседование - нереально. Почти любая рабочая задача в бигтехе, которая проверяет твой реальный уровень, занимает минимум неделю работы. Очевидно, в часовой формат такое не укладывается, поэтому для оценки кандидата пошли по иному пути:
1. рассказ про опыт и свои харды;
2. решение брейн-тизеров и алгоритмических задач.
По первому пункту кандидат, конечно, может обмануть, если хорошо проработает легенду. Но обычно таких ребят быстро ловят - им не хватает скиллов, чтобы придумать качественную и непротиворечивую историю. А вот вторым пунктом выступили алгоритмы, которые идеально подходят сразу для аналитики, ML и бэкенда. Во всех этих направлениях так или иначе присутствует написание кода, а алгоритмический аппарат дает незаменимый навык быстро рефакторить код и видеть его структуру.
А что сейчас
Некоторые компании отказались от отдельных алгособесов, но оставили задачки в других секциях (livecoding). Однако в крупных бигтехах алгосекция все так же существует. Более того, в зарубежных вакансиях алгоритмические секции сейчас, наоборот, снова в тренде.
Чем обусловлен небольшой спад тренда? Компании перегрели кандидатов: на секциях стали спрашивать слишком простые задачки, которые при хорошей подготовке никак не отражают объективно твое умение строить алгоритмы. По сути, их можно просто "зарешать" количеством, и на собесе ты решишь задачу не потому, что придумал решение, а потому что встречал похожую идею раньше.
Но альтернативу алгосам так и не придумали. Давать математический брейн-тизер бэкендеру странно, а усложнить алгозадачу до уровня, где нельзя натренировать типовые паттерны - перебор, ведь это лишь метод проверки мышления, спрашивать вкатуна систем дизайн- ту мач.
Главный вывод.
Алгоритмический аппарат в эпоху LLM станет как никогда актуальным. Ваша задача на работе будет сводиться к тому, чтобы быстро валидировать код, написанный нейросеткой. Это значит, что вам нужно моментально разбираться в чужом коде и видеть узкие места. Именно такие навыки и тренируют алгоритмические задачки.
Поэтому не стоит надеяться, что алгосы пропадут с рынка. В будущем это будет наиболее актуальный и надежный инструмент проверки твоего инженерного мышления.
Что с этим делать и как подготовиться
Если вы готовитесь к собеседованиям, важно понимать: алгоритмы - это не про запоминание 500 задач, а про тренировку шаблонов мышления. Чтобы решать задачи за 20 минут, нужно не заучивать код, а видеть структуру задачи сходу.
Но просто читать про это недостаточно. Чтобы выйти на алгособес уверенно, нужна системная практика с разбором реальных кейсов.
Если хотите оставаться в тренде IT-рынка и его жестких требований, советую наши курсы «Старт». У нас есть отдельный курс по алгоритмам, разбор реальных задач с собеседований в топ-компаниях и подходы, которые учат именно думать, а не зубрить.
Специально для подписчиков канала мы продлили финальные скидки на обучение на 24 часа. Если давно хотели прокачать свой алгоритмический аппарат до уровня топ-компаний, сейчас лучший момент. Это последний шанс взять комбо: алгоритмы + любой курс по специальности по хорошей цене и уже осенью залутать оффер!
Подписаться: @algoses
Please open Telegram to view this post
VIEW IN TELEGRAM
❤2
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
У России три пути: 18+, ***** и IT
И кажется, у нас случился переход между карьерными треками…
Нам неважно, какой у человека бэкграунд и чем он занимался раньше. Важно, куда он хочет прийти и что готов для этого делать.
Наша студентка, Алина, решила кардинально сменить сферу, пришла на «СТАРТ» и теперь готовится к своей новой цели — получить оффер в Яндекс.
Можно следить за успехами и учиться вместе с Алиной. На наши курсы старт, идут финальные 4 часа скидки.
➡️ Записаться
И кажется, у нас случился переход между карьерными треками…
Нам неважно, какой у человека бэкграунд и чем он занимался раньше. Важно, куда он хочет прийти и что готов для этого делать.
Наша студентка, Алина, решила кардинально сменить сферу, пришла на «СТАРТ» и теперь готовится к своей новой цели — получить оффер в Яндекс.
Можно следить за успехами и учиться вместе с Алиной. На наши курсы старт, идут финальные 4 часа скидки.
Please open Telegram to view this post
VIEW IN TELEGRAM
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
This media is not supported in your browser
VIEW IN TELEGRAM
🍌17🤨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 <= 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]
@algoses
Дан целочисленный массив 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 встретится два раза, только два числа встретятся один раз.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
- если биты одинаковые -> 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(1) - по памяти (храним целочисленные переменные xor, diff_bit, a, b)
Код
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for n in nums:
xor ^= n
diff_bit = 1
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]
@algoses
🔥11
Как разогнать карьеру до уровня СЕО? 🏎
С помощью программы «Мини-СЕО»: здесь можно попасть в команду топ-менеджера Т-Банка и получить опыт, который нельзя нагуглить.
У каждого участника будет свое направление, где он сможет:
— развивать сегмент автолюбителей и заниматься региональной экспансией Т-Банка с Жорой Сукасяном;
— вести стратегический план развития 3P, развивать AI-продукты и искать, где AI может упростить работу команды, c Денисом Коротовым;
— разрабатывать эффективные методологии для оценки влияния продукта на экосистему с Владимиром Любимовым;
— исследовать экосистемы и находить наиболее перспективные точки роста с Максимом Безруковым;
— участвовать в создании B2B-маркетплейса c Владимиром Абазовым.
Программа длится шесть месяцев. Никакой скучной теории, работаем над стратегическими проектами по 40 часов в неделю.
Подойдет студентам и джуниор-специалистам, которые уже умеют в математику и аналитику.
Подать заявку можно до 25 сентября
С помощью программы «Мини-СЕО»: здесь можно попасть в команду топ-менеджера Т-Банка и получить опыт, который нельзя нагуглить.
У каждого участника будет свое направление, где он сможет:
— развивать сегмент автолюбителей и заниматься региональной экспансией Т-Банка с Жорой Сукасяном;
— вести стратегический план развития 3P, развивать AI-продукты и искать, где AI может упростить работу команды, c Денисом Коротовым;
— разрабатывать эффективные методологии для оценки влияния продукта на экосистему с Владимиром Любимовым;
— исследовать экосистемы и находить наиболее перспективные точки роста с Максимом Безруковым;
— участвовать в создании B2B-маркетплейса c Владимиром Абазовым.
Программа длится шесть месяцев. Никакой скучной теории, работаем над стратегическими проектами по 40 часов в неделю.
Подойдет студентам и джуниор-специалистам, которые уже умеют в математику и аналитику.
Подать заявку можно до 25 сентября
Задача с собеседования в 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
@algoses
Дан целочисленный массив 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
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Свойство монотонно: если можно составить 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(1) - по памяти (храним некоторое кол-во переменных)
Код
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
@algoses
❤2🔥2🤯2