Алгоритмы - Собеседования, Олимпиады, ШАД

Задача в Авито

Дан массив целых чисел и число k. Нужно вернуть k наиболее встречающиеся по частоте элементы.

Пример:
1 1 1 2 2 3
2
Вывод: 1 2

Решение:
Будем хранить частоту чисел в хеш-мапе, перенесем в вектор пары (частота, элемент), найдем K-ую порядковую статистику и отберем элементы с частотой >= пороговой

vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int num : nums) freq[num]++;

vector<pair<int, int>> elements;
for (auto& [num, count] : freq)
elements.emplace_back(count, num);

auto kth = elements.begin() + k - 1;
nth_element(elements.begin(), kth, elements.end(),
[](auto& a, auto& b) { return a.first > b.first; });

int threshold = kth->first;
vector<int> result;
for (auto& [count, num] : elements)
if (count > threshold)
result.push_back(num);

for (auto& [count, num] : elements)
if (count == threshold && result.size() < k)
result.push_back(num);

return result;
}

Асимптотика О(N)

Кто не понял, это была проверка на адекватность

@algoses

По многочисленным просьбам разбираем 7ую задачу со стажировки в Т-банк. Код уже здесь.

@ProdAnalysis

Вот и разбор алгоримтов на стажировку в Тинькофф! Коды тут. Разобрали первые 3 задачи, а разбор оставшихся будет только на нашем майском экспресс курсе по алгоритмам.
Будьте очень внимательны к ответам ChatGPT, на этот раз задачи составлены таким образом, чтобы обмануть нейросеть. Тех, кто воспользуется таким решением, система будет банить (это не байт).

@postypashki_old

Задача в Авито

Дан массив целых чисел и число k. Нужно вернуть k наиболее встречающиеся по частоте элементы.

Пример:
1 1 1 2 2 3
2
Вывод: 1 2

Решение:
Будем хранить частоту чисел в хеш-мапе, затем пушаем в массив пары из элемента и сколько он встречался. Сортируем массив и выводим первые k. лол всё

vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (auto el : nums)
cnt[el]++;

vector<pair<int, int>> arr;
for (const auto & [key, value] : cnt)
arr.emplace_back(value, key);
sort(arr.rbegin(), arr.rend());

vector<int> ans;
for (int i = 0; i < k; ++i)
ans.push_back(arr[i].second);
return ans;
}

Асимптотика O(NlogN) в худшем случае

Если наши решение лучше, не стесняемся писать в комментарии

@algoses

Т-банк открыл контест на летнюю стажировку. Задания уже лежат тут, там же их можно обсудить вместе с админом. И конечно разбор соответствующих контестов будет на нашем курсе по АВ тестам и экспресс курсе по алгоритмам как приятный бонус, так что присмотритесь к ним.

Стажировка в Т-банке - самая крупная стажировка после Яндекса по количеству мест. В целом решает не сколько баллы за экзамены, сколько "ваш социальный рейтинг", анкета — подробней смотрим здесь. После контестов зовут на собес: он дикая халява, если хоть немного пробовали вкатиться в специальность.

@postypashki_old

Задача в Т-Банк

Даны n комнат, пронумерованных от 0 до n - 1. Изначально все комнаты, кроме 0-ой, заперты. Ваша цель - посетить все комнаты. Однако, вы не можете посетить комнату, не имея ключа, открывающую её.
Когда вы посещаете комнату, вы можете найти какое-то множество различных ключей, используя которые, вы можете пройти в другие комнаты.
Для каждой комнаты вам известно, какие ключи в ней находятся. Вы должны ответить, можно ли посетить все n комнат, или нет

Решение:
Построим ориентированный граф, в котором вершинами будут комнатами, а ребро из u в v будет означать, что в комнате u есть ключ для комнаты v.
Таким образом, можно обойти граф обходом в глубину из вершины 0, пометить все вершины, куда можно добраться, и в конце проверить, помечены ли все вершины.

vector<char> used;
vector<vector<int>> g;

void dfs(int v) {
used[v] = true;
for (auto u : g[v])
if (!used[u])
dfs(u);
}

bool canVisitAllRooms(vector<vector<int>>& rooms) {
int n = (int)rooms.size();
used.resize(n);
g = rooms;

dfs(0);

for (int i = 0; i < n; ++i) {
if (!used[i])
return false;
}
return true;
}

Асимптотика O(N)

@algoses

Визуализация данных: как превратить цифры в истории.

