Комбинаторика на собеседовании аналитика
Зачем аналитику комбинаторика
Комбинаторика — раздел математики, который отвечает на вопрос «сколько способов». Сколько вариантов выборки из базы, сколько уникальных сегментов можно построить из пяти признаков, сколько комбинаций A/B-тестов при четырёх параметрах. Аналитик сталкивается с такими вопросами регулярно, поэтому интервьюеры проверяют базовое понимание.
На собеседовании задачи по комбинаторике обычно не требуют сложных формул. Достаточно понимать разницу между перестановками, сочетаниями и размещениями и уметь применять правила сложения и умножения.
Комбинаторика на собеседовании аналитика — это не олимпиадная математика. Интервьюер проверяет, умеете ли вы структурировать подсчёт и не путаете ли «выбрать 3 из 10» с «расставить 3 из 10 по порядку».
Базовые понятия
Правило умножения. Если первый выбор можно сделать m способами, а второй — n способами, то общее число комбинаций равно m * n. Пример: 5 каналов привлечения и 3 сегмента аудитории дают 15 вариантов таргетинга.
Правило сложения. Если события не пересекаются, общее число исходов — сумма. Пользователь может прийти из поиска (100 вариантов запросов) или из рекламы (50 объявлений) — итого 150 вариантов первого касания.
Перестановки — количество способов расставить n элементов в ряд. Равно n! (n факториал). Для 5 элементов — 120. Применение: сколько порядков вопросов в тесте из пяти вопросов.
Размещения — количество способов выбрать k элементов из n с учётом порядка. Формула: n! / (n - k)!. Из 10 кандидатов выбрать тройку призёров (1-е, 2-е, 3-е место) — 10 * 9 * 8 = 720 вариантов.
Сочетания — количество способов выбрать k элементов из n без учёта порядка. Формула: n! / (k! * (n - k)!). Из 10 метрик выбрать 3 для дашборда — C(10, 3) = 120 вариантов.
Принцип включения-исключения
Принцип включения-исключения решает задачи, где множества пересекаются. Формула для двух множеств: |A или B| = |A| + |B| - |A и B|.
Пример. В отделе 30 сотрудников. 18 знают Python, 15 знают SQL, 10 знают оба языка. Сколько знают хотя бы один? Ответ: 18 + 15 - 10 = 23.
Для трёх множеств формула расширяется: прибавляем размеры, вычитаем попарные пересечения, прибавляем тройное пересечение. На собеседовании чаще всего встречается вариант с двумя множествами — его нужно знать наизусть.
Типичные задачи на собеседовании
Задача 1: Сколько способов рассадить 6 человек за круглый стол? Ответ — (6 - 1)! = 120. При круговых перестановках делим на n, потому что вращение стола не создаёт новую рассадку.
Задача 2: Из колоды в 36 карт вытащить 3. Сколько вариантов? Порядок не важен — это сочетания. C(36, 3) = 36! / (3! * 33!) = 7 140.
Задача 3: Сколько уникальных сегментов можно составить из 5 бинарных признаков? Каждый признак — включён или нет. 2^5 = 32 комбинации, минус одна пустая = 31 непустой сегмент.
Задача 4: В команде 8 аналитиков. Нужно выбрать 2 для проекта A и 3 для проекта B. Сначала выбираем 2 из 8 для A: C(8, 2) = 28. Затем 3 из оставшихся 6 для B: C(6, 3) = 20. Итого: 28 * 20 = 560 вариантов.
Ключевой вопрос при решении комбинаторной задачи: важен ли порядок? Если да — используйте размещения или перестановки. Если нет — сочетания. Ошибка в этом выборе даёт ответ, отличающийся в разы.
Типичные ошибки
- Путают сочетания и размещения — забывают спросить себя, важен ли порядок.
- Забывают про повторения — если элементы можно использовать повторно, формулы меняются.
- Не проводят sanity check — если из 5 элементов нужно выбрать 3, ответ не может быть больше 5! = 120. Простая проверка ловит грубые ошибки.
Как готовиться
Выучите три формулы: перестановки, размещения, сочетания. Затем решите 10-15 задач, каждый раз начиная с вопроса «важен ли порядок?». Это единственный навык, который нужен — остальное приложится.
Комбинаторика часто пересекается с задачами на вероятность — классическая вероятность определяется как отношение благоприятных исходов к общему числу, и для подсчёта обоих нужна комбинаторика. Все темы — в разделе задачи на логику.
FAQ
Нужно ли заучивать формулу факториала?
Достаточно понимать, что n! = 1 * 2 * ... * n, и помнить значения до 10! = 3 628 800. На собеседовании калькулятор обычно доступен, но интервьюер хочет видеть, что вы правильно выбрали формулу и подставили числа, а не просто запомнили ответ.
Какие задачи по комбинаторике дают чаще всего?
Задачи на сочетания — абсолютный лидер. «Сколько способов выбрать k из n» встречается почти на каждом собеседовании с логическим блоком. На втором месте — задачи на принцип включения-исключения с диаграммами Венна.
Как не запутаться в формулах на собеседовании?
Начинайте с малого примера. Если нужно выбрать 2 из 4 элементов — перечислите все варианты вручную (AB, AC, AD, BC, BD, CD = 6 штук). Убедитесь, что формула C(4, 2) = 6 даёт тот же результат. Этот приём показывает интервьюеру зрелость мышления и страхует от ошибок.