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

Имеется 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

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

Нужно написать функцию 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

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

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

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

Решение:

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

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

@algoses

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

Есть 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

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

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

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

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

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

После семинара доступна запись. В роли куратора сам Владислав, который поможет заполнить анкету, поможет в абсолютно в любом вопросе, задаче. В конце курса вас ждет пробный экзамен, разбор реального контеста ШАДа 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р 4500р за курс, при покупке на одного человека.
Сегодня и завтра отдаем курс по скидке, со среды (мск) продажа идет по зачеркнутой цене.
При покупке любого курса серии дискретная математика обойдет в 3500р. (скидки не суммируются).
А при покупке двух и более курсов серии сегодня и завтра, дискретная математика в подарок!

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

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

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

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

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

Ещё задача в 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

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

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

@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

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

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

@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

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

@postypashki_old

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

@ProdAnalysis

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

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

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

Василию на день рождения подарили массив билет в кино. Билет был необычный: Василий мог сесть на любое место в зале, на которое захочет. Так как в кино крутили Барби, то весь зал был переполнен, кроме одного ряда. На каждом месте в ряду известно, сидит ли человек или нет. Известно, что в этом ряду сидит хотя бы один человек и свободно хотя бы одно место, чтобы Василий смог сесть.
Василий не любит людей... Он хочет сесть на такое место, чтобы расстояние до ближайшего человека было максимальным. Помогите ему в этом

Дан массив, состоящий из 0 и 1: свободно или занято место соответственно
Верните максимальное расстояние до ближайшего человека из возможных

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

Не забываем про крайние случаи при преподсчете: для последних сидений может не быть ближайшего справа занятого сидения и для самых левых ближайшего слева. Так как мы берем минимум из расстояний, то можно просто ставить 2n + 1 и -2n-1 в дефолтные значения ближайших правых и левых занятых сидений соответственно.

int maxDistToClosest(vector<int>& seats) {
int n = (int)seats.size();

vector<int> clRight(n);
for (int i = n - 1; i >= 0; --i) {
if (seats[i])
clRight[i] = i;
else {
if (i != n - 1)
clRight[i] = clRight[i + 1];
else clRight[i] = 2 * n + 1;
}
}

int ans = 0, clLeft = -2 * n - 1;
for (int i = 0; i < n; ++i) {
int dist = min(i - clLeft, clRight[i] - i);
ans = max(ans, dist);

if (seats[i])
clLeft = i;
}

return ans;
}

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

@algoses

Вот и задание вчерашней олимпиады.
Как прошло, товарищи? Давайте 500 шэров и делаем разбор.

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

@matesha_shad

Задача в Яндекс

Дана строка символов. Найти количество пар индексов i и j (i <= j), между которыми включительно нет повторяющихся символов.

Пример
aba -> 5

Решение:
Проходимся один раз по строке с запоминанием последней слева позицией символа и просто считаем ответ.

Типичные ошибки
1) Последняя позиция используется как есть, тогда как строка без повторений может начаться только со следующего символа
2) Используется последняя позиция для текущего символа, а не самая правая позиция последнего повторяющегося символа. В итоге в строке типа "baab" подстрока "aab" будет ошибочно считаться неимеющей повторов

int countUniqueSubstrings(const string& s) {
unordered_map<char, int> last_pos;
int left = 0;
int result = 0;

for (int right = 0; right < s.size(); ++right) {
char current_char = s[right];
if (last_pos.find(current_char) != last_pos.end() && last_pos[current_char] >= left) {
left = last_pos[current_char] + 1;
}

last_pos[current_char] = right;
result += (right - left + 1);
}
return result;
}

@algoses