Задача с собеседования Яндекс
Задача
Дана последовательность a и последовательность a'. Вам требуется найти такие l, r, что отсортировав подмассив a[l:r+1], можно получить массив a'. Если ответов несколько, выберите отрезок наибольшей длины. По условию такая операция всегда существует.
Чат алгоритмистов
Решение
Найдем первое отличающееся вхождение, позицию i: a[i]!= a'[i](то есть самое левое) и найдем последнее (самое правое). Далее расширим эти границы: до тех пор, пока левее от левой границы в приведенном массиве a стоит меньше или равный a'[l-1]<= a'[l], будем двигать его влево. Аналогично и с правым указателем, расширим его вправо.
Код
l,r=-1,-1
for i in range(n):
if a[i]!=aa[i]:
r=i
if l==-1:
l=i
while l>0 and aa[l-1]<=aa[l]:
l-=1
while r<n-1 and aa[r+1]>=aa[r]:
r+=1
print(l+1,r+1)
@algoses
Задача
Дана последовательность a и последовательность a'. Вам требуется найти такие l, r, что отсортировав подмассив a[l:r+1], можно получить массив a'. Если ответов несколько, выберите отрезок наибольшей длины. По условию такая операция всегда существует.
Чат алгоритмистов
Решение
Код
for i in range(n):
if a[i]!=aa[i]:
r=i
if l==-1:
l=i
while l>0 and aa[l-1]<=aa[l]:
l-=1
while r<n-1 and aa[r+1]>=aa[r]:
r+=1
print(l+1,r+1)
@algoses
❤14🔥1
Магистратура — это 2 года жизни и серьезные вложения. Как не ошибиться с выбором?
Приходите на день открытых дверей ИТ-магистратуры Центрального университета — разберем все важные вопросы, которые помогут принять правильное решение.
О чем будем говорить:
→ Как создаются программы магистратуры в ЦУ, что такое продуктовый подход в высшем образовании и как это делает выпускников реально востребованными на рынке
→ Как университет помогает студентам строить карьеру: от менторства до трудоустройства в топовые компании
→ Какие направления есть в ЦУ и как выбрать то, что приведет к вашим карьерным целям
→ Реальные истории студентов: как они поступали, учились и куда пошли работать
Спикеры — практики с опытом в Google, Яндексе, Т-Банке и Visa, которые сейчас отвечают за образовательный опыт студентов ЦУ.
Когда:
Онлайн 13 ноября с 19:30 до 21:00 (трансляции в VK и YouTube).
Очно 18 ноября с 19:30 до 21:00 (в Москве с экскурсией по кампусу ЦУ).
Регистрируйся по ссылке!
Реклама. АНО ВО "Центральный университет", ИНН 7743418023, erid: 2Ranynxo6A5
Приходите на день открытых дверей ИТ-магистратуры Центрального университета — разберем все важные вопросы, которые помогут принять правильное решение.
О чем будем говорить:
→ Как создаются программы магистратуры в ЦУ, что такое продуктовый подход в высшем образовании и как это делает выпускников реально востребованными на рынке
→ Как университет помогает студентам строить карьеру: от менторства до трудоустройства в топовые компании
→ Какие направления есть в ЦУ и как выбрать то, что приведет к вашим карьерным целям
→ Реальные истории студентов: как они поступали, учились и куда пошли работать
Спикеры — практики с опытом в Google, Яндексе, Т-Банке и Visa, которые сейчас отвечают за образовательный опыт студентов ЦУ.
Когда:
Онлайн 13 ноября с 19:30 до 21:00 (трансляции в VK и YouTube).
Очно 18 ноября с 19:30 до 21:00 (в Москве с экскурсией по кампусу ЦУ).
Регистрируйся по ссылке!
Реклама. АНО ВО "Центральный университет", ИНН 7743418023, erid: 2Ranynxo6A5
💊7❤2
Когда: 25–28 ноября
Формат: онлайн + финал на площадке
Участвуй, если ты:
Выбери свой кейс:
✴️ VibeCode Jam: собеседование будущего. Создай ИИ-платформу для прохождения технических собеседований с виртуальным интервьюером.✴️ Self-Deploy: CI/CD без DevOps. Автоматизируй генерацию CI/CD пайплайнов по анализу структуры Git-репозитория.
Почему стоит участвовать:
Регистрация открыта!
Реклама.
О рекламодателе.
Please open Telegram to view this post
VIEW IN TELEGRAM
❤3
Задача с собеса в Авито
Условие задачи
Дано бинарное поисковое дерево (BST) и число k. Нужно вернуть значение k-го по величине элемента в этом дереве (нумерация с 1).
для любой вершины: все значения в левом поддереве меньше её значения; все значения в правом поддереве больше её значения.
Решение
Очень важное свойство BST: если обойти дерево в порядке
лево -> корень -> право (симметричный / inorder обход),
то значения вершин будут посещаться в отсортированном по возрастанию порядке.
Значит, k-й посещённый элемент при таком обходе — это и есть k-й по величине.
Делаем итеративный inorder-обход через стек:
1. Идём по указателю node максимально влево, по пути кладём все вершины в стек.
2. Когда упёрлись в None, достаём вершину из стека — это следующий по возрастанию элемент.
3. Уменьшаем k. Если k стало 0 — возвращаем значение этой вершины.
4. Переходим в правого ребёнка и повторяем.
Так мы не храним все элементы, а только путь в стеке.
Сложность:
по времени: O(h + k), где h — высота дерева (в худшем O(n), для сбалансированного O(log n)), по памяти: O(h) на стек
Код:
class Solution:
def kthSmallest(self, root: Optional['TreeNode'], k: int) -> int:
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right
@algoses
Условие задачи
Дано бинарное поисковое дерево (BST) и число k. Нужно вернуть значение k-го по величине элемента в этом дереве (нумерация с 1).
для любой вершины: все значения в левом поддереве меньше её значения; все значения в правом поддереве больше её значения.
Решение
лево -> корень -> право (симметричный / inorder обход),
то значения вершин будут посещаться в отсортированном по возрастанию порядке.
Значит, k-й посещённый элемент при таком обходе — это и есть k-й по величине.
Делаем итеративный inorder-обход через стек:
1. Идём по указателю node максимально влево, по пути кладём все вершины в стек.
2. Когда упёрлись в None, достаём вершину из стека — это следующий по возрастанию элемент.
3. Уменьшаем k. Если k стало 0 — возвращаем значение этой вершины.
4. Переходим в правого ребёнка и повторяем.
Так мы не храним все элементы, а только путь в стеке.
Сложность:
Код:
class Solution:
def kthSmallest(self, root: Optional['TreeNode'], k: int) -> int:
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right
@algoses
🔥11❤3🗿1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Поступашки продолжают набор на новую линейку карьерных курсов 🎉
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
➡️ SQL и базы данных
➡️ анализ временных рядов
➡️ обучение с подкреплением
Все курсы стартуют 29.11. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
📊 Цена 10'000р 6'990р! Хочешь купить несколько курсов сразу? Дадим хорошую скидку!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
Все курсы стартуют 29.11. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено
Please open Telegram to view this post
VIEW IN TELEGRAM
😁4❤1
Разбор на стажировку Яндекса
Финальные 6 часов скидок на наши курсы подходят к концу. В честь этого выкладываем разбор актуального контеста в Яндекс:
— Бэкенд
— Аналитика
— ML & DS
Обязательно пересылайте такую годноту своим друзьям и одногруппникам в чаты. Больше подписчиков — больше разборов.
@postypashki_old
Финальные 6 часов скидок на наши курсы подходят к концу. В честь этого выкладываем разбор актуального контеста в Яндекс:
— Бэкенд
— Аналитика
— ML & DS
Обязательно пересылайте такую годноту своим друзьям и одногруппникам в чаты. Больше подписчиков — больше разборов.
@postypashki_old
😁3❤2🔥1🙉1
Задача с собеседования в Яндекс
Дан отсортированный в порядке возрастания массив nums, состоящий из уникальных целых чисел.
Известно, что диапазон [a, b] представляет собой множество всех целых чисел от a до b включительно.
Вам необходимо вернуть наименьший отсортированный список диапазонов, в котором каждый элемент массива находится в одном из диапазонов. И нет такого числа, которое есть в диапазоне, но отсутствует в изначальном массиве nums.
Пример:
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Чат алгоритмистов
Решение
Проходим внешним циклом по всем элементам массива.
start - начало текущего диапазона. С помощью внутреннего цикла ищем окончание диапазона (проверяем наличие следующего эл-та и то, что числа идут подряд, если оба условия верны: обновляем i).
Если начало диапазона не равняется текущему значению nums[i]: выводим (строковый) диапазон, состоящий из более чем одного числа. Иначе: диапазон состоит из одного числа. Переходим к следующему эл-ту (за пределами выведенного диапазона).
Сложность
O(n) - по времени
O(n) - по памяти
Код
def summaryRanges(self, nums: List[int]) -> List[str]:
result = []
i = 0
while i < len(nums):
start = nums[i]
while i < len(nums) - 1 and nums[i] + 1 == nums[i + 1]:
i+= 1
if start != nums[i]:
result.append(str(start) + "->" + str(nums[i]))
else:
result.append(str(nums[i]))
i += 1
return result
@algoses
Дан отсортированный в порядке возрастания массив nums, состоящий из уникальных целых чисел.
Известно, что диапазон [a, b] представляет собой множество всех целых чисел от a до b включительно.
Вам необходимо вернуть наименьший отсортированный список диапазонов, в котором каждый элемент массива находится в одном из диапазонов. И нет такого числа, которое есть в диапазоне, но отсутствует в изначальном массиве nums.
Пример:
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Чат алгоритмистов
Решение
start - начало текущего диапазона. С помощью внутреннего цикла ищем окончание диапазона (проверяем наличие следующего эл-та и то, что числа идут подряд, если оба условия верны: обновляем i).
Если начало диапазона не равняется текущему значению nums[i]: выводим (строковый) диапазон, состоящий из более чем одного числа. Иначе: диапазон состоит из одного числа. Переходим к следующему эл-ту (за пределами выведенного диапазона).
Сложность
O(n) - по времени
O(n) - по памяти
Код
result = []
i = 0
while i < len(nums):
start = nums[i]
while i < len(nums) - 1 and nums[i] + 1 == nums[i + 1]:
i+= 1
if start != nums[i]:
result.append(str(start) + "->" + str(nums[i]))
else:
result.append(str(nums[i]))
i += 1
return result
@algoses
🔥4🥱4❤2
Состоялся первый студенческий хакатон для мессенджера МАХ — участники привезли на очный финал в Москву больше 50 сервисов, и жюри выбрало девять лучших. В треке «Цифровизация» выиграла команда SUPERVIBECODING с сервисом «Цифровой кампус», в социальном треке — Smolensk Dynamics, разработавшая бота для анализа состава продуктов питания, а в «Эффективности» сильнейшими стали ребята из Explain с AI-календарём.
Хакатон получился масштабным: заявки отправили более 2,7 тысяч студентов, до финала дошли 56 команд, из которых были выбраны победители. В VK Education отмечают, что участники продемонстрировали отличное понимание реальных потребностей пользователей и вузов и создали актуальные и востребованные мини-приложения и чат-боты для мессенджера МАХ.
@algoses
Хакатон получился масштабным: заявки отправили более 2,7 тысяч студентов, до финала дошли 56 команд, из которых были выбраны победители. В VK Education отмечают, что участники продемонстрировали отличное понимание реальных потребностей пользователей и вузов и создали актуальные и востребованные мини-приложения и чат-боты для мессенджера МАХ.
@algoses
🤣87💊7🤨6❤3🤯2
Задача с собеседования в Яндекс
Дан массив строк strs. Найдите анаграммы и сгруппируйте их вместе.
Группы анаграмм можно вывести в любом порядке.
Пример:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Чат алгоритмистов
Решение
Идея: хэш-таблица, где ключ - кортеж из 26 эл-ов (каждое число - количество вхождений определённой буквы в слово), а значение - список слов, имеющих одинаковую частоту букв (анаграммы).
Проходим по каждому слову в массиве strs и создаём массив из 26 нулей (кол-во букв алфавита). Для каждого символа в слове вычисляем его индекс (соответствует позиции буквы в алфавите) и увеличиваем счётчик.
Далее преобразовываем список в кортеж, чтобы сделать его ключом словаря.
Проверяем, есть ли ключ в словаре. Если да: добавляем слово в существующий список анаграмм по этому ключу, если нет: создаём новую группу анаграмм.
Выводим двумерный список, состоящий из сгруппированных значений нашего словаря с анаграммами.
Сложность
O(n × k) - по времени
O(n × k) - по памяти
Код
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagrams = {}
for word in strs:
letter_counts = [0] * 26
for char in word:
letter_counts[ord(char) - ord("a")] += 1
key = tuple(letter_counts)
if key not in anagrams:
anagrams[key] = [word]
else:
anagrams[key].append(word)
return list(anagrams.values())
@algoses
Дан массив строк strs. Найдите анаграммы и сгруппируйте их вместе.
Группы анаграмм можно вывести в любом порядке.
Пример:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Чат алгоритмистов
Решение
Проходим по каждому слову в массиве strs и создаём массив из 26 нулей (кол-во букв алфавита). Для каждого символа в слове вычисляем его индекс (соответствует позиции буквы в алфавите) и увеличиваем счётчик.
Далее преобразовываем список в кортеж, чтобы сделать его ключом словаря.
Проверяем, есть ли ключ в словаре. Если да: добавляем слово в существующий список анаграмм по этому ключу, если нет: создаём новую группу анаграмм.
Выводим двумерный список, состоящий из сгруппированных значений нашего словаря с анаграммами.
Сложность
O(n × k) - по времени
O(n × k) - по памяти
Код
anagrams = {}
for word in strs:
letter_counts = [0] * 26
for char in word:
letter_counts[ord(char) - ord("a")] += 1
key = tuple(letter_counts)
if key not in anagrams:
anagrams[key] = [word]
else:
anagrams[key].append(word)
return list(anagrams.values())
@algoses
🔥8❤6
Гранты на обучение в Центральном университете
Получи грант на 4 года до 3 480 000 ₽ на учебу в бакалавриате Центрального университета.
Гранты покрывают до 100% стоимости обучения. Сумма гранта не уменьшается, а может только увеличиться за дополнительные достижения и успехи в учебе.
Конкурс состоит из двух этапов: тестирование и бизнес-игра. Фаст-трек: поступи по ускоренному пути, если у тебя уже есть достижения.
Грант открывает доступ к мероприятиям университета: стипендиальная программа, пробные ЕГЭ и другие.
Для выпускников 10–11-х классов и СПО.
Участвуй в конкурсе уже сейчас!
Получи грант на 4 года до 3 480 000 ₽ на учебу в бакалавриате Центрального университета.
Гранты покрывают до 100% стоимости обучения. Сумма гранта не уменьшается, а может только увеличиться за дополнительные достижения и успехи в учебе.
Конкурс состоит из двух этапов: тестирование и бизнес-игра. Фаст-трек: поступи по ускоренному пути, если у тебя уже есть достижения.
Грант открывает доступ к мероприятиям университета: стипендиальная программа, пробные ЕГЭ и другие.
Для выпускников 10–11-х классов и СПО.
Участвуй в конкурсе уже сейчас!
❤4💊2
Задача с собеседования в Zalando
В лимонадном киоске один стакан лимонада стоит 5 долларов. Покупатели стоят в очереди и приобретают лимонад в порядке, указанном в массиве bills. Каждый клиент покупает только один лимонад и платит одной из следующих купюр: 5, 10 или 20 долларов.
Вам необходимо дать правильную сдачу каждому клиенту, чтобы итоговая сумма, которую он заплатил, составила ровно 5 долларов. Имейте в виду, что вначале у вас нет денег для сдачи.
Задан целочисленный массив bills, где bills[i] - это купюра, которой расплачивается i-й любитель лимонада.
Верните true, если можете дать правильную сдачу каждому клиенту, или false в противном случае.
Пример 1:
Input: bills = [5,5,5,10,20]
Output: true
Пример 2:
Input: bills = [5,5,10,10,20]
Output: false
Чат алгоритмистов
Решение
Создаём переменные для хранения купюр, переменная twenty нам не нужна, потому что не будет использоваться в качестве сдачи.
Проходим по каждому элементу в массиве и обрабатываем платежи, увеличивая (принимая купюру) и/или уменьшая (при необходимости сдачи) счётчик переменной.
Проверяем возможность дать клиенту сдачу при каждом платеже, применяя жадный алгоритм. Ищем наиболее оптимальное решение на каждом шаге:
При оплате 10$ - выбора нет, отдаём купюру номиналом 5, и это наиболее оптимально в данном случае. Но если клиент платит 20$, предпочитаем дать сдачу с использованием купюры наибольшего номинала (10+5, а не 5+5+5), так как 5$ более универсальны и чаще могут понадобиться для размена.
Сложность
O(n) - по времени
O(1) - по памяти
Код
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five = 0
ten = 0
for b in bills:
if b == 5:
five += 1
elif b == 10:
if five < 1:
return False
else:
five -= 1
ten += 1
else:
if five >= 1 and ten >= 1:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True
@algoses
В лимонадном киоске один стакан лимонада стоит 5 долларов. Покупатели стоят в очереди и приобретают лимонад в порядке, указанном в массиве bills. Каждый клиент покупает только один лимонад и платит одной из следующих купюр: 5, 10 или 20 долларов.
Вам необходимо дать правильную сдачу каждому клиенту, чтобы итоговая сумма, которую он заплатил, составила ровно 5 долларов. Имейте в виду, что вначале у вас нет денег для сдачи.
Задан целочисленный массив bills, где bills[i] - это купюра, которой расплачивается i-й любитель лимонада.
Верните true, если можете дать правильную сдачу каждому клиенту, или false в противном случае.
Пример 1:
Input: bills = [5,5,5,10,20]
Output: true
Пример 2:
Input: bills = [5,5,10,10,20]
Output: false
Чат алгоритмистов
Решение
Проходим по каждому элементу в массиве и обрабатываем платежи, увеличивая (принимая купюру) и/или уменьшая (при необходимости сдачи) счётчик переменной.
Проверяем возможность дать клиенту сдачу при каждом платеже, применяя жадный алгоритм. Ищем наиболее оптимальное решение на каждом шаге:
При оплате 10$ - выбора нет, отдаём купюру номиналом 5, и это наиболее оптимально в данном случае. Но если клиент платит 20$, предпочитаем дать сдачу с использованием купюры наибольшего номинала (10+5, а не 5+5+5), так как 5$ более универсальны и чаще могут понадобиться для размена.
O(n) - по времени
O(1) - по памяти
Код
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five = 0
ten = 0
for b in bills:
if b == 5:
five += 1
elif b == 10:
if five < 1:
return False
else:
five -= 1
ten += 1
else:
if five >= 1 and ten >= 1:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True
@algoses
❤6🔥4
Задача с собеседования в Zalando
Дан массив интервалов, где intervals[i] = [starti, endi]. Необходимо объединить все пересекающиеся интервалы, а затем вернуть массив, состоящий из непересекающихся интервалов, которые покрывают все интервалы из входных данных.
Пример 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Пример 2:
Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Чат алгоритмистов
Решение
1. Сортируем интервалы по началу, это гарантирует: если текущий интервал не пересекается с последним, то он не может пересекаться с каким-либо более ранним, т.к. все предыдущие интервалы имеют начало не больше, чем у последнего, и если последний заканчивается до начала текущего, то все предыдущие тем более закончились раньше. Это позволяет решить задачу за один проход.
2. Проходим по каждому отсортированному интервалу в массиве:
- добавляем новый интервал в список, если это первый интервал в списке ИЛИ если конец последнего интервала меньше начала текущего
(в merged лежит [1,6], а текущий интервал [8,10], 6 < 8 => интервалы не пересекаются => добавляем [8,10] как новый интервал).
- иначе объединяем его с последним интервалом и обновляем конец
(в merged лежит [1,3], текущий интервал = [2,6], они пересекающиеся, так как 3 ≥ 2. Обновляем конец объединённого интервала: max(3, 6) = 6, то есть [1,6]).
Сложность
O(n log n) - по времени
O(n) - по памяти
Код
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda interval: interval[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
@algoses
Дан массив интервалов, где intervals[i] = [starti, endi]. Необходимо объединить все пересекающиеся интервалы, а затем вернуть массив, состоящий из непересекающихся интервалов, которые покрывают все интервалы из входных данных.
Пример 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Пример 2:
Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Чат алгоритмистов
Решение
2. Проходим по каждому отсортированному интервалу в массиве:
- добавляем новый интервал в список, если это первый интервал в списке ИЛИ если конец последнего интервала меньше начала текущего
(в merged лежит [1,6], а текущий интервал [8,10], 6 < 8 => интервалы не пересекаются => добавляем [8,10] как новый интервал).
- иначе объединяем его с последним интервалом и обновляем конец
(в merged лежит [1,3], текущий интервал = [2,6], они пересекающиеся, так как 3 ≥ 2. Обновляем конец объединённого интервала: max(3, 6) = 6, то есть [1,6]).
Сложность
O(n) - по памяти
Код
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda interval: interval[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
@algoses
❤6🔥2
Media is too big
VIEW IN TELEGRAM
2 недели, 2 бигтеха, 95 сильнейших студентов AI360⚡
С 17 по 28 ноября второкурсники из МФТИ, НИУ ВШЭ, ИТМО и Университета Иннополиса работали в офисах Сбера и Яндекса под менторством тех, кто создаёт ИИ-продукты прямо сейчас.
Разбирали научные статьи по AI вместе с экспертами, работали над проектами в командах и защищали результаты на постерной сессии перед топ-менеджерами. Успели даже попасть на AI Journey 2025 и пообщаться с Германом Грефом 💚
Лучший способ прокачаться в ИИ — учиться там, где его создают 😎
AI360 — это про то, как компании растят новое поколение AI-специалистов вместе с лучшими вузами страны 🔝
Хочешь не пропустить следующий отбор на AI360? Подписывайся на нас — там будут все анонсы, лайфхаки по подготовке и истории студентов 🚀
С 17 по 28 ноября второкурсники из МФТИ, НИУ ВШЭ, ИТМО и Университета Иннополиса работали в офисах Сбера и Яндекса под менторством тех, кто создаёт ИИ-продукты прямо сейчас.
Разбирали научные статьи по AI вместе с экспертами, работали над проектами в командах и защищали результаты на постерной сессии перед топ-менеджерами. Успели даже попасть на AI Journey 2025 и пообщаться с Германом Грефом 💚
Лучший способ прокачаться в ИИ — учиться там, где его создают 😎
AI360 — это про то, как компании растят новое поколение AI-специалистов вместе с лучшими вузами страны 🔝
Хочешь не пропустить следующий отбор на AI360? Подписывайся на нас — там будут все анонсы, лайфхаки по подготовке и истории студентов 🚀
❤7🔥3😎2
Т-Образование запускает курс по алгоритмам и структурам данных
Он поможет подготовиться к техническим интервью и уверенно решать алгоритмические задачи — один из ключевых этапов отбора в ИТ-компании.
В программе:
— еженедельные лекции с разбором новых тем и практикой;
— языки курса — C++, Perl, Java, C#, Python, Go, Scala, Kotlin и Swift;
— общий чат студентов и преподавателей по решению задач.
Курс ведет инженер мобильного приложения Т-Банка, преподаватель Т-Поколения и интервьюер алгоритмической секции.
Занятия проходят онлайн, а в конце у участников будет сертификат в портфолио.
Успейте подать заявку до 23 января
Он поможет подготовиться к техническим интервью и уверенно решать алгоритмические задачи — один из ключевых этапов отбора в ИТ-компании.
В программе:
— еженедельные лекции с разбором новых тем и практикой;
— языки курса — C++, Perl, Java, C#, Python, Go, Scala, Kotlin и Swift;
— общий чат студентов и преподавателей по решению задач.
Курс ведет инженер мобильного приложения Т-Банка, преподаватель Т-Поколения и интервьюер алгоритмической секции.
Занятия проходят онлайн, а в конце у участников будет сертификат в портфолио.
Успейте подать заявку до 23 января
🔥4❤🔥2❤1
Задача с собеседования в Zalando
Даны три целых числа: x, y и z.
У вас есть x строк, равных "AA", y строк, равных "BB", и z строк, равных "AB". Вы хотите выбрать некоторое (возможно, все или ни одной) количество из этих строк и объединить их в некотором порядке, чтобы сформировать новую строку. Эта новая строка не должна содержать подстрок "AAA" или "BBB".
Известно, что подстрока - это непрерывная непустая последовательность символов внутри строки.
Верните максимально возможную длину новой строки.
Пример 1:
Input: x = 2, y = 5, z = 1
Output: 12
Объяснение: мы можем объединить строки "BB", "AA", "BB", "AA", "BB" и "AB" в таком порядке. Тогда наша новая строка будет "BBAABBAABBAB".
Длина этой строки равна 12, и мы можем показать, что невозможно сформировать строку большей длины.
Пример 2:
Input: x = 3, y = 2, z = 2
Output: 14
Объяснение: мы можем объединить строки "AB", "AB", "AA", "BB", "AA", "BB" и "AA" в таком порядке. Тогда наша новая строка будет "ABABAABBAABBAA".
Длина этой строки равна 14, и мы можем показать, что невозможно сформировать строку большей длины.
Ограничения:
1 <= x, y, z <= 50
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Задачу можно решить с помощью жадного алгоритма или более элегантно - с помощью выведения математической формулы, считающей длину строки. Используем второй способ:
Последовательности, которые мы можем соединять:
"AB" + "AA" = "ABAA"
"BB" + "AB" = "BBAB"
"AA" + "BB" = "AABB"
И те, которые НЕ можем:
"AA" + "AA" = "AAAA"
"BB" + "BB" = "BBBB"
"AA" + "AB" = "AAAB"
Строка "AB" самая безопасная и может использоваться для разбиения других последовательностей.
Если у нас равное количество строк "AA" и "BB" (x == y), то, чтобы высчитать максимальную длину строки нужно: сложить количество строк "AA", "BB" и "AB" и умножить сумму на 2 (по 2 символа в каждой строке).
Если же количество строк "AA" и "BB" различно, то: чередуем "AA" и "BB" столько раз, сколько можно. Далее, когда один из типов строк заканчивается, добавляем ещё одну строку противоположного типа. Так мы максимально продляем строку и не допускаем образования запрещённой подстроки.
Для наглядности:
Если x < y: ...AA + BB + AB - и дальше можем продолжать строку только типом "AB".
Если x > y: ...BB + AA или ...BB + AB + AA - и далее строку продолжать невозможно.
Определим, строк какого типа у нас меньше ("AA" или "BB"). Сформулируем формулу: мы используем все строки безопасного типа "AB" (по 2 символа в каждой: z * 2), также все строки того типа, которого у нас меньше (m * 2 символа), и строки противоположного типа в количестве, равном количеству строк менее частого типа + 1 ((m + 1)* 2 символа).
Сложность
O(1) - по времени
O(1) - по памяти
Код
class Solution:
def longestString(self, x: int, y: int, z: int) -> int:
m = min(x, y)
if x == y:
return 2 * (x + y + z)
else:
return 2 * m + (m + 1) * 2 + 2 * z
@algoses
Даны три целых числа: x, y и z.
У вас есть x строк, равных "AA", y строк, равных "BB", и z строк, равных "AB". Вы хотите выбрать некоторое (возможно, все или ни одной) количество из этих строк и объединить их в некотором порядке, чтобы сформировать новую строку. Эта новая строка не должна содержать подстрок "AAA" или "BBB".
Известно, что подстрока - это непрерывная непустая последовательность символов внутри строки.
Верните максимально возможную длину новой строки.
Пример 1:
Input: x = 2, y = 5, z = 1
Output: 12
Объяснение: мы можем объединить строки "BB", "AA", "BB", "AA", "BB" и "AB" в таком порядке. Тогда наша новая строка будет "BBAABBAABBAB".
Длина этой строки равна 12, и мы можем показать, что невозможно сформировать строку большей длины.
Пример 2:
Input: x = 3, y = 2, z = 2
Output: 14
Объяснение: мы можем объединить строки "AB", "AB", "AA", "BB", "AA", "BB" и "AA" в таком порядке. Тогда наша новая строка будет "ABABAABBAABBAA".
Длина этой строки равна 14, и мы можем показать, что невозможно сформировать строку большей длины.
Ограничения:
1 <= x, y, z <= 50
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Последовательности, которые мы можем соединять:
"AB" + "AA" = "ABAA"
"BB" + "AB" = "BBAB"
"AA" + "BB" = "AABB"
И те, которые НЕ можем:
"AA" + "AA" = "AAAA"
"BB" + "BB" = "BBBB"
"AA" + "AB" = "AAAB"
Строка "AB" самая безопасная и может использоваться для разбиения других последовательностей.
Если у нас равное количество строк "AA" и "BB" (x == y), то, чтобы высчитать максимальную длину строки нужно: сложить количество строк "AA", "BB" и "AB" и умножить сумму на 2 (по 2 символа в каждой строке).
Если же количество строк "AA" и "BB" различно, то: чередуем "AA" и "BB" столько раз, сколько можно. Далее, когда один из типов строк заканчивается, добавляем ещё одну строку противоположного типа. Так мы максимально продляем строку и не допускаем образования запрещённой подстроки.
Для наглядности:
Если x < y: ...AA + BB + AB - и дальше можем продолжать строку только типом "AB".
Если x > y: ...BB + AA или ...BB + AB + AA - и далее строку продолжать невозможно.
Определим, строк какого типа у нас меньше ("AA" или "BB"). Сформулируем формулу: мы используем все строки безопасного типа "AB" (по 2 символа в каждой: z * 2), также все строки того типа, которого у нас меньше (m * 2 символа), и строки противоположного типа в количестве, равном количеству строк менее частого типа + 1 ((m + 1)* 2 символа).
Сложность
O(1) - по памяти
Код
def longestString(self, x: int, y: int, z: int) -> int:
m = min(x, y)
if x == y:
return 2 * (x + y + z)
else:
return 2 * m + (m + 1) * 2 + 2 * z
@algoses
🔥4❤1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Новогодние скидки на нашу линейку математических курсов 🎓
Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
➡️ алгоритмы
➡️ теория вероятностей
➡️ линейная алгебра
➡️ математический анализ
Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что вам реально понадобится! Хочешь конкретики? На нашам сайте можно найти программу, подробности и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты! А если вы выполните все рекомендации, но не достигнете поставленной цели, то вам вернут все потраченные деньги!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что вам реально понадобится! Хочешь конкретики? На нашам сайте можно найти программу, подробности и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты! А если вы выполните все рекомендации, но не достигнете поставленной цели, то вам вернут все потраченные деньги!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Please open Telegram to view this post
VIEW IN TELEGRAM
❤3
Media is too big
VIEW IN TELEGRAM
В ИТМО открылся МЕГАКОВОРКИНГ Сбера 🔥
740 м² футуризма в историческом корпусе, очень большое студенческое пространство в университете с технологиями Умного дома Sber: умное освещение, климат-контроль, интеллектуальные колонки с ГигаЧат и интерактивные панели для командной работы. Пространство трансформируется под любые задачи — от тихих зон до переговорных и лектория.
На новоселье студенты протестировали все возможности: послушали воркшоп про карьеру в IT, пообщались с рекрутерами и зависали под живую музыку 💚
Подписывайся на СберСтудент!
740 м² футуризма в историческом корпусе, очень большое студенческое пространство в университете с технологиями Умного дома Sber: умное освещение, климат-контроль, интеллектуальные колонки с ГигаЧат и интерактивные панели для командной работы. Пространство трансформируется под любые задачи — от тихих зон до переговорных и лектория.
На новоселье студенты протестировали все возможности: послушали воркшоп про карьеру в IT, пообщались с рекрутерами и зависали под живую музыку 💚
Подписывайся на СберСтудент!
🗿7🔥3❤2😍1
Задача с собеседования в Zalando
Даны два целых числа a и b. Верните любую возможную строку s, такую, что:
- s имеет длину, равную a + b, и содержит ровно a букв "a" и ровно b букв "b",
- подстрока "aaa" не встречается в s,
- и подстрока "bbb" не содержится в s.
Пример 1:
Input: a = 1, b = 2
Output: "abb"
("abb", "bab" and "bba" - корректные варианты)
Пример 2:
Input: a = 4, b = 1
Output: "aabaa"
Ограничения:
0 <= a, b <= 100
Гарантируется, что существует строка s для данных a и b.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Применяем жадный алгоритм: выбираем символ, которого у нас больше, чтобы сбалансировать разницу между ними и сохранить менее частый символ для случаев, когда необходимо будет разбить последовательность более частого. Если два последних символа одинаковы - добавляем противоположный, чтобы не допустить подстроки с тремя повторяющимися буквами.
Сложность
O(a + b) - по времени
O(a + b) - по памяти
Код
class Solution:
def strWithout3a3b(self, a: int, b: int) -> str:
result = []
while a > 0 or b > 0:
if len(result) >=2 and result[-1] == result[-2]:
if result[-1] == "a":
result.append("b")
b -= 1
else:
result.append("a")
a -= 1
else:
if a >= b:
result.append("a")
a -= 1
else:
result.append("b")
b -= 1
return "".join(result)
@algoses
Даны два целых числа a и b. Верните любую возможную строку s, такую, что:
- s имеет длину, равную a + b, и содержит ровно a букв "a" и ровно b букв "b",
- подстрока "aaa" не встречается в s,
- и подстрока "bbb" не содержится в s.
Пример 1:
Input: a = 1, b = 2
Output: "abb"
("abb", "bab" and "bba" - корректные варианты)
Пример 2:
Input: a = 4, b = 1
Output: "aabaa"
Ограничения:
0 <= a, b <= 100
Гарантируется, что существует строка s для данных a и b.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Сложность
O(a + b) - по памяти
Код
def strWithout3a3b(self, a: int, b: int) -> str:
result = []
while a > 0 or b > 0:
if len(result) >=2 and result[-1] == result[-2]:
if result[-1] == "a":
result.append("b")
b -= 1
else:
result.append("a")
a -= 1
else:
if a >= b:
result.append("a")
a -= 1
else:
result.append("b")
b -= 1
return "".join(result)
@algoses
🔥2❤1
Media is too big
VIEW IN TELEGRAM
Как прошел ICPC Northern Eurasia Finals 2025 🔥
15-17 декабря в Питере 317 команд из лучших вузов боролись за путёвку в мировой финал ICPC — чемпионата мира по программированию
Сбер в этом году стал партнёром финала и пригласил участников на экскурсию в ИТ-Хаб, где создают продукты для 100+ миллионов пользователей. Команда блока «Риски» Сбера рассказала про AI-Researcher — мультиагентную систему, которая сама проводит исследования: придумывает гипотезы, пишет код и тестирует результаты. По ряду параметров система уже обошла аналоги от Google DeepMind 💻
А на церемонии награждения Сбер поздравил ребят, которые теперь едут на World Finals 🏆
Спортивное программирование — это не только алгоритмы, но и живое комьюнити. Здесь находят друзей, менторов и будущих коллег 💚
15-17 декабря в Питере 317 команд из лучших вузов боролись за путёвку в мировой финал ICPC — чемпионата мира по программированию
Сбер в этом году стал партнёром финала и пригласил участников на экскурсию в ИТ-Хаб, где создают продукты для 100+ миллионов пользователей. Команда блока «Риски» Сбера рассказала про AI-Researcher — мультиагентную систему, которая сама проводит исследования: придумывает гипотезы, пишет код и тестирует результаты. По ряду параметров система уже обошла аналоги от Google DeepMind 💻
А на церемонии награждения Сбер поздравил ребят, которые теперь едут на World Finals 🏆
Спортивное программирование — это не только алгоритмы, но и живое комьюнити. Здесь находят друзей, менторов и будущих коллег 💚
❤2🤣2
Задача с собеседования в Zenefits
Дан массив nums размером n, верните элемент большинства (гарантируется, что он всегда есть в массиве).
Элемент большинства (или мажоритарный) - это преобладающий элемент последовательности, который в данном случае должен встречаться более, чем n / 2 раз.
Решите задачу за линейное время и с O(1) по памяти.
Пример 1:
Input: nums = [3,2,3]
Output: 3
Пример 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Без дополнительного условия на асимптотику задачу можно было бы решить с использованием хэш-таблицы, где ключ - элемент массива, а значение - кол-во его вхождений в массив. Сложность при этом: O(n) - по времени и O(n) - по памяти.
С учётом условия улучшения пространственной сложности до O(1), оптимальным и стандартным будет использование алгоритма Бойера-Мура:
Создаём две переменные: result (содержит элемент, претендующий на то, чтобы оказаться мажоритарным) и count (счётчик "приоритета" элемента-кандидата на преобладание в последовательности). В начале цикла кандидатом окажется элемент, идущий первым в массиве, увеличиваем счётчик его "приоритета" на 1. Далее мы сравниваем каждый последующий элемент с текущим значением result, если они равны - увеличиваем счётчик, если нет - уменьшаем. Если в какой-то момент счётчик приоритета становится равным 0, выбираем нового кандидата и записываем в result. Так проходим по всем эл-там массива и в конце выводим result с последним вписанным в него значением.
Таким образом, суть алгоритма в симуляции попарного "обнуления" противоположных элементов путём уменьшения счётчика count. Так как преобладающий эл-т составляет больше половины всей последовательности, в процессе для него не останется противоположного элемента для попарного "удаления". Наличие мажоритарного эл-та гарантируется условием задачи, поэтому нам не нужна дополнительная проверка.
Сложность
O(n) - по времени
O(1) - по памяти
Код
class Solution:
def majorityElement(self, nums: List[int]) -> int:
result, count = 0, 0
for i in nums:
if count == 0:
result = i
count += 1
elif i == result:
count += 1
else:
count -= 1
return result
@algoses
Дан массив nums размером n, верните элемент большинства (гарантируется, что он всегда есть в массиве).
Элемент большинства (или мажоритарный) - это преобладающий элемент последовательности, который в данном случае должен встречаться более, чем n / 2 раз.
Решите задачу за линейное время и с O(1) по памяти.
Пример 1:
Input: nums = [3,2,3]
Output: 3
Пример 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
С учётом условия улучшения пространственной сложности до O(1), оптимальным и стандартным будет использование алгоритма Бойера-Мура:
Создаём две переменные: result (содержит элемент, претендующий на то, чтобы оказаться мажоритарным) и count (счётчик "приоритета" элемента-кандидата на преобладание в последовательности). В начале цикла кандидатом окажется элемент, идущий первым в массиве, увеличиваем счётчик его "приоритета" на 1. Далее мы сравниваем каждый последующий элемент с текущим значением result, если они равны - увеличиваем счётчик, если нет - уменьшаем. Если в какой-то момент счётчик приоритета становится равным 0, выбираем нового кандидата и записываем в result. Так проходим по всем эл-там массива и в конце выводим result с последним вписанным в него значением.
Таким образом, суть алгоритма в симуляции попарного "обнуления" противоположных элементов путём уменьшения счётчика count. Так как преобладающий эл-т составляет больше половины всей последовательности, в процессе для него не останется противоположного элемента для попарного "удаления".
Сложность
O(1) - по памяти
Код
def majorityElement(self, nums: List[int]) -> int:
result, count = 0, 0
for i in nums:
if count == 0:
result = i
count += 1
elif i == result:
count += 1
else:
count -= 1
return result
@algoses
❤5😈4