Треш на алгоритмических собеседованиях на топовые офферы и магистратуры в CS

Мы опросили наших выпускников программы алгоритмы про, что им встречалось по каждому направлению отсюда. И вот что из этого вышло.

Задача Андрея (4 курс БГУ ФПМИ) на собеседовании в магистратуру СКН.
Условие: Даны n исходных строк и m строк-запросов. Для каждой строки-запроса s нужно определить, существует ли среди исходных строк строка t, такая что: len(t) = len(s) и t отличается от s ровно в одной позиции. Строки состоят только из символов a, b, c. На каждый запрос выведите YES, если такая строка существует, иначе NO. Ограничения: n, m <= 3e5, суммарная длина всех строк не превышает 6e5

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


Задача на собеседование в GOOGLE на позицию SWE разработчика с зп 8000$

Условие: Дана перестановка чисел от 1 до n. Из неё удалили два элемента, после чего оставшиеся n - 2 чисел разделили на две непустые части.

Программа запускается два раза. При первом запуске дана левая часть последовательности. Нужно вывести строку-памятку длиной не более 1000 символов. При втором запуске дана эта памятка и правая часть последовательности. Нужно определить два числа от 1 до n, которых нет ни в левой, ни в правой части.
Ограничение: 4 <= n <= 3e5.

Идея решения:
Каждому числу i сопоставляем случайный 64- битный хеш (можно просто рандом число назначить mt19937 например) h(i).
На первом запуске считаем:
H_left = sum(h(x)) по всем x из левой части и сохраняем H_left в памятку.
На втором запуске считаем:
H_missing = sum(h(i)) для i от 1 до n - H_left - sum(h(x)) по правой части
Тогда:
H_missing = h(a) + h(b), где a и b - два пропавших числа.
Дальше перебираем a и проверяем, существует ли число b с хешем:
h(b) = H_missing - h(a).
Все хеши можно заранее хранить в unordered_map. Сложность - O(n)
Код с решением задачи.


Задача из собеседования в hft Sspectral technologies которую дали Артёму на SWE позицию с зп 70 000$ в год

Условие: Дано дерево из n вершин. В одной из вершин находится скрытая вершина x, которую нужно определить. Можно делать запросы вида:
? v
В ответ интерактор сообщает:
0, если v = x
номер соседа вершины v, который является первым на пути из v в x.
Когда скрытая вершина найдена, нужно вывести:
! x
Разрешается сделать не более log2(n) + 1 запросов.

Идея решения
Рассматриваем множество вершин, в котором сейчас может находиться x. Находим центроид этого поддерева и спрашиваем его. Если ответ 0, вершина найдена. Иначе интерактор возвращает соседа u. После удаления центроида дерево распадается на компоненты, и x гарантированно находится в компоненте, содержащей u. Оставляем только эту компоненту и повторяем процесс. Так как центроид делит дерево на компоненты размера не более половины текущего дерева, количество возможных вершин уменьшается каждый раз в два раза. Поэтому потребуется O(log n) запросов.
Это полный аналог бинарного поиска: в массиве выбираем середину и оставляем одну половину, а в дереве выбираем центроид и оставляем одну из компонент после его удаления.
Код с решением

Подписаться: @algoses