Данные — это новая нефть. Но без правильной визуализации они остаются просто цифрами в таблице. Давайте разберём, как делать графики, которые не просто красивые, но и действительно полезные.

Пять принципов эффективной визуализации

1. Выбирайте правильный тип графика
- Тренды → Линейный график (matplotlib, plotly)
- Сравнение → Столбчатая диаграмма (seaborn)
- Доли → Круговая или кольцевая диаграмма (но только если сегментов <5!)
- Распределение → Гистограмма или boxplot

2. Убивайте "мусор"
Уберите лишние линии, 背景色 и анимации, если они не несут смысла.
Используйте минималистичные темы

3. Цвет — ваш союзник (или враг)
Для категорий: Пастельные тона (например, #66c2a5, #8da0cb).
Для акцентов: Яркий цвет (один!), например, красный для негатива.
Проверка: Распечатайте график в ЧБ — если всё читаемо, вы молодец.

4. Аннотации решают всё
Добавляйте подписи к выбросам

5. Интерактивность ≠ сложность

Для дашбордов: Plotly или Tableau.
Простой пример:

import plotly.express as px
fig = px.bar(df, x='город', y='доход', color='месяц', title='Доход по городам')
fig.show()

⚙ Инструменты
Python: Matplotlib, Seaborn, Plotly.
BI: Tableau, Power BI, Metabase.
Быстрые правки: Canva для презентаций.

📌 Правило: Хорошая визуализация — та, после которой не остаётся вопросов.

🎓 Напоминаем, у поступашек открыта запись на курс по А/Б тестированию!

@ProdAnalysis

Выкладываем все задания отборочного этапа ШАД 2025 года! Сегодня последний день, чтобы подать заявку! Отбор получился самым сложным за все время, чтобы обмануть сомнительный интеллект.

Это им удалось, чатгпт выдает что-то неадекватное. Надеяться можно только на наши курсы, где УЖЕ ВЫЛОЖЕН РАЗБОР ШАДА 2025 года. Разбор только на наших курсах, только сегодня (4 мая) скидка 30%!

@postypashki_old

Ещё задача в Amazon

Даны две бинарные строки a и b, нужно их сложить))

Пример
a = "11", b = "1"
a + b = "100"

Длины строк от 1 до 10^5

Решение:
От такой задачи разрешается подпрыгнуть от радости на собеседовании, громко ударить кулаком об стол, закричать ОЧЕВ и отключиться от собеседования

По символьно считываем строки, складываем символы и поддерживаем добавляемое значение в следующий разряд. ВСЁ

string addBinary(string a, string b) {
if (a.size() > b.size())
swap(a, b);

int n = (int)a.size(), m = (int)b.size();
if (n < m) {
a = string(m - n, '0') + a;
n = m;
}

string res;
int pred = 0;
for (int i = n - 1; i >= -1; --i) {
if (i == -1 && pred == 0) break;

int d1 = 0, d2 = 0;
if (i > -1) {
d1 = a[i] - '0';
d2 = b[i] - '0';
}

if (d1 + d2 == 2) {
res += (pred ? "1" : "0");
pred = 1;
} else if (d1 + d2 == 1) {
res += (pred ? "0" : "1");
} else {
res += (pred ? "1" : "0");
pred = 0;
}
}

reverse(res.begin(), res.end());

return res;
}

Решение за O(N)

@algoses

Поступашки продолжают набор на курс по дискретной математике!

Мечтаешь поступить в ШАД или магистратуру? Или просто хочешь тащить собесы, но не хватает фундамента? Тогда тебе к нам!

На курсе будет разобрана специфика задач, ВСЕ идеи и подходы, используемые составителями. А также тебя ждёт пробный экзамен!

Как всегда лекции со всей необходимой систематизированной теорией, семинары (на которых вы не просто сидите в чате, а имеете возможность отвечать, как на живом уроке), домашние задачи, разбор домашних задачек, куратор и еще куча всяких плюшек!

Цена самая доступная: 6000р 4500р за курс, при покупке на одного человека.
Сегодня и завтра отдаем курс по скидке, со среды (мск) продажа идет по зачеркнутой цене.
При покупке любого курса серии дискретная математика обойдет в 3500р. (скидки не суммируются).
А при покупке двух и более курсов серии сегодня и завтра, дискретная математика в подарок!

Начинаем уже в эту пятницу! Первые лекции уже доступны, поэтому торопитесь.

После семинара доступна запись. Кураторы помогут заполнить анкету, помогут в абсолютно в любом вопросе, задаче. Вас ждет пробный экзамен, разбор реального контеста ШАДа 2025 года и персональное собеседование, как в ШАДе! А также разведка по каждому экзамену, инсайды и персональные рекомендации.

