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

Дана прямоугольная матрица, заполненная нулями и единицами. Единицы это земля, нули это вода. Из каждой ячейки, заполненной 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

Поступашки открывают набор на курс по теории вероятностей и математической статистики для тех, кто поступает в Академию Аналитиков Авито!

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

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

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

Цена самая доступная: 9000 р за курс.

Начинаем уже 1 июня!

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

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

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

Задача для пориджей с собеседования в Яндекс

Дан массив целых чисел, нужно найти непустой подотрезок (непрерывную подпоследовательность) с заданной суммой X, либо сказать, что это невозможно.

Для найденного отрезка (если он существует) следует выдать на выход индексы его концов.

Решение:

Частичные суммы, далее два варианта:
1) Сортировка / std::map, решение за O(nlogn)
2) Хешмапа, решение за O(N)

unordered_map<long long, int> sum_map;
sum_map[0] = -1;
long long sum = 0;

for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
auto it = sum_map.find(sum - X);
if (it != sum_map.end()) {
return {it->second + 1, i};
}
if (!sum_map.count(sum)) {
sum_map[sum] = i;
}
}

return {-1, -1};

Что нужно учитывать:
1) В массиве могут быть отрицательные числа
2) Подотрезок должен быть непустой

Хорошо, если вы скажете про переполнение и что перфиксная сумма может не поместиться в int

Итоговое решение O(N)

@algoses

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

Вполне себе прикладная задача, которая может встретиться в проде.
Поисковая формулировка: для двух поисковых выдач, заданных массивами DocId-ов (векторы целых чисел) длины N, для всех k от 1 до N нужно посчитать количество общих документов в топах размера k.

Формальная формулировка: Для двух массивов целых чисел длины N, для всех k от 1 до N, посчитать количество общих чисел на префиксах длины k. Числа в пределах массива могут повторяться, пересечение считается без учета кратности.

Решение:

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

int n = A.size();
vector<int> result(n);
unordered_set<int> setA, setB;
int common = 0;

for (int i = 0; i < n; ++i) {
int a = A[i];
int b = B[i];

if (!setA.count(a)) {
setA.insert(a);
if (setB.count(a)) {
common++;
}
}

if (!setB.count(b)) {
setB.insert(b);
if (setA.count(b)) {
common++;
}
}

result[i] = common;
}

Если повторы внутри одного вектора запрещены, то возможно решение с одним хешсетом всех встреченных элементов двух массивов
Нужно отдельно обговорить допускаем ли мы повторы чисел внутри одного вектора. Хорошо, если вы сами спросите об этом на собесе

В результате решение O(N)

@algoses

Задача H ШАД 2025

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

Условие задачи
На отрезке [0, L] (координата L ≤10^6) множество точек.
Всегда присутствуют концы 0 и L. Поддерживаются запросы:
1.добавить новую точку X;
2.удалить существующую точку X;
3.вывести среднее по всем расстояниям между двумя точками в множестве

Разбор
Для начала выведем формулу среднего, answer = Sum / Binom(n, 2) = Sum*2 / (n * (n - 1)) (Binom(n, 2) - это количество возможных пар расстояний, а Sum - сумма по всем расстояниям в паре). В таком случае наша задача сводится к быстрому поддержанию суммы Sum.
Рассмотрим как меняется значение Sum при изменении в точке X (например добавления, а случай удаления абсолютно так же считается, просто учитывается с противоположным знаком).
Все точки слева внесут вклад в сумму равный count(x[i] < X) * X - sum(x[i] | x[i] < X) (то есть мы просто сумму разниц разложим на разницу сумм (сумма элементов X и сумма всех элементов, которые левее, обозначим sum_left), правая сумма вычисляется по аналогичной логике.
delta_S = count(x[i] < X) * X - sum_left + sum_rigtht - count(x[i] > X) * X
Суммы (sum_left, sum_right) и количества (count) мы можем вычислять с помощью структур за O(log L) (например фенвик либо ДО и т п). Далее попробуем оптимизировать эту асимптотику, хотя log L и так достаточно для решения данных ограничений. Считаем все запросы, запомним, а координаты все когда либо использованных значений сожмем (воспользуемся идеями сжатися координат), это позволит нам асимптотику O(log q). Соответственно итоговая асимптотика будет O(qlog q).

@algoses