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

Треш на алгоритмических собеседованиях на топовые офферы и магистратуры в 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