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

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

Наконец то встретилась новая задача, которая к тому же есть на литкоде.

Дается массив a. Вы стоите на самой левой позиции и хотите попасть на самую последнюю позицию.
Когда вы стоите на позиции i, вы можете прыгнуть максимум на a[i] позиций вперед.
Вернуть true если можно с левого края попасть на правый край.

Пример
3, 1, 2, 0, 0, 4.
Ответ false.

Решение:
От i той позиции мы можем прыгнуть на любую позицию из [i, a[i]+i]. Будем воспринимать это как отрезок.
Тогда у нас получается n отрезков. Они между собой как то пересекаются.

Если два отрезка пересекается это означает что вы можете попасть на любую позицию на объединение отрезков.

Вам надо слить отрезки и убедиться что в одном отрезки находится позиция 0 и позиция n-1.

Слить все отрезки мы можем за О(n), так как отрезки отсортированы по первому числу. (кстати задача про сливания отрезков это старая задача Яндекса)
Ссылка в комментариях.

@algoses

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

Дан список ненулевой длины, состоящий из направлений
L - left
R - right
D - down
U - up
Каждый элемент перемещает вас на 1 в заданном направлении.

Известно, что петли (возврат в уже посещенную точку) дают нулевое перемещение и являются пустой тратой времени. Нужно удалить из списка все петли и вернуть оптимизированный короткий маршрут, например:
[R, D, L, U, R] -> [R]
[R, D, L, R, U, U, R] -> [R, U, R]

Важно отметить, что цель не просто попасть в ту же самую конечную точку, но и придерживаться первоначального маршрута (не срезать по прямой):
[D, R, U] -> [D, R, U]

Вернуть нужно массив направлений.
Ограничения: O(N) по времени и памяти

Решение:

Большинство придумывают решение, в котором складывается текущая координата в хэшмапу. Как только попадаем в ситуацию, когда точка есть, смотрим, какая позиция, и удаляем все до текущей точки. Это неидеальное решение - при удалении можно случайно сделать квадрат, вырезать лишнее и тд и пр, короче решение не очень

Решение по-лучше - есть хешсет (unordered_set) с посещенными координатами и список координат. Как только видим, что в хешсете что-то есть, отступаем по списку, пока не найдем ту самую координату, по пути очищая хешсет. Поиск в хешсете это O(1), поэтому получаем линию по времени и памяти. Просто и быстро, но мало кто догадывается на собесе

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

Третье хорошее решение - есть хешмапа и вектор посещенных точек. В хешмапе храним ласт индекс точки в векторе

Стоит сказать, что решения не уникальны - если идти с конца, можно получить другое решение

@algoses

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

Дано дерево:

struct Node {
    Node *l, *r;
    int value;
}

Требуется написать функцию, которая проверяет, является ли дерево симметричным

Решение:

Будем рекурсивно спускаться в детей и проверять у каждого узла наличие ребенка. Если у какого-то ребенка есть путь вниз, а у другого нет, то дерево не является симметричным. Также параллельно в спуске будем проверять симметричность значений value

bool isSymmetric(Node* root) {
return root == NULL ? true : isMirrored(root->l, root->r);
}

bool isMirrored(Node* a, Node* b) {
if (a == NULL && b == NULL)
return true;

if (a != NULL && b != NULL)
return a->value == b->value && isMirrored(a->l, b->r) && isMirrored(a->r, b->l);

return false;
}

@algoses

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

Дана строка, нужно вывести для каждого символа в ней максимальное количество непрерывных повторений этого символа в строке
Например, для строки "aafbaaaaffc" ответом будет
a: 4
b: 1
c: 1
f: 2

Решение:
Ещё одна халявка из яндекса, которую ты обязан решить с прочтения
Линейно пройдемся по строке, поддерживая счетчик, и будем проверять, совпадает ли текущий символ с предыдущим. Если да, то обновляем счетчик, иначе обновляем ответ в словаре

def countSymbs(s):
d = {}
prev = ''
cnt = 1
for char in s:
if char == prev:
cnt += 1
else:
if prev and d.get(prev, 0) < count:
d[prev] = count
count = 1
prev = char

if prev and d.get(prev, 0) < count:
d[prev] = count

return d

assert countSymbs('aafbaaaaffc') == {'a': 4, 'b': 1, 'c': 1, 'f': 2}

