Вопросы на собеседовании в Авито

У Авито сильная DS-культура вокруг классифайда: рекомендации и ранжирование объявлений, модерация, и заметно больше A/B-тестов и продуктовой аналитики, чем у других big-tech в нашем срезе. Ниже — вопросы этого формата с разбором.

1. #ab_testing1 / 9

   Как работает CUPED и за счёт чего он ускоряет эксперименты?

   A)Вычитает из метрики её предэкспериментальную ковариату: Y'=Y−θ(X−E[X])

   B)Просто удаляет выбросы метрики по верхним и нижним перцентилям распределения

   C)Объединяет несколько разных продуктовых метрик в один сводный индекс

   D)Заменяет обычный t-тест на непараметрический ранговый аналог

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

   +A)Вычитает из метрики её предэкспериментальную ковариату: Y'=Y−θ(X−E[X])

   // разбор: Значительная часть дисперсии метрики — стабильные различия юзеров, существовавшие до теста; CUPED убирает эту предсказуемую часть (θ = cov(X,Y)/var(X)). При корреляции 0.7 дисперсия падает вдвое — тест той же мощности идёт вдвое быстрее. Требования: ковариата собрана до эксперимента и не затронута им. Стандарт индустрии от Microsoft/Netflix до Яндекса и Авито.

2. #ab_testing2 / 9

   Почему нельзя сегментировать результаты A/B-теста постфактум («у мужчин 25–34 на iOS эффект есть!») и объявлять это выводом?

   A)Это HARKing и множественные сравнения: значимый сегмент найдётся случайно

   B)Просто потому, что пользовательские сегменты слишком малы

   C)Постфактум-сегментация прямо и строго запрещена внутренней методологией всех крупных компаний

   D)Эффект в сегменте в точности совпадает со средним по тесту

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

   +A)Это HARKing и множественные сравнения: значимый сегмент найдётся случайно

   // разбор: 30 сегментов при α=0.05 — в среднем полтора ложных открытия гарантированно. Плюс подвыборки не защищены рандомизацией от post-hoc отбора. Корректно: заранее объявленные сегменты с поправками, или exploratory-анализ с честной пометкой «гипотеза» и подтверждающим тестом. Красивая история про сегмент — самый продаваемый вид статистической ошибки.

3. #algorithms3 / 9

   Функция делит массив пополам и на каждом уровне линейно обходит все элементы (как merge sort). Почему это O(n log n)?

   A)Потому что рекурсия по определению добавляет ровно логарифмический множитель

   B)Потому что деление пополам стоит O(n²), а обход O(1)

   C)Потому что суммарно уровней n, и на каждом O(log n) работы

   D)Уровней деления log n, на каждом суммарно O(n) работы — итого n·log n

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

   +D)Уровней деления log n, на каждом суммарно O(n) работы — итого n·log n

   // разбор: Дерево рекурсии имеет log₂n уровней (пополам до единиц). На каждом уровне сумма длин всех кусков равна n, значит линейный обход даёт O(n) на уровень. Всего O(n)·log n = O(n log n). Квадрат получился бы, если бы работа на уровне была n на каждый кусок, а не суммарно.

4. #algorithms4 / 9

   Нужно найти k-й по величине элемент в неотсортированном массиве. Что асимптотически лучше полной сортировки?

   A)Ничего лучше нет: сначала отсортировать массив за O(n log n), иначе никак

   B)Перебрать все пары за O(n²)

   C)Quickselect: в среднем O(n) — частичное разбиение как в quicksort

   D)Бинарный поиск по массиву за O(log n)

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

   +C)Quickselect: в среднем O(n) — частичное разбиение как в quicksort

   // разбор: Quickselect выбирает пивот и разбивает массив; в нужную половину рекурсивно спускается, вторую отбрасывает. В среднем O(n) (n + n/2 + n/4 + ...), в худшем O(n²) — лечится медианой медиан или рандомизацией. Полная сортировка O(n log n) избыточна: нам не нужен порядок всех элементов, только k-й. Куча размера k даёт O(n log k) — тоже вариант.

