Задачи с собеседований¶

Подборка классических задач с собеседований, LeetCode и CodeWars, сгруппированных по структуре данных, которую они закрепляют. Если в DSA-лабах lab00–lab11 структуры реализуются «с нуля» без встроенных функций, то здесь мы их применяем — на готовых dict, set, list. Это разные режимы: в лабе важно понять, как устроена хеш-таблица, а тут — как ей пользоваться, чтобы свести перебор O(n²) к одному проходу.

Решения лежат в src/python/tasks/interview/, тесты — в tests/tasks/interview/. У части задач есть Go-версии в модуле src/golang/tasks/ (пакет interview, тесты рядом с кодом — гоняются через make go-test). Структура зеркальная и однозначная: каждой задаче из колонки Модуль соответствует ровно один файл решения src/python/tasks/interview/<модуль>.py и один файл тестов tests/tasks/interview/test_<модуль>.py. Каждый модуль в docstring помечен строкой «Закрепляет: labNN» и оценкой сложности. Запуск тестов — обычным make py-test (или uv run pytest tests/tasks/interview).

Как пользоваться¶

Сначала попробуйте решить задачу сами, опираясь на структуру из соответствующей лабы, и только потом сверьтесь с разбором. Ценность не в «знать ответ», а в том, чтобы видеть: «здесь повторяющийся поиск → нужен словарь», «здесь отсортированный массив → два указателя», «здесь ждём более позднее событие → стек».

Хеш-таблица → lab05 ¶

Словарь и множество дают проверку принадлежности и подсчёт за O(1) — это превращает вложенные циклы в один проход. Самый частый приём на собеседованиях.

Задача	Идея	Сложность	Модуль
Есть ли дубликаты	множество «уже виденных»	O(n) / O(n)	`contains_duplicate`
Two Sum	словарь «значение → индекс», ищем дополнение	O(n) / O(n)	`two_sum`
Пересечение массивов	частоты меньшего массива, вычёркиваем по большему	O(n+m) / O(min)	`array_intersection`
Первый уникальный символ	частотный словарь + второй проход	O(n) / O(k)	`first_unique_char`
Анаграмма	сравнение частотных словарей вместо сортировки	O(n) / O(k)	`valid_anagram`
Макс. серия повторов	максимум длины серии по символу	O(n) / O(k)	`max_consecutive_repeats`
Объединение N массивов	множество уникальных + сортировка результата	O(n + k log k) / O(k)	`union_all_ints`

Массив, стек и два указателя → lab01 ¶

Работа на месте (O(1) памяти), движение указателей по отсортированному массиву и стек «ожидающих» элементов.

Задача	Идея	Сложность	Модуль
Пропущенное число	сумма по Гауссу минус сумма массива	O(n) / O(1)	`missing_number`
Удалить дубли (sorted)	указатель записи `write`, in-place	O(n) / O(1)	`remove_duplicates`
Сдвиг массива на k	тройной разворот in-place	O(n) / O(1)	`rotate_array`
Two Sum (sorted)	два указателя с краёв	O(n) / O(1)	`two_sum_sorted`
Сколько дней до тепла	монотонный стек индексов	O(n) / O(n)	`daily_temperatures`
Переместить нули в конец	указатель записи, in-place	O(n) / O(1)	`move_zeroes`
Развернуть строку	два указателя навстречу	O(n) / O(1)	`reverse_string`

Поиск → lab04 ¶

Опора на отсортированность входа: указатели сходятся к ответу без полного перебора.

Задача	Идея	Сложность	Модуль
Общее число в 3 массивах	три указателя, двигаем минимальный	O(n1+n2+n3) / O(1)	`common_in_three`
k ближайших к элементу	расхождение от позиции влево/вправо	O(k log k) / O(k)	`k_closest`

Биты и арифметика¶

Приёмы, не требующие отдельной структуры: разряды и свойства XOR.

Задача	Идея	Сложность	Модуль
Прибавить единицу	перенос разряда «в столбик»	O(n) / O(1)	`plus_one`
Одиночка среди пар	XOR схлопывает пары	O(n) / O(1)	`single_number`
Второй максимум	один проход, два «призёра» (по уникальным)	O(n) / O(1)	`second_max`

Про second_max

В исходной формулировке часто пишут «за один проход», но решают через sorted(arr)[-2] — это и не один проход, и неверно при дубликатах ([5, 5, 4] должно дать 4, а не 5). В репозитории задача переписана как честный O(n) поиск второго уникального максимума с двумя переменными-инвариантами.

Что можно добавить дальше¶

Курированный набор закрывает структуры из академических лаб. За кадром остались кластеры, которые ложатся не на лабы, а на тему строк/regex и на новые темы, — их можно добавить отдельной партией:

Строки — палиндром, общий префикс, strStr, atoi, reverse integer, генератор хештегов (тема 11, regex и разбор текста).
Матрицы 2D — валидный судоку, поворот картинки на 90°.
Динамика на сетке — число путей робота, треугольник Паскаля.