Задача с собеседования в Яндекс
Написать функцию, которая меняет порядок слов в строке на противоположный, при этом не меняя расположение пробелов
Например: __hello_my___dear_world_ -> __world_dear___my_hello_
Наш чат алгоритмистов
Решение:
Мы сохраняем следующую инфу из строки: слова (подряд идущие непробельные символы) и пробелы (их количество после каждого слова + отдельно ведущие и конечные пробелы).
После этого мы можем взять все слова в обратном порядке, а пробелы вставить ровно так, как они шли в исходной строке.
Код:
string reverseWordsKeepSpaces(const string &s) {
int n = (int)s.size();
int i = 0;
// 1) leading spaces
int leading = 0;
while (i < n && s[i] == ' ') { ++leading; ++i; }
vector<string> words;
vector<int> spacesAfter; // spaces after each word; последний элемент = trailing spaces
// 2) collect words and following spaces counts
while (i < n) {
int j = i;
while (j < n && s[j] != ' ') ++j;
words.emplace_back(s.substr(i, j - i));
int cnt = 0;
int k = j;
while (k < n && s[k] == ' ') { ++cnt; ++k; }
spacesAfter.push_back(cnt);
i = k;
}
// если никаких слов (только пробелы или пустая строка) — вернуть как есть
if (words.empty()) return s;
// trailing spaces — последний элемент spacesAfter
int trailing = spacesAfter.back();
spacesAfter.pop_back(); // теперь spacesAfter.size() == words.size()-1
// 3) формируем результат: leading + reversed words interleaved с spacesAfter (в том же порядке) + trailing
string res;
res.reserve(n);
res.append(leading, ' ');
int m = (int)words.size();
for (int idx = 0; idx < m; ++idx) {
// берем слова с конца: words[m-1], words[m-2], ...
res += words[m - 1 - idx];
if (idx < (int)spacesAfter.size()) {
res.append(spacesAfter[idx], ' ');
}
}
res.append(trailing, ' ');
return res;
}
Асимптотика O(N)
@algoses
Написать функцию, которая меняет порядок слов в строке на противоположный, при этом не меняя расположение пробелов
Например: __hello_my___dear_world_ -> __world_dear___my_hello_
Наш чат алгоритмистов
Решение:
После этого мы можем взять все слова в обратном порядке, а пробелы вставить ровно так, как они шли в исходной строке.
Код:
string reverseWordsKeepSpaces(const string &s) {
int n = (int)s.size();
int i = 0;
// 1) leading spaces
int leading = 0;
while (i < n && s[i] == ' ') { ++leading; ++i; }
vector<string> words;
vector<int> spacesAfter; // spaces after each word; последний элемент = trailing spaces
// 2) collect words and following spaces counts
while (i < n) {
int j = i;
while (j < n && s[j] != ' ') ++j;
words.emplace_back(s.substr(i, j - i));
int cnt = 0;
int k = j;
while (k < n && s[k] == ' ') { ++cnt; ++k; }
spacesAfter.push_back(cnt);
i = k;
}
// если никаких слов (только пробелы или пустая строка) — вернуть как есть
if (words.empty()) return s;
// trailing spaces — последний элемент spacesAfter
int trailing = spacesAfter.back();
spacesAfter.pop_back(); // теперь spacesAfter.size() == words.size()-1
// 3) формируем результат: leading + reversed words interleaved с spacesAfter (в том же порядке) + trailing
string res;
res.reserve(n);
res.append(leading, ' ');
int m = (int)words.size();
for (int idx = 0; idx < m; ++idx) {
// берем слова с конца: words[m-1], words[m-2], ...
res += words[m - 1 - idx];
if (idx < (int)spacesAfter.size()) {
res.append(spacesAfter[idx], ' ');
}
}
res.append(trailing, ' ');
return res;
}
@algoses
❤6🔥2👍1
Как попробовать себя в аналитике до поступления?
Участвуй в олимпиаде по анализу данных DANO — это настоящий тест-драйв профессии и возможность получить преимущества при поступлении.
А еще:
— библиотека материалов и видеоподкаст о проведении исследований;
— задачи для тренировки в телеграм-канале;
— помощь менторов на заключительном этапе;
— комьюнити амбициозных школьников со всей страны.
Финалисты отправятся на недельный проектный тур в Подмосковье.
Олимпиаду проводят НИУ ВШЭ и Т-Банк, а также вузы-соорганизаторы: УрФУ, ПГНИУ, РЭШ, ИТМО и АГУ.
Подать заявку можно онлайн: ссылка
Реклама. АНО ДПО «Т-Образование», ИНН 7743270426, Erid: 2RanykXKdXP
Участвуй в олимпиаде по анализу данных DANO — это настоящий тест-драйв профессии и возможность получить преимущества при поступлении.
А еще:
— библиотека материалов и видеоподкаст о проведении исследований;
— задачи для тренировки в телеграм-канале;
— помощь менторов на заключительном этапе;
— комьюнити амбициозных школьников со всей страны.
Финалисты отправятся на недельный проектный тур в Подмосковье.
Олимпиаду проводят НИУ ВШЭ и Т-Банк, а также вузы-соорганизаторы: УрФУ, ПГНИУ, РЭШ, ИТМО и АГУ.
Подать заявку можно онлайн: ссылка
Реклама. АНО ДПО «Т-Образование», ИНН 7743270426, Erid: 2RanykXKdXP
❤4🤣3
Задача с собеседования в Яндекс
Даны два массива, состоящих из элементов типа (id, val), отсортированных по неубыванию id Нужно их объединить в один массив, удовлетворяющий следующим условиям
1) В итоговом массиве каждый id входит ровно один раз и элементы массива отсортированы по неубыванию id
2) val, имеющие одинаковые id, суммируются и их сумма будет в итоговом массиве под тем же id
Требуется решение с линейной скоростью и константной памятью
Наш чат алгоритмистов
Решение:
Пройдемся по обоим массивам параллельно, поддерживая текущий айдишник и сумму для него
def merge_sum_list(a: List[Pair], b: List[Pair]) -> List[Pair]:
i = 0
j = 0
na = len(a)
nb = len(b)
res: List[Pair] = []
cur_id: Optional[int] = None
cur_sum: float = 0.0
while i < na or j < nb:
if i < na and (j >= nb or a[i][0] < b[j][0]):
next_id, next_val = a[i]
i += 1
else:
next_id, next_val = b[j]
j += 1
if cur_id is None:
cur_id = next_id
cur_sum = next_val
elif next_id == cur_id:
cur_sum += next_val
else:
res.append((cur_id, cur_sum))
cur_id = next_id
cur_sum = next_val
if cur_id is not None:
res.append((cur_id, cur_sum))
return res
@algoses
Даны два массива, состоящих из элементов типа (id, val), отсортированных по неубыванию id Нужно их объединить в один массив, удовлетворяющий следующим условиям
1) В итоговом массиве каждый id входит ровно один раз и элементы массива отсортированы по неубыванию id
2) val, имеющие одинаковые id, суммируются и их сумма будет в итоговом массиве под тем же id
Требуется решение с линейной скоростью и константной памятью
Наш чат алгоритмистов
Решение:
def merge_sum_list(a: List[Pair], b: List[Pair]) -> List[Pair]:
i = 0
j = 0
na = len(a)
nb = len(b)
res: List[Pair] = []
cur_id: Optional[int] = None
cur_sum: float = 0.0
while i < na or j < nb:
if i < na and (j >= nb or a[i][0] < b[j][0]):
next_id, next_val = a[i]
i += 1
else:
next_id, next_val = b[j]
j += 1
if cur_id is None:
cur_id = next_id
cur_sum = next_val
elif next_id == cur_id:
cur_sum += next_val
else:
res.append((cur_id, cur_sum))
cur_id = next_id
cur_sum = next_val
if cur_id is not None:
res.append((cur_id, cur_sum))
return res
@algoses
❤12
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Поступашки открывают набор на новую линейку математических курсов 🎓
Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
➡️ алгоритмы
➡️ теория вероятностей
➡️ линейная алгебра
➡️ математический анализ
Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что вам реально понадобится! Хочешь конкретики? На нашам сайте можно найти программу, подробности и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты! А если вы выполните все рекомендации, но не достигнете поставленной цели, то вам вернут все потраченные деньги!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что вам реально понадобится! Хочешь конкретики? На нашам сайте можно найти программу, подробности и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты! А если вы выполните все рекомендации, но не достигнете поставленной цели, то вам вернут все потраченные деньги!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Please open Telegram to view this post
VIEW IN TELEGRAM
❤1🔥1
Алгособес ШАД 2025.pdf
216.5 KB
Собеседование по алгоритмам в ШАД 2025
Идут последние 6 часов скидки на нашу новую линейку легендартных курсов. В честь этого события делимся и разбираем задачи в прикрепленном файле с собеса по алгосам 2025 года. Задачи 2023-2024 года ниже, еще больше эксклюзивных задач на наших курсах.
https://t.me/algoses/6
https://t.me/algoses/12
https://t.me/algoses/19
https://t.me/algoses/39
https://t.me/algoses/194
https://t.me/botalkaaa/82748
https://leetcode.com/problems/find-all-anagrams-in-a-string/description/
https://t.me/algoses/137
Никаких изменений с форматом в этом году почти не было, все также одна задача на пол часа, нужно решение и код, но могли быть доп вопросы и как бонус предлагался чужой код на оценку. А вот с форматом по математике были небольшие изменения, о них мы расскажем как только будет 300 огоньков 🔥 на этом посте.
@postypashki_old
Идут последние 6 часов скидки на нашу новую линейку легендартных курсов. В честь этого события делимся и разбираем задачи в прикрепленном файле с собеса по алгосам 2025 года. Задачи 2023-2024 года ниже, еще больше эксклюзивных задач на наших курсах.
https://t.me/algoses/6
https://t.me/algoses/12
https://t.me/algoses/19
https://t.me/algoses/39
https://t.me/algoses/194
https://t.me/botalkaaa/82748
https://leetcode.com/problems/find-all-anagrams-in-a-string/description/
https://t.me/algoses/137
Никаких изменений с форматом в этом году почти не было, все также одна задача на пол часа, нужно решение и код, но могли быть доп вопросы и как бонус предлагался чужой код на оценку. А вот с форматом по математике были небольшие изменения, о них мы расскажем как только будет 300 огоньков 🔥 на этом посте.
@postypashki_old
🔥26❤3
IT начинается здесь ⚡️
Хочешь почувствовать себя настоящим разработчиком? Олимпиада «Высшая проба» — профиль «Промышленное программирование».
Задачи от Яндекса, контакты в IT-среде и шанс влиться в профессию мечты
✅ Успей зарегистрироваться до 20 октября 14:00 (мск):https://olymp.hse.ru/mmo/devcode
Реклама. «Национальный исследовательский университет «Высшая школа экономики» ИНН: 7714030726 ERID: 2W5zFHt4g9E
Хочешь почувствовать себя настоящим разработчиком? Олимпиада «Высшая проба» — профиль «Промышленное программирование».
Задачи от Яндекса, контакты в IT-среде и шанс влиться в профессию мечты
✅ Успей зарегистрироваться до 20 октября 14:00 (мск):https://olymp.hse.ru/mmo/devcode
Реклама. «Национальный исследовательский университет «Высшая школа экономики» ИНН: 7714030726 ERID: 2W5zFHt4g9E
❤1
Задача с собеседования в Яндекс
В функцию подается две строки: s и t, где t это непустой алфавит, состоящий из уникальных символов
Надо найти наикратчайшую подстроку в s такую, что она содержит все символы из алфавита t
Наш чат алгоритмистов
Решение должно быть линейно по времени
Решение:
Для удобства заведем хешмапу для быстрой проверки символа в алфавите и поддержания его индекса
Линейно пройдемся правым указателем по строке, поддерживая количество покрытых символов в алфавите, и двигаем левый указатель вправо, пока наша подстрока удовлетворяет условиям
def min_window_with_alphabet(s: str, t: str) -> str:
if not s:
return ""
k = len(t)
mapping = {ch: i for i, ch in enumerate(t)} # char -> index 0..k-1
need = [1] * k
window = [0] * k
required = k
formed = 0
l = 0
best_len = float('inf')
best_l = 0
for r, ch in enumerate(s):
idx = mapping.get(ch)
if idx is not None:
window[idx] += 1
if window[idx] == 1:
formed += 1
while formed == required and l <= r:
cur_len = r - l + 1
if cur_len < best_len:
best_len = cur_len
best_l = l
left_ch = s[l]
idx_l = mapping.get(left_ch)
if idx_l is not None:
window[idx_l] -= 1
if window[idx_l] == 0:
formed -= 1
l += 1
return "" if best_len == float('inf') else s[best_l: best_l + best_len]
@algoses
В функцию подается две строки: s и t, где t это непустой алфавит, состоящий из уникальных символов
Надо найти наикратчайшую подстроку в s такую, что она содержит все символы из алфавита t
Наш чат алгоритмистов
Решение должно быть линейно по времени
Решение:
Линейно пройдемся правым указателем по строке, поддерживая количество покрытых символов в алфавите, и двигаем левый указатель вправо, пока наша подстрока удовлетворяет условиям
def min_window_with_alphabet(s: str, t: str) -> str:
if not s:
return ""
k = len(t)
mapping = {ch: i for i, ch in enumerate(t)} # char -> index 0..k-1
need = [1] * k
window = [0] * k
required = k
formed = 0
l = 0
best_len = float('inf')
best_l = 0
for r, ch in enumerate(s):
idx = mapping.get(ch)
if idx is not None:
window[idx] += 1
if window[idx] == 1:
formed += 1
while formed == required and l <= r:
cur_len = r - l + 1
if cur_len < best_len:
best_len = cur_len
best_l = l
left_ch = s[l]
idx_l = mapping.get(left_ch)
if idx_l is not None:
window[idx_l] -= 1
if window[idx_l] == 0:
formed -= 1
l += 1
return "" if best_len == float('inf') else s[best_l: best_l + best_len]
@algoses
❤9
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Поступашки продолжают набор на новую линейку математических курсов. Стартуем уже в это воскресение 🎓
Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
➡️ алгоритмы
➡️ теория вероятностей
➡️ линейная алгебра
➡️ математический анализ
Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что вам реально понадобится! Хочешь конкретики? На нашам сайте можно найти программу, подробности и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты! А если вы выполните все рекомендации, но не достигнете поставленной цели, то вам вернут все потраченные деньги!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что вам реально понадобится! Хочешь конкретики? На нашам сайте можно найти программу, подробности и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты! А если вы выполните все рекомендации, но не достигнете поставленной цели, то вам вернут все потраченные деньги!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Please open Telegram to view this post
VIEW IN TELEGRAM
🥱2❤1
Задача с собеседования в Amazon
Дан массив целых чисел. Необходимо посчитать сумму минимумов каждого подмассива исходного массива. Ответ вывести по модулю 1e9
Пример:
[3, 1, 2, 4]
Ответ: 17
Наш чат алгоритмистов
Решение:
Для каждого элемента A[i] посчитать, в скольких подмассивах он будет минимальным. Найдём индекс предыдущего элемента строго меньше (prev) и следующий элемент меньше или равный (next) с помощью монотонного стека. Тогда вклад A[i] в сумму равен A[i] * (i - prev[i]) * (next[i] - i). Время O(n), память O(n).
def sumSubarrayMins(A: List[int]) -> int:
n = len(A)
if n == 0:
return 0
# prev: индекс предыдущего элемента, который строго меньше A[i]
prev = [-1] * n
stack = []
for i in range(n):
while stack and A[stack[-1]] >= A[i]:
stack.pop()
prev[i] = stack[-1] if stack else -1
stack.append(i)
# nxt: индекс следующего элемента, который меньше или равен A[i]
nxt = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and A[stack[-1]] > A[i]:
stack.pop()
nxt[i] = stack[-1] if stack else n
stack.append(i)
res = 0
for i in range(n):
left_count = i - prev[i]
right_count = nxt[i] - i
res = (res + A[i] * left_count * right_count) % MOD
return res
@algoses
Дан массив целых чисел. Необходимо посчитать сумму минимумов каждого подмассива исходного массива. Ответ вывести по модулю 1e9
Пример:
[3, 1, 2, 4]
Ответ: 17
Наш чат алгоритмистов
Решение:
def sumSubarrayMins(A: List[int]) -> int:
n = len(A)
if n == 0:
return 0
# prev: индекс предыдущего элемента, который строго меньше A[i]
prev = [-1] * n
stack = []
for i in range(n):
while stack and A[stack[-1]] >= A[i]:
stack.pop()
prev[i] = stack[-1] if stack else -1
stack.append(i)
# nxt: индекс следующего элемента, который меньше или равен A[i]
nxt = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and A[stack[-1]] > A[i]:
stack.pop()
nxt[i] = stack[-1] if stack else n
stack.append(i)
res = 0
for i in range(n):
left_count = i - prev[i]
right_count = nxt[i] - i
res = (res + A[i] * left_count * right_count) % MOD
return res
@algoses
🤯19❤7🔥6
This media is not supported in your browser
VIEW IN TELEGRAM
Твой шанс прокачаться в ИТ, получить карьерный буст и побороться за призовой фонд 10 250 000 рублей 💰 Успей зарегистрироваться до 20 октября.
МТС приглашает на True Tech Champ — всероссийский чемпионат по программированию. Соревнование будет проходить в двух треках.
Трек 1. Алгоритмический. Индивидуальный зачет [призовой фонд 2 750 000 рублей]
Реши задачи, которые помогут прокачаться в работе с алгоритмами и структурами данных. Похожие задания встречаются на собеседованиях в МТС и других крупных компаниях. До 240 лучших участников попадут в финал и сразятся в лайв-кодинге.
Трек 2. Программирование роботов. Командный формат [призовой фонд 7 500 000 рублей]
Проведи робота по виртуальному лабиринту, затем управляй им дистанционно на офлайн-полигоне, а в финале — пройди испытания на реальной площадке и выбей соперников с платформы. Организаторы отправят командам финалистов по одному роботу Waveshare Cobra Flex для кастомизации. После соревнований они останутся у участников в качестве подарка.
📍 Зрелищный шоу-финал с ИИ-технологиями, кодерскими челленджами и выступлениями международных и российских спикеров пройдет 21 ноября в МТС Live Холл.
🎁 Регистрация участников до 20 октября на сайте.
МТС приглашает на True Tech Champ — всероссийский чемпионат по программированию. Соревнование будет проходить в двух треках.
Трек 1. Алгоритмический. Индивидуальный зачет [призовой фонд 2 750 000 рублей]
Реши задачи, которые помогут прокачаться в работе с алгоритмами и структурами данных. Похожие задания встречаются на собеседованиях в МТС и других крупных компаниях. До 240 лучших участников попадут в финал и сразятся в лайв-кодинге.
Трек 2. Программирование роботов. Командный формат [призовой фонд 7 500 000 рублей]
Проведи робота по виртуальному лабиринту, затем управляй им дистанционно на офлайн-полигоне, а в финале — пройди испытания на реальной площадке и выбей соперников с платформы. Организаторы отправят командам финалистов по одному роботу Waveshare Cobra Flex для кастомизации. После соревнований они останутся у участников в качестве подарка.
📍 Зрелищный шоу-финал с ИИ-технологиями, кодерскими челленджами и выступлениями международных и российских спикеров пройдет 21 ноября в МТС Live Холл.
🎁 Регистрация участников до 20 октября на сайте.
🔥2❤1
Задача с собеседования в AirBnB
Дан массив строк (слов) и максимальная ширина maxWidth.
Вам необходимо отформатировать текст таким образом, чтобы каждая строка содержала ровно maxWidth символов, и была полностью выровнена по ширине (слева и справа)
При необходимости нужно добавлять дополнительные пробелы, чтобы в каждой строке было ровно maxWidth символов. Они должны быть распределены как можно более равномерно. Если количество пробелов в строке неравномерно распределяется между словами, то слева будет больше пробелов, чем справа.
Последняя строка должна быть выровнена по левому краю, а между словами не должно быть лишних пробелов (только для последней строки)
Пример:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Наш чат алгоритмистов
Решение:
Мы жадно упаковываем слова в строку, пока добавление следующего слова (с хотя бы одним пробелом) не превысит max_width, для каждой непоследней строки равномерно распределяем требуемые пробелы по промежуткам (избыточные пробелы даём левым промежуткам), а последнюю строку и строки из одного слова выравниваем по левому краю; реализация проходит по словам один раз и формирует финальные строки, поэтому время работы - O(C+W), где C — суммарное число символов в словах, W — число слов
def fullJustify(self, words: List[str], max_width: int) -> List[str]:
res: List[str] = []
n = len(words)
i = 0
while i < n:
j = i + 1
line_len = len(words[i])
while j < n and line_len + 1 + len(words[j]) <= max_width:
line_len += 1 + len(words[j])
j += 1
line_words = words[i:j]
num_words = j - i
if j == n or num_words == 1:
line = " ".join(line_words)
line += " " * (max_width - len(line))
else:
total_chars = sum(len(w) for w in line_words)
total_spaces = max_width - total_chars
slots = num_words - 1
base_space, extra = divmod(total_spaces, slots)
parts: List[str] = []
for k in range(slots):
parts.append(line_words[k])
parts.append(" " * (base_space + (1 if k < extra else 0)))
parts.append(line_words[-1])
line = "".join(parts)
res.append(line)
i = j
return res
@algoses
Дан массив строк (слов) и максимальная ширина maxWidth.
Вам необходимо отформатировать текст таким образом, чтобы каждая строка содержала ровно maxWidth символов, и была полностью выровнена по ширине (слева и справа)
При необходимости нужно добавлять дополнительные пробелы, чтобы в каждой строке было ровно maxWidth символов. Они должны быть распределены как можно более равномерно. Если количество пробелов в строке неравномерно распределяется между словами, то слева будет больше пробелов, чем справа.
Последняя строка должна быть выровнена по левому краю, а между словами не должно быть лишних пробелов (только для последней строки)
Пример:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Наш чат алгоритмистов
Решение:
def fullJustify(self, words: List[str], max_width: int) -> List[str]:
res: List[str] = []
n = len(words)
i = 0
while i < n:
j = i + 1
line_len = len(words[i])
while j < n and line_len + 1 + len(words[j]) <= max_width:
line_len += 1 + len(words[j])
j += 1
line_words = words[i:j]
num_words = j - i
if j == n or num_words == 1:
line = " ".join(line_words)
line += " " * (max_width - len(line))
else:
total_chars = sum(len(w) for w in line_words)
total_spaces = max_width - total_chars
slots = num_words - 1
base_space, extra = divmod(total_spaces, slots)
parts: List[str] = []
for k in range(slots):
parts.append(line_words[k])
parts.append(" " * (base_space + (1 if k < extra else 0)))
parts.append(line_words[-1])
line = "".join(parts)
res.append(line)
i = j
return res
@algoses
🤯4❤3
VK Education и MAX запустили хакатон, где нужно сделать не просто код, а реально работающий сервис — чат-бот или мини-приложение.
Три трека:
• Цифровизация — автоматизация учебных процессов в вузах;
• Социальный — решения для инклюзии, кибербезопасности, экологии;
• Эффективность — сервисы для управления задачами и рабочими процессами.
Всё проходит по классике:
— Команда 2–3 человека (студенты очной формы);
— Онлайн-отбор и образовательная программа;
— Финал — 30 ноября в Москве.
Финалистов будет 54, победителей — 9.
Общий призовой фонд 3 000 000 руб.
Хорошая возможность собрать команду, прокачать навыки, сделать проект в VK и получить деньги + строчку в CV.
@algoses
Три трека:
• Цифровизация — автоматизация учебных процессов в вузах;
• Социальный — решения для инклюзии, кибербезопасности, экологии;
• Эффективность — сервисы для управления задачами и рабочими процессами.
Всё проходит по классике:
— Команда 2–3 человека (студенты очной формы);
— Онлайн-отбор и образовательная программа;
— Финал — 30 ноября в Москве.
Финалистов будет 54, победителей — 9.
Общий призовой фонд 3 000 000 руб.
Хорошая возможность собрать команду, прокачать навыки, сделать проект в VK и получить деньги + строчку в CV.
@algoses
😁38💊29🗿8❤2🔥2🤷♂1💔1
Задача с собеседования Яндекс
Задача
Даны корни двух бинарных деревьев p и q Нужно проверить совпадают ли деревья Два дерева считаются одинаковыми если они структурно идентичны и значения соответствующих узлов равны
Чат алгоритмистов
Решение
Идем синхронно по обоим деревьям, если оба указателя пустые поддеревья совпадают, если пуст только один деревья различаются, затем сравниваем значения текущих узлов и рекурсивно проверяем левое и правое поддерево если все проверки проходят деревья одинаковые
Время O(n) где n число узлов каждый узел посещаем не более одного раза
Память O(h) для стека рекурсии где h высота дерева в худшем случае O(n) в сбалансированном O(log n)
Код
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true;
}
if (!p || !q) {
return false;
}
return p->val == q->val
&& isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
};
@algoses
Задача
Даны корни двух бинарных деревьев p и q Нужно проверить совпадают ли деревья Два дерева считаются одинаковыми если они структурно идентичны и значения соответствующих узлов равны
Чат алгоритмистов
Решение
Время O(n) где n число узлов каждый узел посещаем не более одного раза
Память O(h) для стека рекурсии где h высота дерева в худшем случае O(n) в сбалансированном O(log n)
Код
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true;
}
if (!p || !q) {
return false;
}
return p->val == q->val
&& isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
};
@algoses
🔥6❤2
ИИ уже стал повседневностью. Но один вопрос остается открытым: кто управляет процессом — человек или алгоритм?
🔥 Уже 24 октября в кампусе СберУниверситета состоится IX конференция «Больше чем обучение». Тема этого года — Homo cogitans (человек думающий).
Это не про технологии. Это про мышление — как главный навык XXI века.
Герман Греф, Ник Шеклтон-Джонс, Александр Каплан, Крейг Винг и другие эксперты обсудят, как развивать интеллект, использовать ИИ осознанно и строить команды, которые думают продуктивнее, чем каждый по отдельности.
На площадке также будет форум ИИ-мастеров, арт-инсталляции, книжная выставка и консультации от экспертов Сбера.
Событие уже завтра. Участие онлайн — бесплатно. Регистрируйтесь!
🔥 Уже 24 октября в кампусе СберУниверситета состоится IX конференция «Больше чем обучение». Тема этого года — Homo cogitans (человек думающий).
Это не про технологии. Это про мышление — как главный навык XXI века.
Герман Греф, Ник Шеклтон-Джонс, Александр Каплан, Крейг Винг и другие эксперты обсудят, как развивать интеллект, использовать ИИ осознанно и строить команды, которые думают продуктивнее, чем каждый по отдельности.
На площадке также будет форум ИИ-мастеров, арт-инсталляции, книжная выставка и консультации от экспертов Сбера.
Событие уже завтра. Участие онлайн — бесплатно. Регистрируйтесь!
❤3
Задача с собеседования в Яндекс
Дан массив prices, где prices[i] — цена акции в день i. Нужно выбрать один день для покупки и позже другой день для продажи так, чтобы прибыль была максимальна. Если прибыли получить нельзя — вернуть 0.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение:
Проходим массив один раз, поддерживая:
min_price — минимальную цену, встреченную слева (лучшая покупка до текущего дня);
best — максимальную прибыль на данный момент.
На каждом шаге обновляем best = max(best, prices[i] - min_price) и затем min_price = min(min_price, prices[i]).
Это даёт O(n) по времени и O(1) по памяти.
Код:
#include <bits/stdc++.h>
using namespace std;
int maxProfit(const vector<int>& prices) {
int min_price = INT_MAX;
int best = 0;
for (int p : prices) {
if (p > min_price) {
best = max(best, p - min_price);
}
min_price = min(min_price, p);
}
return best;
}
@algoses
Дан массив prices, где prices[i] — цена акции в день i. Нужно выбрать один день для покупки и позже другой день для продажи так, чтобы прибыль была максимальна. Если прибыли получить нельзя — вернуть 0.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение:
min_price — минимальную цену, встреченную слева (лучшая покупка до текущего дня);
best — максимальную прибыль на данный момент.
На каждом шаге обновляем best = max(best, prices[i] - min_price) и затем min_price = min(min_price, prices[i]).
Это даёт O(n) по времени и O(1) по памяти.
Код:
using namespace std;
int maxProfit(const vector<int>& prices) {
int min_price = INT_MAX;
int best = 0;
for (int p : prices) {
if (p > min_price) {
best = max(best, p - min_price);
}
min_price = min(min_price, p);
}
return best;
}
@algoses
😁17💊2
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Поступашки продолжают набор на новую линейку математических курсов, в эти выходные стартуют уже первые семинары 🎓
Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
➡️ алгоритмы
➡️ теория вероятностей
➡️ линейная алгебра
➡️ математический анализ
Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что вам реально понадобится! Хочешь конкретики? На нашам сайте можно найти программу, подробности и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты! А если вы выполните все рекомендации, но не достигнете поставленной цели, то вам вернут все потраченные деньги!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:
Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что вам реально понадобится! Хочешь конкретики? На нашам сайте можно найти программу, подробности и отзывы на каждый курс.
Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты! А если вы выполните все рекомендации, но не достигнете поставленной цели, то вам вернут все потраченные деньги!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Please open Telegram to view this post
VIEW IN TELEGRAM
🤣2❤1
На Хабре опубликовали любопытный материал: энтузиаст провёл соревнование по алгоритмическому программированию на C/C++ под «Эльбрусы» (e2k) с 31 студентом со всей России в онлайн-формате, разыграв свои личные 215 тысяч рублей, и описывает весь процесс — от идеи до проведения финала. А теперь планирует всё повторить в марте 2026 года: https://habr.com/ru/articles/959742/
👍11❤4🔥1🙉1
Задача с собеседования в Amazon
Дана строка s. Разбить s так, чтобы каждая подстрока разбиения была палиндромом. Вернуть все возможные разбиения строки на палиндромы.
Пример:
Input: s = "aab"
Output: [["a","a","b"], ["aa","b"]]
|s| <= 16
Наш чат алгоритмистов
Решение:
Самое простое решение
Используем рекурсивный возврат с откатом:
1. На каждом шаге пробуем все возможные подстроки, начиная с текущей позиции
2. Если подстрока является палиндромом — добавляем её в текущий путь и рекурсивно продолжаем с оставшейся частью строки
3. Когда достигаем конца строки — сохраняем текущее разбиение
4. Откатываемся и пробуем другие варианты
Это даёт O(n × 2^n) по времени (2^(n-1) возможных разбиений, для каждого O(n) на проверку) и O(n) по памяти для стека рекурсии.
def partition(s: str) -> List[List[str]]:
def is_palindrome(string: str) -> bool:
return string == string[::-1]
def backtrack(start: int, path: List[str]) -> None:
if start == len(s):
result.append(path[:])
return
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
if is_palindrome(substring):
path.append(substring)
backtrack(end, path)
path.pop()
result = []
backtrack(0, [])
return result
Оптимизация:
Можно предварительно вычислить все палиндромы с помощью DP за O(n²), чтобы потом проверять их за O(1). Но для |s| <= 16 рекурсии достаточно
@algoses
Дана строка s. Разбить s так, чтобы каждая подстрока разбиения была палиндромом. Вернуть все возможные разбиения строки на палиндромы.
Пример:
Input: s = "aab"
Output: [["a","a","b"], ["aa","b"]]
|s| <= 16
Наш чат алгоритмистов
Решение:
Используем рекурсивный возврат с откатом:
1. На каждом шаге пробуем все возможные подстроки, начиная с текущей позиции
2. Если подстрока является палиндромом — добавляем её в текущий путь и рекурсивно продолжаем с оставшейся частью строки
3. Когда достигаем конца строки — сохраняем текущее разбиение
4. Откатываемся и пробуем другие варианты
Это даёт O(n × 2^n) по времени (2^(n-1) возможных разбиений, для каждого O(n) на проверку) и O(n) по памяти для стека рекурсии.
def partition(s: str) -> List[List[str]]:
def is_palindrome(string: str) -> bool:
return string == string[::-1]
def backtrack(start: int, path: List[str]) -> None:
if start == len(s):
result.append(path[:])
return
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
if is_palindrome(substring):
path.append(substring)
backtrack(end, path)
path.pop()
result = []
backtrack(0, [])
return result
Оптимизация:
Можно предварительно вычислить все палиндромы с помощью DP за O(n²), чтобы потом проверять их за O(1). Но для |s| <= 16 рекурсии достаточно
@algoses
🔥6❤2🤔1
Media is too big
VIEW IN TELEGRAM
Стать лучшими программистами мира среди студентов 🏆
В сентябре это удалось команде студентов факультета математики и компьютерных наук СПбГУ, когда они стали абсолютными чемпионами мира по программированию ICPC World Finals.
Ребята решили 11 из 12 задач, оставив позади всех конкурентов, включая команды MIT, Stanford, Гарварда и еще 135 лучших университетов мира.
Вся команда чемпионов получила приглашение на работу в Сбер. Им предложили присоединиться к созданию передовых технологий, включая разработку мультиагентных систем на базе GigaChat в рамках GenAI-трансформации банка.
В сентябре это удалось команде студентов факультета математики и компьютерных наук СПбГУ, когда они стали абсолютными чемпионами мира по программированию ICPC World Finals.
Ребята решили 11 из 12 задач, оставив позади всех конкурентов, включая команды MIT, Stanford, Гарварда и еще 135 лучших университетов мира.
Вся команда чемпионов получила приглашение на работу в Сбер. Им предложили присоединиться к созданию передовых технологий, включая разработку мультиагентных систем на базе GigaChat в рамках GenAI-трансформации банка.
От олимпиадных алгоритмов — к технологиям для миллионов пользователей.
🥱24❤18👍5🔥4😁4
Задача с собеседования в Amazon
Реализовать структуру данных MapSum, которая поддерживает две операции:
-
-
Пример:
Работать должно линейно по времени
Наш чат алгоритмистов
Решение:
Будем использовать бор - префиксное дерево, где каждый узел хранит сумму всех значений с данным префиксом:
1. При вставке ключа вычисляем дельту (разницу между новым и старым значением)
2. Проходим по дереву вдоль символов ключа, создавая узлы при необходимости
3. В каждом узле увеличиваем значение на дельту
4. При запросе суммы просто идём по дереву до конца префикса и возвращаем значение узла
Дельта нужна для корректной обработки обновлений: если
Это даёт O(k) по времени для обеих операций (где k — длина ключа/префикса) и O(n × k) по памяти (где n — количество ключей).
class TrieNode:
def init(self):
self.children = {}
self.value = 0
class MapSum:
def init(self):
self.root = TrieNode()
self.map = {} # Храним текущие значения для обработки обновлений
def insert(self, key: str, val: int) -> None:
delta = val - self.map.get(key, 0)
self.map [key] = val
node = self.root
for char in key:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.value += delta
def sum(self, prefix: str) -> int:
node = self.root
for char in prefix:
if char not in node.children:
return 0
node = node.children[char]
return node.value
Можно использовать просто словарь и при каждом
@algoses
Реализовать структуру данных MapSum, которая поддерживает две операции:
-
insert(key, val) — вставить пару ключ-значение (или обновить значение, если ключ существует), key - строка, val - целое число-
sum(prefix) — вернуть сумму всех значений, ключи которых начинаются с заданного префиксаПример:
mapSum.insert("apple", 3)
mapSum.sum("ap") // return 3
mapSum.insert("app", 2)
mapSum.sum("ap") // return 5 (apple + app = 3 + 2)Работать должно линейно по времени
Наш чат алгоритмистов
Решение:
1. При вставке ключа вычисляем дельту (разницу между новым и старым значением)
2. Проходим по дереву вдоль символов ключа, создавая узлы при необходимости
3. В каждом узле увеличиваем значение на дельту
4. При запросе суммы просто идём по дереву до конца префикса и возвращаем значение узла
Дельта нужна для корректной обработки обновлений: если
apple было 3, а стало 7, то во все узлы пути добавляем +4.Это даёт O(k) по времени для обеих операций (где k — длина ключа/префикса) и O(n × k) по памяти (где n — количество ключей).
class TrieNode:
def init(self):
self.children = {}
self.value = 0
class MapSum:
def init(self):
self.root = TrieNode()
def insert(self, key: str, val: int) -> None:
delta = val - self.map.get(key, 0)
node = self.root
for char in key:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.value += delta
def sum(self, prefix: str) -> int:
node = self.root
for char in prefix:
if char not in node.children:
return 0
node = node.children[char]
return node.value
sum() перебирать все ключи с помощью startswith(). Это даст O(1) для insert и O(n) для sum, что проще в реализации, но менее эффективно при частых запросах сумм.@algoses
❤7🗿5