@algoses

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

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

AAABCCCCCDD -> A3BC5D2

Ещё надо выдавать ошибку, если на вход приходит недопустимая строка.

Решение:
Просто пройдемся линейно по строке, считаем, сколько раз встречался символ и сохраняем результат во второй строке.
Казалось бы, примитивная задача, но в ней по невнимательности или из-за стресса допускают ошибки. Будет обидно, если именно ты завалишь такую элементарную задачу

Типичные ошибки:
1) забыл проверить наличие одного символа
2) забыл вывод последней группы
3) забыл сгенерировать ошибку

Тест-кейсы, которые обязательно будет прогонять проверяющий:
1) пустая строка
2) 1 символ или 2 разных символа
3) последовательность из 9 или более одинаковых символов
4) недопустимая строка

@algoses

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

Точка равновесия массива
Дан массив целых чисел. Найдите в нем такой индекс, что сумма элементов слева от него равна сумме элементов справа от него.
Важно решить задачу за O(N) времени и за O(1) памяти.

Решение:
Предварительно посчитаем сумму всего массива
Потом пройдемся по массиву, поддерживая левую сумму, и будем сравнивать её с правой суммой (вся сумма - левая сумма - текущий элемент)

Удовлетворительным решением будет использование частичных левых и правых сумм (но это O(N) памяти)

Плохим решением будет вложенный цикл с подсчетом правых сумм на каждом шаге (уже не O(N) времени очев)

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

@algoses

Новая задача Яндекса:
Дается массив целых чисел. Найти максимальный по длине подотрезок в котором сумма четная.
На самом деле эта задача очень похожа на старую задачу яндекса (задача 974. Subarray Sums Divisible by K на литкоде).
Решить без дополнительной памяти.

Решение:
Если бы можно было использовать доп память то посчитали префиксную сумму. В таком случае сумма на подотрезке четная если prefix_sum[r] - prefix_sum[l-1]) имеют одинаковую четность.

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

Давайте хранить две переменные:
first_odd_pos: позиция где в первый раз увидели нечетную сумму префикса
first_odd_pos: позиция где в первый раз увидели четную сумму префикса

идем слева направо по массиву циклом i и поддерживаем сумму (sum). Если сумма четная то пытаемся обновить i-first_odd_pos, иначе через i-first_odd_pos.
PS: Мы сохраняем только первое вхождение потоому-что хотим максимизировать подотрезок

Время работы O(n)

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

@algoses

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

Дан массив целых чисел nums и целое число target. Нужно найти такую тройку чисел в массиве с различными индексами, что их сумма наиболее близка к target.
Вывести необходимо сумму трех чисел.

Пример

Ввод: nums = [-1,2,1,-4], target = 1
Вывод: 2         (-1 + 2 + 1 = 2)

Input: nums = [0,0,0], target = 1
Output: 0

Решение:
Пусть нужно найти тройку i, j, k (i != j != k), у которой nums[i] + nums[j] + nums[k] == target
Отсортируем массив, будем поддерживать наилучшую сумму и минимальную разницу между этой суммой и target
Переберем циклом указатель i, инициализируем j = i + 1, k = n - 1 и пока j < k каждый раз будем проверять:
- если текущая сумма равна target, то выводим ответ и заканчиваем
- если сумма меньше target, то двигаем j вправо
- иначе двигаем k влево
Сохраняем минимальную разницу, если она меньше, чем была, то сохраняем сумму

Асимптотика O(n^2)

@algoses

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

Даны два массива A и B. Нужно найти минимум abs(A[i] - B[j])

Пример:

A = {0}, B = {1}
Ответ: 1

A = {10, 0, 2}, B = {5, 100, 12}
Ответ: 2

Нужно решение без дополнительной памяти.

Решение:
Отсортируем массивы, далее поставим указатель i на начало A, j на начало B.
Для текущего i будем двигать j вправо до тех пор, пока значение abs(A[i] - B[j]) будет уменьшаться.
Иначе сдвинем i вправо и повторим алгоритм.

Можно привести решение с lower-upper_bound, но это зачтут как минус. На собесе хотят увидеть параллельный проход

Также заметим, что если A = {INT_MAX}, B = {-1}, то ответ не поместится в int.

Решение из-за сортировки получается O(nlogn)
Если в условии массивы изначально отсортированы, то O(n)

