Задача с собеседования в МТС
Условие задачи
Вы начинаете в точке (0, 0). Доступны 4 типа перемещений:
U (x, y) -> (x, y+1)
R (x, y) -> (x+1, y)
D (x, y) -> (x, y-1)
L (x, y) -> (x-1, y)
Нельзя использовать все 4 типа перемещений. Можно задействовать не более 3 различных способов (каждый — сколько угодно раз).
Даны n точек с целочисленными координатами. Определите, можно ли посетить все точки (в любом порядке), соблюдая ограничение на типы перемещения.
Чат алгоритмистов
Банк собесов по алгоритмам
Решение
Чтобы обойти ограничение, необходимо полностью исключить один из типов. Это означает, что все точки должны лежать в одной из полуплоскостей:
1. Без D (вниз): все точки с y ≥ 0 (верхняя полуплоскость)
2. Без U (вверх): все точки с y ≤ 0` (нижняя полуплоскость)
3. Без L (влево): все точки с x ≥ 0 (правая полуплоскость)
4. Без R (вправо): все точки с x ≤ 0 (левая полуплоскость)
Если выполняется хотя бы одно условие, ответ yes. Иначе - no.
n = int(input())
no_D = True
no_U = True
no_L = True
no_R = True
for _ in range(n):
x, y = map(int, input().split())
if y < 0:
no_D = False
if y > 0:
no_U = False
if x < 0:
no_L = False
if x > 0:
no_R = False
if no_D or no_U or no_L or no_R:
print("yes")
else:
print("no")
@algoses
Условие задачи
Вы начинаете в точке (0, 0). Доступны 4 типа перемещений:
U (x, y) -> (x, y+1)
R (x, y) -> (x+1, y)
D (x, y) -> (x, y-1)
L (x, y) -> (x-1, y)
Нельзя использовать все 4 типа перемещений. Можно задействовать не более 3 различных способов (каждый — сколько угодно раз).
Даны n точек с целочисленными координатами. Определите, можно ли посетить все точки (в любом порядке), соблюдая ограничение на типы перемещения.
Чат алгоритмистов
Банк собесов по алгоритмам
Решение
1. Без D (вниз): все точки с y ≥ 0 (верхняя полуплоскость)
2. Без U (вверх): все точки с y ≤ 0` (нижняя полуплоскость)
3. Без L (влево): все точки с x ≥ 0 (правая полуплоскость)
4. Без R (вправо): все точки с x ≤ 0 (левая полуплоскость)
Если выполняется хотя бы одно условие, ответ yes. Иначе - no.
n = int(input())
no_D = True
no_U = True
no_L = True
no_R = True
for _ in range(n):
x, y = map(int, input().split())
if y < 0:
no_D = False
if y > 0:
no_U = False
if x < 0:
no_L = False
if x > 0:
no_R = False
if no_D or no_U or no_L or no_R:
print("yes")
else:
print("no")
@algoses
🗿35❤7😁4
Задача с собеседования Яндекс
Задача
Дана последовательность 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