Программа и Подробности.

Для записи и вопросов: @menshe_treh

Также не забываем про другие курсы к ШАД и магистратурам

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

Дан указатель на первый элемент связного списка. Нужно циклически сдвинуть список на k позиций.
Структура связного списка определяется следующим образом:
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};

Пример:
Список [1, 2, 3, 4, 5], k = 2
Вывод: [4, 5, 1, 2, 3]

0 <= N <= 500 - количество элементов в списке
0 <= k <= 2*10^9

Решение:
В первую очередь заметим, что k может быть очень большим, поэтому, очевидно, что можем сделать k %= N.

Идея очень простая: каждый раз будем брать последний элемент в списке, пометим для него следующим головной, а для предыдущего next сделаем пустым. Для удобного поддержания последнего в сдвиге элемента будем использовать дек, в который пушаем в начало текущую голову.

Также незабываем обработать крайние случаи
1) Пустой список
2) Список, состоящий из 1 элемента

ListNode* rotateRight(ListNode* head, int k) {
if (!head)
return nullptr;

deque<ListNode*> d;
d.push_back(head);

ListNode* cur = head->next;
while (cur) {
d.push_back(cur);
cur = cur->next;
}

if (d.size() == 1)
return head;

k %= (int)d.size();

while (k--) {
ListNode* last = d.back();
d.pop_back();
ListNode* predlast = d.back();

predlast->next = nullptr;
last->next = head;
d.push_front(last);
head = last;
}

return head;
}

Решение за O(N)

@algoses

Поступашки объявляют запись на майские экспресс курсы к отборочным ШАДа!

Вы в целом понимаете как работать почти со всеми темами, но что-то все равно западает? Вы хотите отточить свои навыки решения задач до бритвенной остроты в кратчайшие сроки и научиться оформлять на полный балл? Хотите провести майские выходные с пользой? Тогда майский интенсив - это то, что вам нужно! Лекции со всей необходимой систематизированной теорией, семинары (на которых вы не просто сидите в чате, а имеете возможность отвечать, как на живом уроке), домашние задачи, разбор домашних задачек, куратор Владислав, который готовит в ШАД десяток лет, все что может вам потребоваться для полной подготовки к первому, второму этапу и собеседованию!
Цены самые доступные:

- алгоритмы (6000 5000 за весь курс)
- дискретная математика (6000 5000 за весь курс)
- теория вероятностей (6000 5000 за весь курс)
- линейная алгебра (6000 5000 за весь курс)
- математический анализ (6000 5000 за весь курс)

Сегодня и завтра отдаем интенсивы по скидке, с субботы (мск) продажа идет по зачеркнутой цене.

Начинаем уже в это воскресение! Первые лекции уже доступны, поэтому торопитесь

После семинара доступна запись. В роли куратора сам Владислав, который поможет заполнить анкету, поможет в абсолютно в любом вопросе, задаче. В конце курса вас ждет пробный экзамен, разбор реального контеста ШАДа 2025 года и персональное собеседование, как в ШАДе! А также разведка по каждому этапу, инсайды и персональные рекомендации.

Программа и Подробности.

Записаться и задать вопросы можно тут: @menshe_treh

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

Есть 2 взаимодействующие системы. Одна из них - БД хранящая информацию о пользователях, вторая - использует эту информацию для принятия решения. Пользователи обычно используют систему периодами (сессиями), и в рамках сессии делают много запросов. Между сессиями достаточно большой промежуточный интервал. Хочется сэкономить ресурсы БД и повторяющиеся запросы по возможности не выполнять заново, а выдавать уже запомненный где-то результат.

Необходимо реализовать класс кеша. Класс должен иметь метод для получения данных по ключу, метод для вставки данных. Ограничение на максимальное количество элементов (или размер потребляемой памяти).

Решение:
Покумекав, поразмыслив, в конце вы должны прийти к выбору LRU-кеша
Код класса (по-хорошему надо писать шаблонную реализацию)
template <class Key,
class T,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, T>> >
class LRU;

Со сложностью вставки\поиска за O(1)
Методы:

const_iterator find(const Key& key) const;
iterator find(const Key& key) const;
std::pair<iterator, bool> insert(const Key& key, const T& val);
По аналогии с STL контейнерами

@algoses

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

Дана прямоугольная матрица, заполненная нулями и единицами. Единицы это земля, нули это вода. Из каждой ячейки, заполненной 1, можно попасть в другую ячейку с 1, если каждая из их координат отличается не более, чем на единицу, т.е. каждая ячейка имеет до 8 соседей