@algoses

Вот и разбор программирования на стажировку в Т-банк! Обязательно делимся с друзьями. Ждем 5 тыс просмотров на ролике и выкладываем разбор математики! Кстати а разбор контеста на стажировку в Яндекс будет только на наших курсах.

Смотрим! Смотрим! https://youtu.be/G72BCifHF_Y

Задача с зарубежной компании.
Дается матрица размера n*n. Вы стоите на верхней левой координате, и хотите попасть на правую нижнюю (то есть от (1, 1) в (n, n)).
На матрице стоят числа 0 или 1. За одну операцию можно перейти в соседнюю координату заплатив стоимость, равную значению на позиции.
За какую минимальную стоимость можно попасть в (n, n) от (1, 1)?

Пример:
n = 4
[0, 1, 0, 0]
[0, 0, 0, 0]
[0, 1, 1, 0]
[1, 1, 1, 0]
Ответ 0
Решение:

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

Тогда всего лишь нужно найти кратчайшие расстояния от одной вершины к другой. Подумали об алгоритме Дейкстры?
К сожалению, такое решение не приняли.

Нужно решить за O(n*n), можно ли решить с помощью BFS?
Вообще обычным BFS задачу решить не получится, так как BFS не учитывает вес ребер, а учитывает просто количество ребер, как мы видим минимальное количество ребер не всегда оптимальный путь.

Есть так называемый BFS 0-1, нам всего лишь нужно добавлять в начало очереди те вершины на ребре которых написано 0, и в конец очереди если на ребре стоит 1.
Таким образом BFS в первую очередь будет идти по ребру веса 0, а когда нет возможности то уже по весу 1.


Вопрос на подумать, а можно ли масштабировать такой алгоритм и перестать использовать Дейкстру?

@algoses

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

Даны два отсортированных массива nums1 и nums2 длиной n и m соответственно, необходимо найти их медиану.
Если n + m нечетное, то медианой будет элемент по середине, иначе это среднее двух элементов.

Пример:

nums1 = [1,3], nums2 = [2]
Ответ: 2.00000

nums1 = [1,2], nums2 = [3,4]
Ответ: 2.50000

Существуют решения за O((n + m)*log(n + m)), O(n + m) и O(log(n + m))
По-хорошему, нужно найти O(log(n + m))

Решение:
O((n + m) * log(n + m)) - очевидно
O(n + m) - сливаем два массива за линию (они же отсортированные) и находим медиану

Найдем за O(log(n + m))

Идея следующая: чтобы найти медиану двух массивов, нужно найти такие два элемента в двух массивах, чтобы все элементы слева от этих двух элементов были меньше каждого элемента справа. Это делается бинарным поиском.
Предположим, что первый массив меньше. Если первый массив больше, то поменяйте массивы местами, чтобы убедиться, что первый массив меньше.
В этом алгоритме мы в основном используем два набора, выполняя двоичный поиск в меньшем массиве. Пусть mid1 - это разбиение меньшего массива. Первый набор содержит элементы от 0 до (mid1 – 1) из меньшего массива и элементы mid2 = ((n + m + 1) / 2 – mid1) из большего массива, чтобы убедиться, что в первом наборе ровно (n+m+1)/2 элемента. Второй набор содержит оставшиеся половинки элементов.
Наша цель - найти точку в обоих массивах таким образом, чтобы все элементы в первом наборе были меньше, чем все элементы в элементах другого набора (набора, который содержит элементы с правой стороны).

double medianOf2(vector<int> &a, vector<int> &b) {
int n = a.size(), m = b.size();
if (n > m)
return medianOf2(b, a);

int lo = 0, hi = n;
while (lo <= hi) {
int mid1 = (lo + hi) / 2;
int mid2 = (n + m + 1) / 2 - mid1;

int l1 = (mid1 == 0 ? INT_MIN : a[mid1 - 1]);
int r1 = (mid1 == n ? INT_MAX : a[mid1]);

int l2 = (mid2 == 0 ? INT_MIN : b[mid2 - 1]);
int r2 = (mid2 == m ? INT_MAX : b[mid2]);

if (l1 <= r2 && l2 <= r1) {
if ((n + m) % 2 == 0)
return (max(l1, l2) + min(r1, r2)) / 2.0;
else
return max(l1, l2);
}
if (l1 > r2)
hi = mid1 - 1;
else
lo = mid1 + 1;
}
return 0;
}