5. #algorithms5 / 9

   Приём «монотонный стек» (monotonic stack) обычно решает задачи вида...

   A)Подсчёт количества уникальных элементов среди всех подотрезков заданного массива

   B)Сортировка за линейное время

   C)Поиск НОД в массиве

   D)«следующий больший элемент справа» и подобные — за O(n) вместо O(n²)

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

   +D)«следующий больший элемент справа» и подобные — за O(n) вместо O(n²)

   // разбор: Монотонный стек хранит элементы в возрастающем (или убывающем) порядке; при добавлении нового выталкивает из вершины все нарушающие монотонность — и для каждого вытолкнутого текущий элемент как раз «следующий больший/меньший». Каждый элемент кладётся и снимается один раз → амортизированно O(n). Решает next greater element, «площадь гистограммы».

6. #algorithms_advanced6 / 9

   При обходе большого графа DFS-ом что обязательно, чтобы не зациклиться?

   A)Помечать посещённые вершины (visited) и не заходить в них повторно

   B)Сортировать вершины перед обходом

   C)Использовать рекурсию, без явного стека

   D)Заранее обеспечить, что во входном графе вообще нет ни одного цикла между вершинами

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

   +A)Помечать посещённые вершины (visited) и не заходить в них повторно

   // разбор: В графе с циклами DFS без пометок будет ходить по кругу вечно. visited-множество помечает уже раскрытые вершины, и повторный вход в них отсекается — каждая вершина и ребро обрабатываются один раз, обход O(V+E). Требовать ацикличности входа нельзя — обход должен работать на любом графе. Рекурсия или явный стек — деталь реализации.

7. #classic_ml7 / 9

   Когда линейной модели нужны явные признаки-взаимодействия (x₁·x₂), а бустингу — обычно нет?

   A)Линейная модель аддитивна и взаимодействий сама не выучит; деревья ловят их сплитами до порядка своей глубины

   B)Бустинг запрещает произведения признаков — они дублируют сплиты

   C)Взаимодействия нужны всем моделям в равной мере

   D)Линейной модели взаимодействия не нужны: комбинируя веса признаков, она выучивает их неявно уже в процессе обучения

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

   +A)Линейная модель аддитивна и взаимодействий сама не выучит; деревья ловят их сплитами до порядка своей глубины

   // разбор: В аддитивной модели эффект x₁ не может зависеть от x₂, пока произведение не добавлено руками — классика: цена за м² зависит от района. Дерево делит сначала по одному признаку, потом внутри ветки по другому — это и есть взаимодействие; глубина k покрывает порядки до k. Поэтому фичи-произведения — приём в первую очередь для линейных моделей.

8. #classic_ml8 / 9

   Как правильно организовать разбиение данных при подборе гиперпараметров и финальной оценке модели?

   A)Train/test: тюнимся на тесте, на нём же и репортим качество

   B)Кросс-валидация по всем доступным данным: усреднение по фолдам честнее, отдельный тест не нужен

   C)Случайное 50/50, независимо от задачи

   D)Train/validation/test (или CV по трейну для тюнинга) — тест трогаем один раз в самом конце

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

   +D)Train/validation/test (или CV по трейну для тюнинга) — тест трогаем один раз в самом конце

   // разбор: Гиперпараметры, подобранные по тесту, «подгоняют» модель под него — оценка становится оптимистичной. Тюнинг живёт на валидации или в кросс-валидации по трейну; тест — одноразовая финальная проверка. Для временных рядов сплит обязан быть по времени, иначе утечка из будущего.

9. #classic_ml9 / 9

   Почему в градиентном бустинге уменьшение learning rate почти всегда требует увеличения числа деревьев?

   A)Каждое дерево вносит меньший вклад — для того же качества нужно больше шагов

   B)Маленький learning rate ломает численную стабильность, и её компенсируют числом деревьев

   C)Число деревьев подбирается библиотекой автоматически под заданный learning rate

   D)Learning rate влияет на глубину деревьев, а качество добирается их количеством

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

   +A)Каждое дерево вносит меньший вклад — для того же качества нужно больше шагов

   // разбор: Learning rate масштабирует вклад каждого дерева в ансамбль. Меньший шаг — более плавное движение по ландшафту лосса и обычно лучшее обобщение, но нужно больше итераций. Классическая практика: уменьшить lr, увеличить n_estimators и подобрать точку ранней остановки по валидации.