Требуется найти количество таких "островов" в матрице

Решение:

Ну вот и ещё одна халявка в бигтех, такое будет стыдно слить на собесе
Заметим, что "острова" это всего лишь компоненты связности в графе, где вершины это ячейки в матрице, а ребра это возможность перейти из одной ячейки в другую. То есть ребра будут между всеми соседними единичками.

Так как теперь их посчитать? Запускаем дфс из каждой единичной ячейки, если до этого она не посещалась, дфс обходит все вершинки из острова, отмечает их посещенными и увеличивает счетчик компонент связности, вот и всё.
Решение за O(NM)

@algoses

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

Для заданной строки найти длину наибольшей подстроки без повторяющихся символов.
Например:
abcabcbbddee -> 3 (abc)
bbbbb -> 1 (b)
pwwkew -> 3 (wke)

Решить желательно за линию

Решение:

Решение сложнее O(N) - плохо
С двумя проходами по строке - нормально
С одним проходом по строке - хорошо

Для каждой позиции будем находить самую длинную подстроку, заканчивающуюся в данной позиции. Если мы нашли ответ для позиции i (обозначим за P[i]) - легко посчитать ответ для позиции i + 1: для этого надо найти самое правое вхождение символа S[i+1] в префиксе S[1...i] и взять максимум из найденной позиции и P[i].
Если символов мало, то последнее вхождение каждого символа можно поддерживать в массиве, иначе его стоит хранить в hash_map (это важно уточнить у собеседующего)
Решение за O(N)

Также не забываем в реализации проверить
1) Работу на пустой строке и строке из одного символа
2) Ответ для любой непустой строки хотя бы 1

@algoses

Методы обнаружения выбросов (Часть 1)

В этой части речь будет идти про статистические методы. В основном эти методы подходят, когда данные распределены нормально.

📌 Z-оценка

Метод Z-Score определяет выбросы, измеряя отклонение точки данных от среднего значения в единицах стандартного отклонения. Если Z-Score

(Z = (x - mean) / sd, где x - точка данных, mean - среднее значение, sd - стандартное отклонение)

точки оказывается значительно выше или ниже нуля, это означает, что она сильно отличается от большинства данных и может считаться выбросом. Этот метод особенно эффективен для данных с нормальным распределением, где основная масса значений сосредоточена вокруг среднего.

📌 Interquartile Range (IQR)

Посчитаем разницу между первым и третьим квантилем (то есть возьмём средние 50% данных и разницу между максимальным и минимальным) - это значение называется IQR, а теперь рассчитаем нижнюю и верхнюю границы

(Q1 - 1.5 * IQR, Q3 + 1.5 * IQR)

коэффициент можно брать на своё усмотрение. Все данные, которые не попадут в эти границы - выбросы. Этот метод является более устойчивым к экстремальным значениям.

📌 Критерий Граббса

Важно, что этот критерий требует нормальность, поэтому предварительно нужно проверить (например с помощью Шапиро-Уилка), также этот критерий предназначен для обнаружения одного выброса. Затем считаем статистику Граббса:

G = max(|x_i - X_mean|) / sd
X_mean - среднее значение, sd - среднее отклонение

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

@ProdAnalysis

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

