Задача с собеседования в Яндекс
Дан массив 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
❤20💅4🔥2🤨1
Задача с собеседования в Яндекс
Дана скобочная грамматика: в круглых скобках записано выражение, следом за ними идут квадратные скобки с неотрицательным целым числом. Разворачивается в виде конкатенации строки в круглых скобках на саму себя N раз, где N - число в квадратных скобках
Чуть более формально, грамматика -
term ::= a-z*
term ::= (term)[\d+]
term ::= term1term2 - разворачивается в конкатенацию двух выражений
На вход подается строка со скобочным выражением. Необходимо развернуть его в строку и вернуть. Предлагается считать, что скобочная последовательность на входе всегда корректна
Примеры:
"ab" -> "ab"
"(ab)[3]" -> "ababab"
"((ab)[2])[2]" -> "abababab"
"(a)[2](b)[2]" -> "aabb"
"()[1]bc" -> "bc"
Наш чат алгоритмистов
Решение:
Аккуратная рекурсия
def parse_expression(s: str) -> str:
def helper(i):
res = ""
while i < len(s):
if s[i] == '(':
# Рекурсивно разбираем внутреннее выражение
inner, i = helper(i + 1)
# После этого должен идти [
assert s[i] == '[', f"Ожидалась [ на позиции {i}, а найдено {s[i]}"
i += 1
num_start = i
while s[i].isdigit():
i += 1
repeat = int(s[num_start:i])
assert s[i] == ']', f"Ожидалась ] на позиции {i}, а найдено {s[i]}"
i += 1
res += inner * repeat
elif s[i] == ')':
return res, i + 1
else:
res += s[i]
i += 1
return res, i
result, _ = helper(0)
return result
Подводные камни:
1) выход за границы строки при разборе, неточное вычленение содержимого подвыражений в скобках
2) остаются куски грамматики в выводе
3) некорректно парсится число в квадратных скобках, если имеет более одного разряда - например, парсится задом наперед или только один разряд
@algoses
Дана скобочная грамматика: в круглых скобках записано выражение, следом за ними идут квадратные скобки с неотрицательным целым числом. Разворачивается в виде конкатенации строки в круглых скобках на саму себя N раз, где N - число в квадратных скобках
Чуть более формально, грамматика -
term ::= a-z*
term ::= (term)[\d+]
term ::= term1term2 - разворачивается в конкатенацию двух выражений
На вход подается строка со скобочным выражением. Необходимо развернуть его в строку и вернуть. Предлагается считать, что скобочная последовательность на входе всегда корректна
Примеры:
"ab" -> "ab"
"(ab)[3]" -> "ababab"
"((ab)[2])[2]" -> "abababab"
"(a)[2](b)[2]" -> "aabb"
"()[1]bc" -> "bc"
Наш чат алгоритмистов
Решение:
def parse_expression(s: str) -> str:
def helper(i):
res = ""
while i < len(s):
if s[i] == '(':
# Рекурсивно разбираем внутреннее выражение
inner, i = helper(i + 1)
# После этого должен идти [
assert s[i] == '[', f"Ожидалась [ на позиции {i}, а найдено {s[i]}"
i += 1
num_start = i
while s[i].isdigit():
i += 1
repeat = int(s[num_start:i])
assert s[i] == ']', f"Ожидалась ] на позиции {i}, а найдено {s[i]}"
i += 1
res += inner * repeat
elif s[i] == ')':
return res, i + 1
else:
res += s[i]
i += 1
return res, i
result, _ = helper(0)
return result
Подводные камни:
1) выход за границы строки при разборе, неточное вычленение содержимого подвыражений в скобках
2) остаются куски грамматики в выводе
3) некорректно парсится число в квадратных скобках, если имеет более одного разряда - например, парсится задом наперед или только один разряд
@algoses
❤3🔥3👍1
Задача с собеседования в Яндекс
Дана следующая структура мероприятий, имеющих временное начало и конец
Необходимо найти пересекающиеся встречи
Наш чат алгоритмистов
Решение:
Сортируем встречи по времени начала, затем проходим слева направо, поддерживая наибольший правый конец max_end среди уже просмотренных интервалов и индекс того интервала, который даёт max_end. Если следующий интервал начинается раньше max_end, то он пересекается с каким-то предыдущим (в частности — с тем, чьё max_end), помечаем оба как пересекающиеся. В конце возвращаем (или выводим) все исходные встречи, помеченные как пересекающиеся.
Код:
vector<Meeting> crossing(const vector<Meeting>& meetings) {
int n = (int)meetings.size();
if (n == 0) return {};
// Соберём (from, to, orig_index) и отсортируем по from
struct Node { long long from, to; int idx; };
vector<Node> v;
v.reserve(n);
for (int i = 0; i < n; ++i) v.push_back({meetings[i].from, meetings[i].to, i});
sort(v.begin(), v.end(), [](const Node& a, const Node& b) {
if (a.from != b.from) return a.from < b.from;
return a.to < b.to ;
});
vector<char> overlapped(n, 0); // пометки для исходных индексов
long long max_end = v[0].to;
int idx_max_sorted = 0; // индекс в v, который даёт max_end
// Считаем, что пересечение происходит если start < max_end (строгое пересечение).
// Если нужно считать касание по границе пересечением, менять на <= .
for (int i = 1; i < n; ++i) {
if (v[i].from < max_end) {
// v[i] пересекается с тем, у кого max_end
overlapped[v[i].idx] = 1;
overlapped[v[idx_max_sorted].idx] = 1;
}
if (v[i].to > max_end) {
max_end = v[i].to;
idx_max_sorted = i;
}
}
// Собираем результат в исходном порядке
vector<Meeting> res;
for (int i = 0; i < n; ++i) {
if (overlapped[i]) res.push_back(meetings[i]);
}
return res;
}
Время O(NlogN), память O(N)
@algoses
Дана следующая структура мероприятий, имеющих временное начало и конец
struct Meeting {
long long from;
long long to;
}
vector<Meeting> crossing(const vector<Meeting>& meetings) ...Необходимо найти пересекающиеся встречи
Наш чат алгоритмистов
Решение:
Код:
int n = (int)meetings.size();
if (n == 0) return {};
// Соберём (from, to, orig_index) и отсортируем по from
struct Node { long long from, to; int idx; };
vector<Node> v;
v.reserve(n);
for (int i = 0; i < n; ++i) v.push_back({meetings[i].from, meetings[i].to, i});
sort(v.begin(), v.end(), [](const Node& a, const Node& b) {
if (a.from != b.from) return a.from < b.from;
return
});
vector<char> overlapped(n, 0); // пометки для исходных индексов
long long max_end = v[0].to;
int idx_max_sorted = 0; // индекс в v, который даёт max_end
// Считаем, что пересечение происходит если start < max_end (строгое пересечение).
// Если нужно считать касание по границе пересечением, менять на <= .
for (int i = 1; i < n; ++i) {
if (v[i].from < max_end) {
// v[i] пересекается с тем, у кого max_end
overlapped[v[i].idx] = 1;
overlapped[v[idx_max_sorted].idx] = 1;
}
if (v[i].to > max_end) {
max_end = v[i].to;
idx_max_sorted = i;
}
}
// Собираем результат в исходном порядке
vector<Meeting> res;
for (int i = 0; i < n; ++i) {
if (overlapped[i]) res.push_back(meetings[i]);
}
return res;
}
Время O(NlogN), память O(N)
@algoses
❤5🔥2
Задача с собеседования в Яндекс
Написать функцию, которая меняет порядок слов в строке на противоположный, при этом не меняя расположение пробелов
Например: __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
❤7🔥2👍1
Задача с собеседования в Яндекс
Даны два массива, состоящих из элементов типа (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
❤13
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://news.1rj.ru/str/algoses/6
https://news.1rj.ru/str/algoses/12
https://news.1rj.ru/str/algoses/19
https://news.1rj.ru/str/algoses/39
https://news.1rj.ru/str/algoses/194
https://news.1rj.ru/str/botalkaaa/82748
https://leetcode.com/problems/find-all-anagrams-in-a-string/denoscription/
https://news.1rj.ru/str/algoses/137
Никаких изменений с форматом в этом году почти не было, все также одна задача на пол часа, нужно решение и код, но могли быть доп вопросы и как бонус предлагался чужой код на оценку. А вот с форматом по математике были небольшие изменения, о них мы расскажем как только будет 300 огоньков 🔥 на этом посте.
@postypashki_old
Идут последние 6 часов скидки на нашу новую линейку легендартных курсов. В честь этого события делимся и разбираем задачи в прикрепленном файле с собеса по алгосам 2025 года. Задачи 2023-2024 года ниже, еще больше эксклюзивных задач на наших курсах.
https://news.1rj.ru/str/algoses/6
https://news.1rj.ru/str/algoses/12
https://news.1rj.ru/str/algoses/19
https://news.1rj.ru/str/algoses/39
https://news.1rj.ru/str/algoses/194
https://news.1rj.ru/str/botalkaaa/82748
https://leetcode.com/problems/find-all-anagrams-in-a-string/denoscription/
https://news.1rj.ru/str/algoses/137
Никаких изменений с форматом в этом году почти не было, все также одна задача на пол часа, нужно решение и код, но могли быть доп вопросы и как бонус предлагался чужой код на оценку. А вот с форматом по математике были небольшие изменения, о них мы расскажем как только будет 300 огоньков 🔥 на этом посте.
@postypashki_old
🔥26❤3
Задача с собеседования в Яндекс
В функцию подается две строки: 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
❤11
Задача с собеседования в 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
🤯20❤7🔥6
Задача с собеседования в 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
❤5🤯4
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
Задача с собеседования в Яндекс
Дан массив 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
😁18❤2💊2
Задача с собеседования в 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
Задача с собеседования в 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
❤9🗿7
Стартовал «Технокубок» 2025/26
VK, МФТИ и МГТУ им. Н. Э. Баумана открыли регистрацию на олимпиаду по программированию для школьников 8–11 классов. Победители могут поступить в вузы без экзаменов или получить 100 баллов за ЕГЭ по информатике — для этого участникам предстоит пройти три этапа:
➡️ Два независимых отборочных онлайн-раунда — они 16 ноября и 7 декабря на платформе All Cups. Будет засчитан лучший результат из двух.
➡️ Очный отбор 8 февраля на площадках вузов-партнеров.
➡️ Финал пройдет 13-15 марта в Москве.
Участникам предстоит решать задачи по программированию от партнеров олимпиады и сервисов VK на различных языках — C++, Python, Java, C#, Kotlin и других.
Формат остался прежним, код писать придется самому 😎. На платформе VK Education есть бесплатная программа для подготовки к таким соревнованиям — обучение и тренировки в решении задач на курсе «Старт в олимпиадном программировании» бесплатные.
@algoses
VK, МФТИ и МГТУ им. Н. Э. Баумана открыли регистрацию на олимпиаду по программированию для школьников 8–11 классов. Победители могут поступить в вузы без экзаменов или получить 100 баллов за ЕГЭ по информатике — для этого участникам предстоит пройти три этапа:
Участникам предстоит решать задачи по программированию от партнеров олимпиады и сервисов VK на различных языках — C++, Python, Java, C#, Kotlin и других.
Формат остался прежним, код писать придется самому 😎. На платформе VK Education есть бесплатная программа для подготовки к таким соревнованиям — обучение и тренировки в решении задач на курсе «Старт в олимпиадном программировании» бесплатные.
@algoses
Please open Telegram to view this post
VIEW IN TELEGRAM
❤5
Задача с собеседования в МТС
Условие задачи
Вы начинаете в точке (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