@algoses

Стажировка в Авито (Аналитика)

Прикрепляю тестовое задание, давайте 500 шэров (поделиться с другом) и делаем разбор.
Еще больше тестовых заданий и инсайдов на нашем курсе по аналитике.

@zadachi_ds

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

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

@postypashki_old

Задача с фронтенд Яндекс.

Вы находитесь на левой верхней клетке шахматной доски и хотите добраться до правой нижней. У вас есть возможность двигаться вправо, вниз и по диагонали вниз. При этом запрещено три раза подряд перемещаться по клеткам одного цвета.

Сколько существует путей, чтобы попасть из левой верхней клетки в правую нижнюю?

Решение:
Заметим, что при движении по диагонали вниз мы всегда попадаем на клетки одинакового цвета. Следовательно, мы не можем двигаться по диагонали более одного раза подряд.

Если бы не было возможности двигаться по диагонали, задача была бы стандартной динамической.

Пусть dp[i][j][0] обозначает количество способов добраться до позиции (i, j), при этом последнее движение было вправо или вниз. А dp[i][j][1] — количество способов, когда последнее движение было по диагонали.

В таком случае в позицию (i, j, 0) мы можем попасть из следующих позиций:

(i-1, j, 0); (i-1, j, 1);
(i, j-1, 0); (i, j-1, 1).

А на позицию (i, j, 1) мы можем попасть только из (i-1, j-1, 0).

Теперь, когда мы понимаем все переходы и состояния динамического программирования, ответом будет сумма dp[n-1][n-1][0] и dp[n-1][n-1][1].
Код в комментариях:


Эта задача была на контесте яндекса. Больше разбора для тех кто взял курсы.

@algoses

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

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

intervals[i] = [start_i, end_i]

Нужно слить все пересекающиеся интервалы и вернуть такой набор, в котором все интервалы непересекаются, и их объединение покрывает все интервалы из исходного набора.

Пример

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Решение:
Метод сканирующей прямой
Во вспомогательном массиве сохраним индексы и тип события (интервал открылся 1, закрылся -1) и отсортируем
Далее пройдемся по всем событиям в порядке индексов и будем поддерживать счетчик количества интервалов, которые покрывают текущую точку. Если в какой-то момент счетчик становится 0, то добавляем в ответ новый интервал и идем дальше. Если ненулевой, то ничего добавлять не нужно

static bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first != b.first)
return a.first < b.first;
return a.second > b.second;
}

vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = (int)intervals.size();
vector<pair<int, int>> ev;
for (int i = 0; i < n; ++i) {
ev.emplace_back(intervals[i][0], 1);
ev.emplace_back(intervals[i][1], -1);
}
sort(ev.begin(), ev.end(), cmp);
vector<vector<int>> res;
int cnt = 0, first = -1;
for (auto event : ev) {
int ind = event.first, type = event.second;
cnt += type;
if (cnt == 0) {
res.push_back({first, ind});
first = -1;
} else if (first == -1)
first = ind;
}
return res;
}

@algoses

Задача с МЛ секции Яндекс (2025)

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

Задача:
Дан отсортированный по неубыванию список целых чисел a, индекс элемента index и целое число k.
Необходимо вернуть в любом порядке k чисел из списка, которые являются ближайшими по значению к элементу a[index].

Ограничения:
- Размер списка 1 <= N <= 10^6 ;
- Элементы списка: -10^9 <= a[i] <= 10^9 ;
- Число 0 < k <= N ;
- Индекс элемента 0 <= index < N .
- Среди двух одинаково отдалённых элементов выбирается больший

find_k_closest(a=[2, 3, 5, 7, 11], index=3, k=2) -> [5, 7]
find_k_closest(a=[11, 12, 15, 15, 24], index=1, k=3) -> [11, 12, 15]
find_k_closest(a=[2, 3, 5, 7, 11], index=2, k=2) -> [5, 7]

Решение:
Так как массив отсортирован, в ответ попадут несколько элементов слева от index и сколько-то элементов правее от index.

В ответ обязательно попадет a[index], так как расстояние ноль. Дальше смотрим на соседей index (справа и слева), кто ближе, того и добавляем в ответ, и сдвигаем указатель.

