Подготовка к собеседованию — ML-инженер

Короткий ответ: Big O описывает, как растёт время работы или потребление памяти алгоритма при увеличении размера входных данных n, отбрасывая константы и младшие члены. Это верхняя оценка скорости роста.

Подробно:

Big O отвечает на вопрос «что произойдёт, когда n станет очень большим?». Нас не интересует точное число операций, а только характер роста. Поэтому O(2n + 100) упрощается до O(n), а O(3n² + n) — до O(n²).

Основные классы роста (от лучшего к худшему):

# O(1) — константа: не зависит от n
def first(arr):
    return arr[0] if arr else None

# O(log n) — логарифм: каждый шаг делит задачу пополам (бинарный поиск)
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# O(n) — линейная: один проход
def total(arr):
    s = 0
    for x in arr:        # n итераций
        s += x
    return s

# O(n log n) — эффективные сортировки (merge, quick, Timsort)
def sort_it(arr):
    return sorted(arr)

# O(n^2) — квадрат: вложенный цикл
def has_dup_naive(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# O(2^n) — экспонента: наивный Фибоначчи, перебор подмножеств
def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

Ориентир по росту при n = 1 000 000: O(1) — 1 операция, O(log n) — ~20, O(n) — миллион, O(n log n) — ~20 млн, O(n²) — триллион (уже слишком), O(2^n) — нереально даже при n = 50.

⚠️ Ловушка: Big O — это про асимптотику (поведение при больших n), а не про реальное время. O(n) алгоритм может быть медленнее O(n²) на маленьких данных из-за больших констант. Также путают: Big O (верхняя граница, Ω — нижняя, Θ — точная), в собесах под «O» обычно подразумевают Θ.

Короткий ответ: Переобучение — модель выучила шум трейна вместо закономерности: на трейне ошибка низкая, на новых данных — высокая. Обнаруживают по разрыву train/validation, лечат регуляризацией, упрощением модели, ранней остановкой и бóльшим объёмом данных.

Подробно:

1. Обнаружение — сравнить ошибку на трейне и на валидации; learning curves: train-ошибка падает, validation-ошибка стоит или растёт → модель начала запоминать шум.
2. Лечение — уменьшить ёмкость или добавить сигнала, а не «крутить» метрику.

	Обнаружить	Исправить
Разрыв метрик	train ≈ 0, валидация заметно хуже	регуляризация (L1/L2), проще модель
Learning curves	кривые расходятся с ростом эпох	early stopping
Кросс-валидация	нестабильные метрики по фолдам	больше данных, аугментация
Сложность модели	глубокие деревья, миллионы весов	ограничить глубину, срезать фичи

⚠️ Частая ошибка: сказать «кросс-валидация предотвращает переобучение». CV его лишь обнаруживает — честно оценивает качество. Предотвращают регуляризация, упрощение модели и данные.

Короткий ответ: Жадно: в каждом узле перебираются фичи и пороги, выбирается сплит с максимальным снижением impurity (Джини или энтропия; для регрессии — MSE). Без ограничения глубины дерево доводит листья до чистоты — то есть запоминает трейн вместе с шумом.

Подробно:

1. Критерий сплита — прирост: impurity(родителя) − взвешенная impurity(детей); Джини G = 1 − Σpₖ², энтропия −Σpₖ·log pₖ — на практике почти взаимозаменяемы.
2. Жадность — каждый узел оптимизируется отдельно; глобально оптимальное дерево — NP-полная задача, поэтому неудачный верхний сплит никогда не пересматривается.
3. Почему переобучение — модель кусочно-константная: при неограниченной глубине каждый лист ужимается до одного объекта → нулевая ошибка на трейне, высокая дисперсия на тесте.

Ограничение	Что делает
max_depth	режет число уровней
min_samples_leaf	не даёт листу ужаться до 1 объекта
ccp_alpha (прунинг)	срезает узлы, не окупающие сложность
Ансамбли	RF/бустинг превращают слабость дерева в силу

⚠️ Частая ошибка: считать, что дерево находит «лучшее разбиение» глобально — оно жадное, и это принципиальное ограничение, а не деталь реализации.

Короткий ответ: Precision (точность) = TP/(TP+FP) — доля настоящих позитивов среди всех, кого модель назвала позитивными. Recall (полнота) = TP/(TP+FN) — доля найденных среди всех реальных позитивов. Recall критичен там, где дорог пропуск (скрининг рака, fraud); precision — там, где дорога ложная тревога (спам-фильтр, блокировка контента).

Подробно:

	Факт: 1	Факт: 0
Прогноз: 1	TP	FP
Прогноз: 0	FN	TN

1. Precision — читаем строку «прогноз: 1»: сколько из срабатываний модели настоящие. Метрика цены ложной тревоги.
2. Recall — читаем столбец «факт: 1»: какую долю реальных позитивов мы поймали. Метрика цены пропуска.
3. Trade-off через порог — на фиксированной выборке снижение порога не уменьшает recall, но precision может вырасти или упасть в зависимости от меток добавленных объектов. При скорах 0.9 (негатив) и 0.8 (позитив) снижение порога с 0.9 до 0.8 повышает precision с 0 до 1/2. Проверяйте фактическую precision–recall-кривую, а не предполагайте монотонность precision.

⚠️ Частая ошибка: назвать формулы и остановиться. Сильный ответ начинается с вопроса «что дороже — пропустить или ложно сработать», и только из него следует, какая метрика главная.

Источник: scikit-learn: precision–recall curve.

Короткий ответ: Скейлинг нужен моделям, которые опираются на расстояния, скалярные произведения или градиентный спуск: kNN, SVM, k-means, PCA, линейные с регуляризацией, нейросети. Деревьям, лесам и бустингу — не нужен: они инвариантны к монотонным преобразованиям.

Подробно:

Модель	Скейлинг	Почему
kNN, k-means, SVM	обязателен	расстояния: фича в метрах «задавит» фичу в километрах
PCA	обязателен	дисперсия: компоненты уйдут в фичу с большим масштабом
Линейные + L1/L2	обязателен	штраф на веса зависит от масштаба фич
Нейросети	нужен	сходимость градиентного спуска
Деревья / RF / бустинг	не нужен	сплиты по порогам, порядок значений не меняется

И ключевое: скейлер — часть модели. Fit только на train, transform на valid/test — иначе утечка статистик теста в обучение.

⚠️ Частая ошибка: «скейлю всё на всякий случай» до сплита — безобидная привычка превращается в лик; и наоборот, тратить время на скейлинг для XGBoost.