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

Условие:
Определим понятие хорошей последовательности - абсолютная разница между любыми двумя элементами этой последовательности должна быть больше либо равна максимальному элементу. То есть (i, j) | a_i - a_j | > max(a[l:r+1]). Вам даётся массив длины 10^5 и требуется определить наибольшую длину хорошей подпослдеовательности.

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

Решение:
Очевидно, что если в подпоследовательности будет больше двух положительных элементов, то x - y > x (x = max(x, y)) верно лишь в том случае, когда y < 0. Соответственно длина последовательности будет точно хотя бы равняться количеству отрицательных элементов. При построении последовательности возьмем один положительный элемент (потому что иначе с двумя положительными не будет выполняться условие |a_i - a_j| > max(a_i, a_j) и возьмем жадно аименьший положительный. Тогда можно будет проверить, получится ли этот положительный элемент добавить в последовательность отрицательных так чтобы не нарушалось то условие (для этого достаточно перебрать наименьшую абсолютную разницу, то есть просто перебрать пары соседних в отсортированном порядке).


int n;
cin >> n;
vector<int> a(n);
int ans = 0;
for (int i = 0; i < n; i++ ){
cin >> a[i];
ans += (a[i] <= 0);
}
sort(a.begin(), a.end());
int mn = inf;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
mn = min(a[i], mn);
}
}
bool flag = (mn != inf);
for (int i = 1; i < n; i++) {
if (a[i] <= 0) {
flag &= (a[i] - a[i - 1] >= mn)
}
}
cout << ans + flag;

@algoses

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

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

Яндекс открывает набор в бесплатные олимпиадные Кружки по программированию, искусственному интеллекту и математике

В этом году, помимо Кружка по олимпиадному программированию для школьников 6–11 классов, впервые открываются направления по искусственному интеллекту (8–11 классы) и олимпиадной математике (5–11 классы).

Обучение во всех Кружках бесплатное и доступно онлайн и офлайн. Занятия ведут опытные преподаватели: победители олимпиад, тренеры сборных и члены жюри. В программу обучения входят лекции, семинары с разбором задач и пробные олимпиадные туры. Успешное прохождение курса поможет занять призовые места на олимпиадах, что значительно повысит шансы на поступление в вуз.

Выпускники курса по программированию уже составляют большинство победителей и призеров Всероссийской олимпиады.

Обучение бесплатное. Успейте подать заявки: до 3 сентября — на математику и до 30 сентября — на ИИ. Занятия стартуют осенью 2025 года

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

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