Задача с зарубежной компании.
Дается матрица размера 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

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

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

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

Даны два массива 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

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

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

Новая задача Яндекса:
Дается массив целых чисел. Найти максимальный по длине подотрезок в котором сумма четная.
На самом деле эта задача очень похожа на старую задачу яндекса (задача 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

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

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

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

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

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

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

@algoses

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

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

AAABCCCCCDD -> A3BC5D2

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

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

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

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

@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

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

Дано дерево:

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

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

Дан список ненулевой длины, состоящий из направлений
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

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

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

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

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

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

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

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

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

@algoses

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

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

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

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

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

@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

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

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