Нужно написать функцию normalize, которая принимает на вход юниксовый путь и выдает его нормализованный вариант (схлопываются слеши, обрабатываются все возможные точки).
Каталоги разделяются слэшами (/). Подряд может идти несколько слэшей ( /// ). Если указан символ точка "." - это означает текущую папку. Если указано два символа точки подряд ".." - это означает ссылку на родительскую папку. Требуется получить нормализованное представление

Примеры:
In: /foo/bar//bax/asdf/quux/..
Out: /foo/bar/bax/asdf

In: a/../../b
Out: ../b

In: /a/../../b
Out: /b

Решение:
Изейшая задачка на стек
Если встречаем несколько слэшей, при этом до этого слэш был, то игнорим их. Если встречаем имя папки, пушаем её. Если встречаем две точки, то попаем последний элемент в стеке (и проверяем перед этим, что он не пуст, иначе пушаем две точки)

def normalize(path: str) -> str:
if not path:
return "."

is_absolute = path.startswith('/')
parts = []

for part in path.split('/'):
if part == '' or part == '.':
continue
elif part == '..':
if parts and parts[-1] != '..':
parts.pop()
else:
if not is_absolute:
parts.append(part)
else:
parts.append(part)

normalized_path = '/'.join(parts)

if is_absolute:
normalized_path = '/' + normalized_path

if not normalized_path:
return '/' if is_absolute else '.'

return normalized_path

Асимптотика O(N)

@algoses

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

Имеется n пользователей, каждому из них соответствует список e-mail-ов (всего m). Например:

user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru
user2 -> foo@gmail.com, ups@pisem.net
user3 -> xyz@pisem.net, vasya@pupkin.com
user4 -> ups@pisem.net, aaa@bbb.ru
user5 -> xyz@pisem.net

Считается, что если у двух пользователей общий email, значит, это один и тот же пользователь.

Требуется реализовать алгоритм, выполняющий слияние пользователей. На выходе должен быть список пользователей с их e-mail-ами (такой же как на входе). В качестве имени можно брать любое из исходных имен. Список e-mail-ов должен содержать уникальные e-mail-ы. Параметры n и m произвольные.

В указанном примере ответ будет такой
user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru, ups@pisem.net, aaa@bbb.ru
user3 -> xyz@pisem.net, vasya@pupkin.com

Нужно решение с линейной асимптотикой

Решение:
Довольно стандартная задача
Построим граф на пользователях такой, что два пользователя лежат в одной компоненте связности тогда и только тогда, когда они должны быть объединены в одного пользователя. Для этого используем хеш-мапу: для каждого e-mail-а список пользователей.
Соединим последовательно цепочкой этих пользователей друг с другом в графе. Граф будет иметь размер порядка O(n + m). После этого найдем в графе компоненты связности и восстановим по ним ответ на задачу

Итоговая асимптотика O(n + m)

@algoses

Задача с HFT компании.

Задача встретилась у одного ученика на собеседование в HFT.
Сразу скажу, задача сложнее, чем Яндекс-задачи.

Дается массив целых чисел a и число k.
Значения подмасива [l, r] будем считать как (r-l+1)*min(a[l], a[l+1], ..., a[r]).
(То есть значения подмасива - это длина массива на минимальное число из подотрезка)

Вы имеете право рассматривать подотрезок [l, r] если l <= k <= r (напомню k дали в инпуте). Найти максимальное значение.

Решение:
Давайте переберем позицию i, и предположим это минимальный элемент какого-то подотрезка.
То есть мы говорим что a[i] минимальное число на каком-то подотрезке [L, R], где L <= k <= R и L <= i <= R.

Значит значения этого подотрезка это a[i] * (R - L + 1). Какие L, R нужно брать для зафиксированного i?
Вам нужно найти минимальный L, и максимальный R что в подотрезке [L, R] число a[i] минимальное.

Если мы для каждой позиции i будем знать L, R то мы сможем найти ответ. Ответ просто max(a[i] * (R[i] - L[i] + 1)), при условии что
L[i] <= k <= R[i].

Теперь поговорим, как же все-таки эти отрезки находить для каждой позиции i.

Эти отрезки мы можем посчитать монотонными стеками. Сначала пройдем слева направо, храня возрастающий монотонный стек.

Когда мы пытаемся добавить число a[i] в стек, мы удаляем сколько-то элементов, замечу, что для этих удаляемых позиций правая граница будет как раз таки i.

То есть мы, когда удаляем число из стека, мы понимаем, что для удаляемого элемента правый отрезок — это i.

Аналогично пройдемся справа налево и посчитаем левые границы.

Решение O(n). Если на собесе решали не за линию то засчитывали фейл.


Код в комментариях.

@algoses

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

Дан некоторый алфавит и строка. Необходимо найти в строке панграмму минимальной длины, где панграмма - это такая подстрока исходной строки, в которую входят все буквы из алфавита (но необязательно только они).

Пример:
A = {a, b, c}
s = "dfagabkaceb"
Ответом могут быть строки "bkac" и "aceb"

Решение:
Халявные два указателя буквально подарят тебе оффер
Будем двигать правый указатель, расширяя подстроку, пока не включим все символы из алфавита. Как только все символы оказались в окне, будем двигать левый указатель, обновляя ответ и сохраняя все необходимые символы.
Обязательно надо проверить, что панграмма с концом в конце исходной строки также рассматривается.
Асимптотика O(N)

В целом, можно предложить алгоритм без сдвига начала строки за O(NS), что тоже прокатит
Типичные ошибки:
1) Не обработать ненахождение панграммы в принципе
2) Неправильно похендлить алфавит длиной один
3) Ненахождение ответа в конце текста

@algoses