Задача с собеседования в Яндекс
Реализовать функцию fuzzypussy search как в редакторе sublime text 3.
Для незнакомых с редактором - по факту требуется проверить, является ли первая строка подпоследовательностью второй
fuzzysearch('car', 'cartwheel') -> true
наш чат алгоритмистов
Решение:
Один проход по символам строки
def fuzzysearch(needle, haystack):
if not needle:
return True
if not haystack:
return False
i = 0 # индекс в needle
for char in haystack:
if char == needle[i]:
i += 1
if i == len(needle):
return True
return False
Асимптотика O(N)
@algoses
Реализовать функцию fuzzy
Для незнакомых с редактором - по факту требуется проверить, является ли первая строка подпоследовательностью второй
fuzzysearch('car', 'cartwheel') -> true
наш чат алгоритмистов
Решение:
def fuzzysearch(needle, haystack):
if not needle:
return True
if not haystack:
return False
i = 0 # индекс в needle
for char in haystack:
if char == needle[i]:
i += 1
if i == len(needle):
return True
return False
Асимптотика O(N)
@algoses
❤19🔥6😁4
Свершилось! Поступашки открывают набор на новую линейку математических курсов 🎓
Хочешь поступить в Ai Masters или топовую магистратуру? А, может, ты мечтаешь тащить собесы, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
➡️ алгоритмы
➡️ теория вероятностей
➡️ линейная алгебра
➡️ математический анализ
Все курсы стартуют 28.07, все лекции выложены сразу. Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий Ai Mastersа, разбор реального контеста в Ai Masters, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, ты получишь эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты!
📊 Цена очень доступная: 12'000 7'500 рублей за каждый курс. До 16.07 включительно отдаем курс со скидкой, дальше продажи по зачеркнутой цене.
Для вопросов и покупок пишем администратору и не тянем с этим: количество мест ограничено!
Хочешь поступить в Ai Masters или топовую магистратуру? А, может, ты мечтаешь тащить собесы, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
Все курсы стартуют 28.07, все лекции выложены сразу. Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий Ai Mastersа, разбор реального контеста в Ai Masters, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, ты получишь эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты!
Для вопросов и покупок пишем администратору и не тянем с этим: количество мест ограничено!
Please open Telegram to view this post
VIEW IN TELEGRAM
❤3
Задача с собеседования в Яндекс
Дана строка из десятичных цифр (длинное число, младшие разряды расположены по младшему индексу). Написать код, который умножит это число на число 1 <= n <= 9.
Ограничения по памяти: О(1) доп памяти, т.е. надо использовать исходную строку (считаем, что возможное увеличение длины на 1 разряд не приведет к реаллокации)
наш чат алгоритмистов
Решение:
Пройдемся по строке с разрядами и столбиком умножим число на n. Поддерживаем остаток и считаем так до конца
def multiply_digit_inplace(num_str, n):
if not (1 <= n <= 9):
raise ValueError("n должен быть от 1 до 9")
num = list(num_str) # строка как список символов (можно считать, что это изменяемый массив)
carry = 0
for i in range(len(num)):
digit = int(num[i])
prod = digit * n + carry
num[i] = str(prod % 10)
carry = prod // 10
if carry:
num.append(str(carry))
return ''.join(num)
Асимптотика O(N)
@algoses
Дана строка из десятичных цифр (длинное число, младшие разряды расположены по младшему индексу). Написать код, который умножит это число на число 1 <= n <= 9.
Ограничения по памяти: О(1) доп памяти, т.е. надо использовать исходную строку (считаем, что возможное увеличение длины на 1 разряд не приведет к реаллокации)
наш чат алгоритмистов
Решение:
def multiply_digit_inplace(num_str, n):
if not (1 <= n <= 9):
raise ValueError("n должен быть от 1 до 9")
num = list(num_str) # строка как список символов (можно считать, что это изменяемый массив)
carry = 0
for i in range(len(num)):
digit = int(num[i])
prod = digit * n + carry
num[i] = str(prod % 10)
carry = prod // 10
if carry:
num.append(str(carry))
return ''.join(num)
Асимптотика O(N)
@algoses
😁5❤4
Свершилось! Поступашки открывают набор на новую линейку карьерных курсов 🎉
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
➡️ дата сайнс (глубокое обучение)
➡️ фронтенд
➡️ дата инженер
➡️ математика для карьеры
Все курсы стартует 03.08. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
📊 Цена 15'000р 9'000р при покупке до 18 июля включительно! Хочешь купить несколько курсов сразу? Дадим хорошую скидку!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Не забываем и про линейку старт, на которую тоже только до 18.07 действует скидка 40%!
➡️ алгоритмы старт
➡️ аналитика старт
➡️ машинное обучение старт
➡️ бэкенд разработка старт
ЗАПИСАТЬСЯ
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
Все курсы стартует 03.08. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Не забываем и про линейку старт, на которую тоже только до 18.07 действует скидка 40%!
ЗАПИСАТЬСЯ
Please open Telegram to view this post
VIEW IN TELEGRAM
❤2
Задача с собеседования в Яндекс
На входе дана непустая строка. Требуется вяснить, можно ли удалить из нее ровно один символ так, чтобы получился палиндром.
Требуется решение за линейное время с константой дополнительной памяти.
наш чат алгоритмистов
Решение:
Несложно заметить следующее
Если строка уже является палиндромом, то ответ всегда положительный (достаточно удалить центральный или один из центральных символов)
В противном случае, если начать проверку строки на палиндромность с левого и правого концов - можно найти первое несовпадение abcX....Ycba. Можно заметить, что в случае положительного ответа на задачу один из символов X или Y в данном несовпадении должен быть удален и что после этого палиндромом должна быть строка .....Y или X.....
Таким образом, решение задачи сводится к поиску такого несовпадения и проверки двух случаев
def can_be_palindrome_by_removing_one_char(s):
def is_palindrome_range(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
left, right = 0, len(s) - 1
while left < right and s[left] == s[right]:
left += 1
right -= 1
if left >= right:
return True # строка уже палиндром или можно удалить любой символ
# Проверяем два варианта: пропустить символ слева или справа
return (is_palindrome_range(left + 1, right) or
is_palindrome_range(left, right - 1))
@algoses
На входе дана непустая строка. Требуется вяснить, можно ли удалить из нее ровно один символ так, чтобы получился палиндром.
Требуется решение за линейное время с константой дополнительной памяти.
наш чат алгоритмистов
Решение:
Если строка уже является палиндромом, то ответ всегда положительный (достаточно удалить центральный или один из центральных символов)
В противном случае, если начать проверку строки на палиндромность с левого и правого концов - можно найти первое несовпадение abcX....Ycba. Можно заметить, что в случае положительного ответа на задачу один из символов X или Y в данном несовпадении должен быть удален и что после этого палиндромом должна быть строка .....Y или X.....
Таким образом, решение задачи сводится к поиску такого несовпадения и проверки двух случаев
def can_be_palindrome_by_removing_one_char(s):
def is_palindrome_range(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
left, right = 0, len(s) - 1
while left < right and s[left] == s[right]:
left += 1
right -= 1
if left >= right:
return True # строка уже палиндром или можно удалить любой символ
# Проверяем два варианта: пропустить символ слева или справа
return (is_palindrome_range(left + 1, right) or
is_palindrome_range(left, right - 1))
@algoses
🔥14❤8
Задача с собеседования в Яндекс
Дан вектор, надо удалить из него нули, сохранив порядок остальных элементов. Интересует как с использованием стандартных средств, так и без них.
наш чат алгоритмистов
Решение:
Линейно пройдемся по элементам массива, поддерживая указатель на записываемый элемент. Затем удалим лишние индексы
def remove_zeros(arr):
write = 0
for read in range(len(arr)):
if arr[read] != 0:
arr[write] = arr[read]
write += 1
# обрезаем хвост (если надо)
del arr[write:]
Асимптотика O(N)
@algoses
Дан вектор, надо удалить из него нули, сохранив порядок остальных элементов. Интересует как с использованием стандартных средств, так и без них.
наш чат алгоритмистов
Решение:
def remove_zeros(arr):
write = 0
for read in range(len(arr)):
if arr[read] != 0:
arr[write] = arr[read]
write += 1
# обрезаем хвост (если надо)
del arr[write:]
Асимптотика O(N)
@algoses
😁20❤4
Задача с собеседования в Т-банк
Условие:
Определим понятие хорошей последовательности - абсолютная разница между любыми двумя элементами этой последовательности должна быть больше либо равна максимальному элементу. То есть (i, j) | a_i - a_j | > max(a[l:r+1]). Вам даётся массив длины 10^5 и требуется определить наибольшую длину хорошей подпослдеовательности.
наш чат алгоритмистов
Решение:
Очевидно, что если в подпоследовательности будет больше двух положительных элементов, то x - y > x (x = max(x, y)) верно лишь в том случае, когда y < 0. Соответственно длина последовательности будет точно хотя бы равняться количеству отрицательных элементов. При построении последовательности возьмем один положительный элемент (потому что иначе с двумя положительными не будет выполняться условие |a_i - a_j| > max(a_i, a_j) и возьмем жадно аименьший положительный. Тогда можно будет проверить, получится ли этот положительный элемент добавить в последовательность отрицательных так чтобы не нарушалось то условие (для этого достаточно перебрать наименьшую абсолютную разницу, то есть просто перебрать пары соседних в отсортированном порядке).
int n;
cin >> n;
vector<int> a(n);
int ans = 0;
for (int i = 0; i < n; i++ ){
cin >> a[i];
ans += (a[i] <= 0);
}
sort(a.begin(), a.end());
int mn = inf;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
mn = min(a[i], mn);
}
}
bool flag = (mn != inf);
for (int i = 1; i < n; i++) {
if (a[i] <= 0) {
flag &= (a[i] - a[i - 1] >= mn)
}
}
cout << ans + flag;
@algoses
Условие:
Определим понятие хорошей последовательности - абсолютная разница между любыми двумя элементами этой последовательности должна быть больше либо равна максимальному элементу. То есть (i, j) | a_i - a_j | > max(a[l:r+1]). Вам даётся массив длины 10^5 и требуется определить наибольшую длину хорошей подпослдеовательности.
наш чат алгоритмистов
Решение:
int n;
cin >> n;
vector<int> a(n);
int ans = 0;
for (int i = 0; i < n; i++ ){
cin >> a[i];
ans += (a[i] <= 0);
}
sort(a.begin(), a.end());
int mn = inf;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
mn = min(a[i], mn);
}
}
bool flag = (mn != inf);
for (int i = 1; i < n; i++) {
if (a[i] <= 0) {
flag &= (a[i] - a[i - 1] >= mn)
}
}
cout << ans + flag;
@algoses
🔥4❤3
Поступашки продолжают набор на новую линейку карьерных курсов 🎉
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
➡️ дата сайнс (глубокое обучение)
➡️ фронтенд
➡️ дата инженер
➡️ математика для карьеры
Все курсы стартует 03.08. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
📊 Цена на сайте, только при покупке до 24 июля включительно скидка 40%! Хочешь купить несколько курсов сразу? Дадим хорошую скидку!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Не забываем и про линейку старт, на которую тоже только до 24.07 действует скидка 40%!
➡️ алгоритмы старт
➡️ аналитика старт
➡️ машинное обучение старт
➡️ бэкенд разработка старт
ЗАПИСАТЬСЯ
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
Все курсы стартует 03.08. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Не забываем и про линейку старт, на которую тоже только до 24.07 действует скидка 40%!
ЗАПИСАТЬСЯ
Please open Telegram to view this post
VIEW IN TELEGRAM
❤3
Бесплатные занятия для школьников по ИТ
Приглашаем на Demo Days — цикл открытых занятий от преподавателей ЦУ по разработке, машинному обучению, продакт-менеджменту и аналитике.
Вы сможете:
— поучаствовать в реальных практиках профессий: от анализа данных до создания цифровых продуктов;
— почувствовать себя студентом: один из дней можно пройти очно в кампусе ЦУ;
— получить до +30% к гранту за выполненные домашние задания.
Занятия проходят очно и онлайн, вы можете присоединиться в любой момент до 6 августа
Для учеников 10-х и 11-х классов. Регистрируйтесь по ссылке!
Реклама. АНО ВО "Центральный университет", ИНН 7743418023, erid: 2RanykhxyCm
Приглашаем на Demo Days — цикл открытых занятий от преподавателей ЦУ по разработке, машинному обучению, продакт-менеджменту и аналитике.
Вы сможете:
— поучаствовать в реальных практиках профессий: от анализа данных до создания цифровых продуктов;
— почувствовать себя студентом: один из дней можно пройти очно в кампусе ЦУ;
— получить до +30% к гранту за выполненные домашние задания.
Занятия проходят очно и онлайн, вы можете присоединиться в любой момент до 6 августа
Для учеников 10-х и 11-х классов. Регистрируйтесь по ссылке!
Реклама. АНО ВО "Центральный университет", ИНН 7743418023, erid: 2RanykhxyCm
❤1
Cтарт новой линейки математических курсов уже завтра🎓
Хочешь поступить в Ai Masters или топовую магистратуру? А, может, ты мечтаешь тащить собесы, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
➡️ алгоритмы
➡️ теория вероятностей
➡️ линейная алгебра
➡️ математический анализ
Все курсы стартуют 28.07, все лекции выложены сразу. Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий Ai Mastersа, разбор реального контеста в Ai Masters, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, ты получишь эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты!
📊 Цена очень доступная: 12'000 7'200 только до 26.07 включительно, дальше продажи по зачеркнутой цене.
Для вопросов и покупок пишем администратору и не тянем с этим: количество мест ограничено!
Хочешь поступить в Ai Masters или топовую магистратуру? А, может, ты мечтаешь тащить собесы, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
Все курсы стартуют 28.07, все лекции выложены сразу. Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий Ai Mastersа, разбор реального контеста в Ai Masters, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, ты получишь эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты!
Для вопросов и покупок пишем администратору и не тянем с этим: количество мест ограничено!
Please open Telegram to view this post
VIEW IN TELEGRAM
❤1
Экзамены в Т-академию до 31 августа. Усеваем подать заявку. Академия открывает возможность стажировки или устройства в штат.
Задания на все направления здесь. Там же можно их обсудить вместе с админом 😎😎
@code_of_art
Задания на все направления здесь. Там же можно их обсудить вместе с админом 😎😎
@code_of_art
🔥5👍2❤1
Задача с собеседования в лабораторию Т-банка
Задача:
Нам даны две последовательности A и B из 0 и 1 (длиной до 10^6). У вас есть две операции:
1. Выбрать последовательность и поменять местами элементы на позициях (i, j) - стоимость такой операции будет |i-j|
2. Выбрать элемент последовательности и поменять значение бита на противоположное, стоимость в таком случае будет 1
Требуется за минимальную стоимость сделать последовательности равными
наш чат алгоритмистов
Решение:
Заметим, что операцию 1 нет смысла использовать когда |i - j| > 1, а выигрышь стоимости в 1 достигается только при |i - j| = 1. Тогда можно решать задачу с помощью dp, dp_i - минимальный ответ для того чтобы сделать префиксы последовательностей длинной i равным.
Тогда пересчёта будет два:
Первый - это прийти в состояние i, воспользовавшись операцией 2 и тогда стоимость для префикса длины будет считаться как dp{i-1} + (a[i] != b[i])
Второй - это воспользоваться операцией 2 и поменять символы на позициях (i - 1, i), но в таком случае нужно проверить, что строки станут равными после этой операции (если быть точнее, то префиксы строк).
int n;
cin >> n;
string a, b;
cin >> a;
cin >> b;
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + (a[i - 1] != b[i - 1]);
if (i >= 2 && a[i - 2] == b[i - 1] && a[i - 1] == b[i - 2]) {
dp[i] = min(dp[i], dp[i - 2] + 1);
}
}
cout << dp[n] << '\n';
@algoses
Задача:
Нам даны две последовательности A и B из 0 и 1 (длиной до 10^6). У вас есть две операции:
1. Выбрать последовательность и поменять местами элементы на позициях (i, j) - стоимость такой операции будет |i-j|
2. Выбрать элемент последовательности и поменять значение бита на противоположное, стоимость в таком случае будет 1
Требуется за минимальную стоимость сделать последовательности равными
наш чат алгоритмистов
Решение:
Тогда пересчёта будет два:
Первый - это прийти в состояние i, воспользовавшись операцией 2 и тогда стоимость для префикса длины будет считаться как dp{i-1} + (a[i] != b[i])
Второй - это воспользоваться операцией 2 и поменять символы на позициях (i - 1, i), но в таком случае нужно проверить, что строки станут равными после этой операции (если быть точнее, то префиксы строк).
int n;
cin >> n;
string a, b;
cin >> a;
cin >> b;
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + (a[i - 1] != b[i - 1]);
if (i >= 2 && a[i - 2] == b[i - 1] && a[i - 1] == b[i - 2]) {
dp[i] = min(dp[i], dp[i - 2] + 1);
}
}
cout << dp[n] << '\n';
@algoses
🔥10❤1
Задача с собеса Авито
На вход дана строка, требуется вернуть строку отсортированную по частоте встречаемости символов.
Ограничения:
- длина строки от 1 до 5 * 10 ** 5
- строка состоит из английских букв в верхнем и нижнем регистре
наш чат алгоритмистов
Решение:
С помощью словаря подсчитаем частоты символов— O(N).Создадим массив корзин (bucket), где индекс — это частота символа.
(Максимальная возможная частота символа = N, если вся строка из одного символа.)
Разложим символы по корзинам в соответствии с их частотой — O(M), где M — число уникальных символов (M ≤ N). В конце пройдемся по корзине от самой высокой частоты к низкой и соберем результат — O(N)
def frequencySort(s):
freq = {}
for char in s:
if chat not in freq:
freq[char] = 0
freq[char] += 1
buckets = [[] for _ in range(len(s) + 1)]
for char, count in freq.items():
buckets[count].append(char)
result = []
for count in range(len(buckets) - 1, -1, -1):
for char in buckets[count]:
result.append(char * count)
return ''.join(result)
@algoses
На вход дана строка, требуется вернуть строку отсортированную по частоте встречаемости символов.
Ограничения:
- длина строки от 1 до 5 * 10 ** 5
- строка состоит из английских букв в верхнем и нижнем регистре
наш чат алгоритмистов
С помощью словаря подсчитаем частоты символов— O(N).Создадим массив корзин (bucket), где индекс — это частота символа.
(Максимальная возможная частота символа = N, если вся строка из одного символа.)
Разложим символы по корзинам в соответствии с их частотой — O(M), где M — число уникальных символов (M ≤ N). В конце пройдемся по корзине от самой высокой частоты к низкой и соберем результат — O(N)
def frequencySort(s):
freq = {}
for char in s:
if chat not in freq:
freq[char] = 0
freq[char] += 1
buckets = [[] for _ in range(len(s) + 1)]
for char, count in freq.items():
buckets[count].append(char)
result = []
for count in range(len(buckets) - 1, -1, -1):
for char in buckets[count]:
result.append(char * count)
return ''.join(result)
@algoses
❤11😁2🔥1
Новая линейка карьерных курсов стартует уже в это воскресение 🎉
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
➡️ дата сайнс (глубокое обучение)
➡️ фронтенд
➡️ дата инженер
➡️ математика для карьеры
Все курсы стартует 03.08. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
📊 Цена на сайте, только при покупке до 2 августа включительно скидка 40%! Хочешь купить несколько курсов сразу? Дадим хорошую скидку!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Не забываем и про линейку старт, на которую тоже только до 2 августа действует скидка 40%!
➡️ алгоритмы старт
➡️ аналитика старт
➡️ машинное обучение старт
➡️ бэкенд разработка старт
ЗАПИСАТЬСЯ
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
Все курсы стартует 03.08. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Не забываем и про линейку старт, на которую тоже только до 2 августа действует скидка 40%!
ЗАПИСАТЬСЯ
Please open Telegram to view this post
VIEW IN TELEGRAM
❤4👍1
Задача с собеседования в Яндекс
Дан массив целых чисел nums и целое число k. Необходимо найти количество смежных подмассивов, произведение элементов которых строго меньше k.
nums = [10, 5, 2, 6], k = 100
Ответ: 8
Объяснение: 8 подмассивов удовлетворяют условию:
[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6].
Ограничения:
длина от 1 до 3 *10^ 4
значения от 1 до 1000
k от 1 до 10 ^ 6
наш чат алгоритмистов
Используем метод скользящего окна с двумя указателями (left и right). product = 1 (текущее произведение), count = 0 (счётчик подмассивов), left = 0 (левый указатель). Для каждого right от 0 до n-1. Умножаем product на nums[right]. Если product >= k, сдвигаем left, деля product на nums[left], пока product снова не станет < k. Добавляем к count количество новых подмассивов: right - left + 1.
def num_subarrays_product_less_than_k(nums, k):
if k <= 1:
return 0
product = 1
count = left = 0
for right in range(len(nums)):
product *= nums[right]
while product >= k:
product /= nums[left]
left += 1
count += right - left + 1
return count
@algoses
Дан массив целых чисел nums и целое число k. Необходимо найти количество смежных подмассивов, произведение элементов которых строго меньше k.
nums = [10, 5, 2, 6], k = 100
Ответ: 8
Объяснение: 8 подмассивов удовлетворяют условию:
[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6].
Ограничения:
длина от 1 до 3 *10^ 4
значения от 1 до 1000
k от 1 до 10 ^ 6
наш чат алгоритмистов
Используем метод скользящего окна с двумя указателями (left и right). product = 1 (текущее произведение), count = 0 (счётчик подмассивов), left = 0 (левый указатель). Для каждого right от 0 до n-1. Умножаем product на nums[right]. Если product >= k, сдвигаем left, деля product на nums[left], пока product снова не станет < k. Добавляем к count количество новых подмассивов: right - left + 1.
def num_subarrays_product_less_than_k(nums, k):
if k <= 1:
return 0
product = 1
count = left = 0
for right in range(len(nums)):
product *= nums[right]
while product >= k:
product /= nums[left]
left += 1
count += right - left + 1
return count
@algoses
👍14❤2🔥1
Свершилось! Поступашки открывают набор на новую линейку продвинутых карьерных курсов 🎉
Мечтаешь стать крутым специалистом и с легкость тащить рабочие задачи и собесы, получив конкурентное преимущество? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
➡️ машинное обучение хард
➡️ бэкенд хард
➡️ аналитика хард
➡️ алгоритмы хард
Курсы продвинутые и рассчитаны на тех, у кого уже есть БАЗА, для тех, кто хочет затронуть более сложные темы и идеально подготовиться к собесам, для тех, кто претендует на что-то большее чем просто джуниор. Если вы только в начале своего пути, советуем курсы старт, на которые тоже до 08.08 действует скидка.
Все курсы стартует 17.08. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- продвинутые пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
📊 Цена 12'000р 7'200р при покупке до 8 августа включительно! Хочешь купить несколько курсов сразу? Дадим хорошую скидку!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Не забываем и про линейку старт, на которую тоже только до 08.08 действует скидка 40%!
➡️ алгоритмы старт
➡️ аналитика старт
➡️ машинное обучение старт
➡️ бэкенд разработка старт
ЗАПИСАТЬСЯ
Мечтаешь стать крутым специалистом и с легкость тащить рабочие задачи и собесы, получив конкурентное преимущество? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
Курсы продвинутые и рассчитаны на тех, у кого уже есть БАЗА, для тех, кто хочет затронуть более сложные темы и идеально подготовиться к собесам, для тех, кто претендует на что-то большее чем просто джуниор. Если вы только в начале своего пути, советуем курсы старт, на которые тоже до 08.08 действует скидка.
Все курсы стартует 17.08. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- продвинутые пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Не забываем и про линейку старт, на которую тоже только до 08.08 действует скидка 40%!
ЗАПИСАТЬСЯ
Please open Telegram to view this post
VIEW IN TELEGRAM
❤2
Задача с собеседования Яндекс
Задача
Дана последовательность 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
🔥11🤨5❤3🙈2🙉1
Яндекс открывает набор в бесплатные олимпиадные Кружки по программированию, искусственному интеллекту и математике
В этом году, помимо Кружка по олимпиадному программированию для школьников 6–11 классов, впервые открываются направления по искусственному интеллекту (8–11 классы) и олимпиадной математике (5–11 классы).
Обучение во всех Кружках бесплатное и доступно онлайн и офлайн. Занятия ведут опытные преподаватели: победители олимпиад, тренеры сборных и члены жюри. В программу обучения входят лекции, семинары с разбором задач и пробные олимпиадные туры. Успешное прохождение курса поможет занять призовые места на олимпиадах, что значительно повысит шансы на поступление в вуз.
Выпускники курса по программированию уже составляют большинство победителей и призеров Всероссийской олимпиады.
Обучение бесплатное. Успейте подать заявки: до 3 сентября — на математику и до 30 сентября — на ИИ. Занятия стартуют осенью 2025 года
В этом году, помимо Кружка по олимпиадному программированию для школьников 6–11 классов, впервые открываются направления по искусственному интеллекту (8–11 классы) и олимпиадной математике (5–11 классы).
Обучение во всех Кружках бесплатное и доступно онлайн и офлайн. Занятия ведут опытные преподаватели: победители олимпиад, тренеры сборных и члены жюри. В программу обучения входят лекции, семинары с разбором задач и пробные олимпиадные туры. Успешное прохождение курса поможет занять призовые места на олимпиадах, что значительно повысит шансы на поступление в вуз.
Выпускники курса по программированию уже составляют большинство победителей и призеров Всероссийской олимпиады.
Обучение бесплатное. Успейте подать заявки: до 3 сентября — на математику и до 30 сентября — на ИИ. Занятия стартуют осенью 2025 года
🍌4🔥2❤1💊1
Красная таблетка от рутины: шаг за пределы консоли в автоматизацию тестирования на JavaScript ⤵️
🔜 Уже 14 августа в 20:00 состоится интенсив от QA.GURU, который проведет автор курса «Автоматизация тестирования на Javascript + Playwright» Любовь Данилова — «Красная таблетка: вход в автоматизацию»!
Что успеете за занятие👇
— Возьмете реальное тестовое задание на тестирование бэкенда:
— Напишете автотесты в прямом эфире
— Подключите Allure
— Настроите CI/CD
— Используете Playwright + JavaScript
— Обсудите, как выполняет задание junior и middle
✔️ Также вас ждет бонусный блок от руководителя карьерного центра — Маргариты Головко:
— Рынок труда: что происходит сейчас и как искать работу?
— Карьерный трек и зарплаты AQA
— Как мы помогаем находить работу? Про Карьерный центр и сопровождение.
Регистрируйтесь по ссылке, чтобы не пропустить!👨💻
Что успеете за занятие
— Возьмете реальное тестовое задание на тестирование бэкенда:
— Напишете автотесты в прямом эфире
— Подключите Allure
— Настроите CI/CD
— Используете Playwright + JavaScript
— Обсудите, как выполняет задание junior и middle
— Рынок труда: что происходит сейчас и как искать работу?
— Карьерный трек и зарплаты AQA
— Как мы помогаем находить работу? Про Карьерный центр и сопровождение.
Регистрируйтесь по ссылке, чтобы не пропустить!
Please open Telegram to view this post
VIEW IN TELEGRAM
❤1👍1
Задача с собеседования в Яндекс
Дано бинарное дерево (не поиска):
struct Node {
Node* parent;
Node* left;
Node* right;
}
Нужно написать функцию, которая для двух данных вершин будет возвращать их наименьшего (ближайшего) общего предка:
Node* lca(Node* a, Node* b);
Ограничения: память O(1)
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение:
Считаем глубину для каждой вершины, потом идем двумя указателями вверх от вершин, пока они не встретятся. O(h) по времени, где h - высота дерева.
#include <unordered_map>
struct Node {
Node* parent;
Node* left;
Node* right;
};
std::unordered_map<Node*, int> depth_map;
void compute_depths(Node* node, int depth = 0) {
if (!node) return;
depth_map[node] = depth;
if (node->left) {
node->left->parent = node;
compute_depths(node->left, depth + 1);
}
if (node->right) {
node->right->parent = node;
compute_depths(node->right, depth + 1);
}
}
Node* lca(Node* a, Node* b) {
int da = depth_map[a];
int db = depth_map[b];
while (da > db) {
a = a->parent;
--da;
}
while (db > da) {
b = b->parent;
--db;
}
while (a != b) {
a = a->parent;
b = b->parent;
}
return a;
}
@algoses
Дано бинарное дерево (не поиска):
struct Node {
Node* parent;
Node* left;
Node* right;
}
Нужно написать функцию, которая для двух данных вершин будет возвращать их наименьшего (ближайшего) общего предка:
Node* lca(Node* a, Node* b);
Ограничения: память O(1)
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение:
struct Node {
Node* parent;
Node* left;
Node* right;
};
std::unordered_map<Node*, int> depth_map;
void compute_depths(Node* node, int depth = 0) {
if (!node) return;
depth_map[node] = depth;
if (node->left) {
node->left->parent = node;
compute_depths(node->left, depth + 1);
}
if (node->right) {
node->right->parent = node;
compute_depths(node->right, depth + 1);
}
}
Node* lca(Node* a, Node* b) {
int da = depth_map[a];
int db = depth_map[b];
while (da > db) {
a = a->parent;
--da;
}
while (db > da) {
b = b->parent;
--db;
}
while (a != b) {
a = a->parent;
b = b->parent;
}
return a;
}
@algoses
🔥3🏆3❤2