Будьте осторожны с выходом за пределы массива.

def find_k_closest(a: list[int], index: int, k: int) -> list:
left_ptr = index - 1
right_ptr = index + 1
k_closest = [a[index]]
while len(k_closest) != k:
if left_ptr < 0 or ((right_ptr < len(a)) and (abs(a[index] - a[right_ptr]) <= abs(a[index] - a[left_ptr]))):
k_closest.append(a[right_ptr])
right_ptr += 1
elif left_ptr >= 0:
k_closest.append(a[left_ptr])
left_ptr -= 1

return k_closest

Скорость посчитайте сами, жду ответов в комментариях😉

@algoses

Задача с Google.
Довольно простая задача от гугла. На самом деле задачи там сложнее чем в Яндексе, наверное эта задача попалась в первом отборе.

Задача:
Даются две строки s, t. Вернуть True, если можно сделать строку t равной s.
Вам разрешается не более одного раза выбрать подотрезок [l, r] сделать циклический сдвиг подстроки t[l. r].
Важно: Решить без дополнительной памяти.

Пример:
s = 'addeffge'
t = 'adeffdge'
Выбираем подотрезок [2, 5] и делаем циклический сдвиг вправо.

Решение:
Пройдемся слева направо по строке t. Найдем самую левую позицию l, что t[l] != s[l], а также найдем максимальную позицию r, что t[r] != s[r].
Если таких позиций нет то ответ True.
Если l=r то ответ False.

Иначе у нас два варианта, циклически сдвинуть подотрезок влево или вправо. Мы сделаем и тот и другой вариант и проверим совпали ты строки. Главное помнить не использовать дополнительную память.


Время работы алгоритма O(len(t))

@algoses

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

У Пети был массив целых чисел, состоящий из уникальных элементов и отсортированный по возрастанию. Его друг Вася, когда увидел массив, начал завидовать Пете и решил циклически сдвинуть исходный массив на k позиций. Другими словами, изначальный массив nums теперь имеет вид

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

Дан массив nums (уже сдвинутый) и число target. Нужно за O(logN) найти индекс числа target в nums, или вернуть -1, если его нет.

Решение
Применим два бинарных поиска

Сначала найдем величину сдвига k: это достаточно просто сделать, сравниваем средний элемент с самым правым. Если средний больше, то точка сдвига находится правее, иначе левее и таким образом найдем k
Далее применим также бинарный поиск на всем массиве для нахождения индекса target.
Теперь, когда мы знаем наш сдвиг k, нам просто нужно изменить наше среднее значение следующим образом: currm = (m + k) % N. И задача решена

Два бинарных поиска: O(2logN) = O(logN)

@algoses

Задача с собеседования в Тинькофф.

Умеете ли решать следующую задачу?
Дается массив целых чисел 'a', найти два индекса 0 <=l<r<n, что a[l] + a[r] == target.
Думаю многие знают эту задачу, называется Two Sum. Эта задача очень часто встречалась в Яндексе.

Так вот люди в Тинькофф поменяли эту задачу:
Дается отсортированный массив целых чисел 'a', найти два индекса 0 <=l<r<n, что a[l] + a[r] == target.
Решить нужно за O(n) и без дополнительной памяти.

Решение:
-Сначала вспомним как решать с доп памятью:
Заведем хеш-таблицу has. Пройдемся циклом по массиву 'a'. Пусть мы на позиции i, нам хотелось бы найти такой j, что j < i и a[i] + a[j] == target. Мы могли бы в хеш-таблице узнать встречали ли число a[j], равным target-a[i].

Заметим, что мы вообще не использовали факт отсортированности массива.
Пусть j=0, найдем максимальный i, что a[j] + a[i] <= target. В таком случае для j=0, лучшая пара это i. Если a[i] + a[j] = target, то супер мы нашли ответ.

Пусть j=1, найдем максимальный i, что a[j] + a[i] <= target. Как думаешь i, для j=1 может быть больше чем i для j=0?
Конечно нет, а это означает мы можем применить метод двух указателей.

j будет всегда идти слева направо, а i справа налево. Как только находим сумму равная target выходим из цикла. Этот метод сработал число из за отсортированности массива.

Для практики вы можете взять задачу Two Sum из литкода, отсортировать массив который вам дают и применить метод двух указателей.

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