Вопросы на собеседовании Data Engineer

DWH и моделирование данных, ETL и оркестрация, Spark и стриминг, SQL, распределённые системы и инфра. Ниже — что спрашивают на собесе дата-инженера, с ответами.

1. #algorithms1 / 9

   Почему поиск по ключу в хеш-таблице (dict/set) в среднем O(1), а в списке — O(n)?

   A)Список хранит элементы строго отсортированными, а хеш-таблица — вперемешку без порядка

   B)В списке элементы занимают меньше памяти, поэтому поиск медленнее

   C)Хеш по ключу сразу вычисляет позицию (бакет), а список надо обходить подряд

   D)Разницы нет, оба O(n)

   показать ответ и разбор

   +C)Хеш по ключу сразу вычисляет позицию (бакет), а список надо обходить подряд

   // разбор: Хеш-функция превращает ключ в индекс бакета за O(1), и мы прыгаем прямо к нему. В списке адреса по значению неизвестны, поэтому линейный поиск обходит элементы один за другим — O(n). Цена O(1): нет порядка и есть накладные расходы на хеширование и коллизии.

2. #algorithms2 / 9

   Алгоритм работает за O(n). Что это значит на практике?

   A)Он выполняет ровно n операций при входе — ни больше, ни меньше

   B)Число операций растёт линейно с размером входа n

   C)В худшем случае он делает порядка n² операций

   D)Ему требуется ровно n байт дополнительной памяти

   показать ответ и разбор

   +B)Число операций растёт линейно с размером входа n

   // разбор: O(n) — про асимптотику: при росте входа вдвое время растёт примерно вдвое. Это верхняя оценка скорости роста, а не точное число операций и не про память. Константы и младшие члены отбрасывают: O(3n+5) — это O(n).

3. #algorithms3 / 9

   Бинарный поиск работает за O(log n). Какое условие обязательно для его применения?

   A)Массив должен состоять из чисел, строки бинарным поиском искать не получится

   B)Массив (или диапазон) должен быть отсортирован по искомому ключу

   C)В массиве не должно быть повторяющихся значений

   D)Размер массива должен быть степенью двойки

   показать ответ и разбор

   +B)Массив (или диапазон) должен быть отсортирован по искомому ключу

   // разбор: Бинарный поиск на каждом шаге отбрасывает половину диапазона, сравнивая середину с искомым — это возможно только если данные упорядочены по ключу. O(log n) — число делений пополам до одного элемента. Повторы и нечисловые типы допустимы (лишь бы был порядок); степень двойки не требуется.

4. #algorithms4 / 9

   Стек (stack) — это структура с дисциплиной...

   A)LIFO: последним пришёл — первым вышел

   B)FIFO: первым пришёл — первым вышел

   C)По приоритету: первым выходит элемент с наименьшим ключом среди всех имеющихся

   D)Случайного доступа по индексу

   показать ответ и разбор

   +A)LIFO: последним пришёл — первым вышел

   // разбор: Стек — LIFO: push кладёт наверх, pop снимает верхний, оба O(1). Аналогия — стопка тарелок. FIFO — это очередь, приоритет — куча. Стек естественно моделирует вложенность: вызовы функций (call stack), парсинг скобок, откат (undo), обход в глубину.

5. #algorithms_advanced5 / 9

   Чем отличаются два способа реализации DP: мемоизация и табуляция?

   A)Мемоизация — рекурсия сверху вниз с кэшем; табуляция — итеративное заполнение таблицы снизу вверх

   B)Мемоизация применима только к задачам на графах, а табуляция — исключительно к задачам на деревьях и решётках

   C)Это два названия одного и того же приёма

   D)Табуляция экспоненциальна, мемоизация линейна

   показать ответ и разбор

   +A)Мемоизация — рекурсия сверху вниз с кэшем; табуляция — итеративное заполнение таблицы снизу вверх

   // разбор: Оба варианта DP устраняют повторный счёт перекрывающихся подзадач, но идут с разных концов. Мемоизация — это рекурсия сверху вниз, которая запоминает результат каждой подзадачи и при повторе берёт из кэша; считает только реально нужные подзадачи, но держит стек рекурсии. Табуляция заполняет таблицу снизу вверх циклом от базовых случаев; нет рекурсии и её стека, но иногда считает лишние ячейки.

