Задача с собеседования в лабораторию Т-банка

Задача:
Нам даны две последовательности 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

Задача с собеса Авито

На вход дана строка, требуется вернуть строку отсортированную по частоте встречаемости символов.


Ограничения:
- длина строки от 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

Задача с собеседования в Яндекс

Дан массив целых чисел 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

Задача с собеседования Яндекс

Задача 
Дана последовательность 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

Задача с собеседования в Яндекс

Дано бинарное дерево (не поиска):
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

Один день из жизни стажера-аналитика в Т-банке

Выпускника прошлых потоков наших продвинутых курсов, на которые идут последние часы 50% скидки, не упусти свой шанс забрать разбор Т-банка и уже осенью получить заветный оффер.

Мой рабочий день начинается с планирования. Первым делом я проверяю календарь и список задач. Сегодня запланирована важная встреча с наставником, так что я принимаю решение поехать в офис — там коммуникация с командой эффективнее. Офис Т-банка расположен в центре Москвы, на Белорусской, что очень удобно: рядом сразу две станции метро и ветки МЦД.

Обычно, когда езжу в офис, я начинаю день с зала. Для сотрудников здесь доступен полноценный клуб с тренажерным залом, там есть всё и кардио, и все популярные тренажеры, и залы для групповых занятий. После тренировки сходил в баню и с отличным настроением пошел, встретился коллег-стажеров с нашего потока - мы обсудили подготовку к предстоящему ИТ-пикнику.

К 11:00 я уже сел за свое рабочее место. Изучил бэклог и расставляю приоритеты на день. Моя главная цель на стажировке - выполнить все задачи для последующего перевода в штат. Сегодня в фокусе - продолжение работы над ML-моделью для классификации клиентов из сегмента малого и среднего бизнеса. Это нужно для автоматизации работы с бизнесами и выявления некорректной регистрации бизнесов. После приоритизации задач, заглянул в кофе поинт позавтракать. Здесь всегда есть кофе, чай, свежие фрукты и выпечка. Это хорошая возможность на несколько минут переключиться и пообщаться с коллегами из других отделов. Затем наконец сел за решение задачи, покопался в подборе параметров модели для разметки бизнесов, получилось улучшить скор и сел дописывать тест в другой задаче, там были проблемы с мощностью теста и бадди посоветовал использовать cuped.

Около 13:00 отправляюсь в столовую. Для сотрудников организовано полноценное бесплатное питание (шведский стол). Выбрал котлеты, гречку, крем-суп и салат с моцареллой. Как мне кажется система бесплатной столовой получше решение, чем 1000 рублей в день на рестораны (еды значительно больше, ну и столовая в т-банке вкуснее).

В 13:30 у меня созвон с наставником. Мы проводили еженедельную оценку работы, проделанной на стажировке, он дает мне советы: я докладываю о прогрессе по модели, обсуждаю проблемные места и получаю обратную связь. Наставник отмечает, что я успешно справился с предыдущей задачей по классификации, и ставит новую - с дизайном АБ.

Вторая половина дня уходит на подготовку и запуск A/B-теста для нового сценария взаимодействия с клиентами малого бизнеса. Мне нужно проверить гипотезу, что измененная механика отправки email-уведомлений увеличит конверсию в отклик. В начале сегментировал клиентскую базу и сформировао тестовую и контрольную группы. Особое внимание уделяю исключению пересечений с другими текущими экспериментами в банке. К концу дня мне удается подготовить код для запуска теста, но дашборд сделать не успел.

В 17:30 рабочий день кончился и пошёл перед уходом поиграл с товарищем в настольный теннис.

@postypashki_old

Задача с собеседования в Яндекс

Дан массив 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

Задача с собеседования в Яндекс

Дана скобочная грамматика: в круглых скобках записано выражение, следом за ними идут квадратные скобки с неотрицательным целым числом. Разворачивается в виде конкатенации строки в круглых скобках на саму себя 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

Задача с собеседования в Яндекс

Дана следующая структура мероприятий, имеющих временное начало и конец

struct Meeting {
    long long from;
    long long to;
}

vector<Meeting> crossing(const vector<Meeting>& meetings) ...

Необходимо найти пересекающиеся встречи

Наш чат алгоритмистов

Решение:
Сортируем встречи по времени начала, затем проходим слева направо, поддерживая наибольший правый конец 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

Задача с собеседования в Яндекс

Написать функцию, которая меняет порядок слов в строке на противоположный, при этом не меняя расположение пробелов
Например: __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

Задача с собеседования в Яндекс

Даны два массива, состоящих из элементов типа (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

Собеседование по алгоритмам в ШАД 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

Задача с собеседования в Яндекс

В функцию подается две строки: 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

Задача с собеседования в 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

Задача с собеседования в 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

VK Education и MAX запустили хакатон, где нужно сделать не просто код, а реально работающий сервис — чат-бот или мини-приложение.

Три трека:
• Цифровизация — автоматизация учебных процессов в вузах;
• Социальный — решения для инклюзии, кибербезопасности, экологии;
• Эффективность — сервисы для управления задачами и рабочими процессами.

Всё проходит по классике:
— Команда 2–3 человека (студенты очной формы);
— Онлайн-отбор и образовательная программа;
— Финал — 30 ноября в Москве.
Финалистов будет 54, победителей — 9.

Общий призовой фонд 3 000 000 руб.

Хорошая возможность собрать команду, прокачать навыки, сделать проект в VK и получить деньги + строчку в CV.

@algoses

Задача с собеседования Яндекс

Задача
Даны корни двух бинарных деревьев 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

Задача с собеседования в Яндекс

Дан массив 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

Задача с собеседования в 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

Задача с собеседования в Amazon

Реализовать структуру данных 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()
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

Можно использовать просто словарь и при каждом sum() перебирать все ключи с помощью startswith(). Это даст O(1) для insert и O(n) для sum, что проще в реализации, но менее эффективно при частых запросах сумм.

@algoses