6. #algorithms_advanced6 / 9

   Почему BFS находит кратчайший путь в невзвешенном графе, а DFS — нет?

   A)Обходит вершины волнами по возрастанию расстояния, поэтому впервые достигает каждую по кратчайшему пути

   B)BFS быстрее DFS по времени работы

   C)DFS находит между вершинами лишь самый длинный путь, поэтому для кратчайшего в невзвешенном графе он непригоден

   D)BFS сортирует рёбра по весу перед обходом

   показать ответ и разбор

   +A)Обходит вершины волнами по возрастанию расстояния, поэтому впервые достигает каждую по кратчайшему пути

   // разбор: BFS расходится от старта слоями: сначала все вершины на расстоянии 1, затем 2 и т.д. Значит момент первого попадания в вершину соответствует минимальному числу рёбер до неё — это и есть кратчайший путь в невзвешенном графе. DFS углубляется по одной ветке и может достичь вершины длинным путём раньше короткого. Для взвешенных графов BFS уже недостаточно — нужен Дейкстра.

7. #algorithms_advanced7 / 9

   От чего зависит глубина стека вызовов при рекурсивном обходе?

   A)От высоты дерева рекурсии: на стеке живут кадры текущей цепочки, глубокая рекурсия переполняет стек

   B)От общего числа рекурсивных вызовов за всё время работы, независимо от того, насколько глубоко они вложены

   C)От числа ядер процессора

   D)От объёма кучи, выделенной программе

   показать ответ и разбор

   +A)От высоты дерева рекурсии: на стеке живут кадры текущей цепочки, глубокая рекурсия переполняет стек

   // разбор: На стеке одновременно живут только кадры вызовов текущей цепочки — от корня до текущего листа рекурсии. Значит потребление стека определяется МАКСИМАЛЬНОЙ глубиной вложенности, а не суммарным числом вызовов. Обход сбалансированного дерева уходит на O(log n), а вырожденного (или линейной рекурсии по n) — на O(n), что и грозит переполнением стека на больших входах.

8. #algorithms_advanced8 / 9

   Что такое обход дерева in-order, pre-order и post-order, и чем они задаются?

   A)Порядком узла относительно поддеревьев: pre — до потомков, in — между ними, post — после обоих

   B)Это три разных структуры данных для деревьев

   C)Направлением обхода поддеревьев: pre идёт справа налево, in — слева направо, а post — по замкнутому кругу

   D)Способом хранения дерева в памяти

   показать ответ и разбор

   +A)Порядком узла относительно поддеревьев: pre — до потомков, in — между ними, post — после обоих

   // разбор: Это варианты DFS по дереву, отличающиеся моментом обработки узла. Pre-order: узел → левое → правое (полезно для копирования/сериализации). In-order: левое → узел → правое (в BST даёт отсортированный порядок). Post-order: левое → правое → узел (полезно для удаления/вычисления снизу вверх). Level-order (по уровням) — это уже BFS, а не DFS.

9. #algorithms_advanced9 / 9

   В сбалансированном бинарном дереве поиска (BST) поиск и вставка идут за...

   A)O(1)

   B)O(n)

   C)O(n log n), столько же, сколько стоит полная сортировка этого набора элементов

   D)O(log n) — высота сбалансированного дерева логарифмична от числа узлов

   показать ответ и разбор

   +D)O(log n) — высота сбалансированного дерева логарифмична от числа узлов

   // разбор: В BST на каждом шаге сравнение уводит в левое или правое поддерево, отсекая половину — если дерево сбалансировано, его высота ≈ log₂n, отсюда O(log n). Но без балансировки вырожденное дерево (вставка отсортированных данных) превращается в список высотой n → O(n). Поэтому используют самобалансирующиеся деревья: AVL, красно-чёрные.