Discrete Math на собеседовании

На интервью в Google Senior Engineer часто встречаются задачи «Докажите нижнюю оценку для данного алгоритма» или «Почему данный подход оптимален?». В Meta Design Review - «Объясните, почему Bloom Filter с такими параметрами даёт нам гарантию». Дискретная математика - это не теория ради теории, это язык объяснения и доказательства в инженерных дискуссиях.

• **Google L6 интервью:** задачи на подсчёт в комбинаторном стиле (пути в сетке с препятствиями, stars-and-bars для rate limiting) проверяют глубину, а не скорость
• **Meta System Design:** «Сколько бит нужно для Bloom Filter с fp_rate=0.01 для 10^9 элементов?» - прямой вопрос на формулу m = -n*ln(ε)/(ln2)²
• **Amazon Leadership Principles:** «Докажите, что данный алгоритм распределения задач оптимален» - инвариант + нижняя оценка
• **Coding interviews (LeetCode Hard):** двудольность, SCC, задачи на E[X] - стандарт для Staff Engineer позиций

Предварительные знания

• Discrete Math in Computer Science

Задачи на подсчёт: комбинаторика на интервью

В FAANG-интервью 80% задач на подсчёт сводятся к 5 паттернам: permutation, combination, partition, Catalan, Stirling - их суммарная частота на LeetCode превышает 1200 задач. Задачи на подсчёт появляются в кодинг-интервью часто в замаскированном виде: «сколько способов разложить», «сколько путей в сетке», «сколько сочетаний». Ключ - распознать тип задачи (перестановки, сочетания, stars-and-bars) и перевести на язык формул.

**Ключевые формулы подсчёта:** - **Перестановки:** P(n,k) = n!/(n-k)! - упорядоченный выбор k из n - **Сочетания:** C(n,k) = n!/(k!(n-k)!) - неупорядоченный выбор k из n - **Stars and bars:** C(n+k-1, k) - k одинаковых объектов в n ящиков - **Принцип включений-исключений:** |A∪B∪C| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + |A∩B∩C| - **Мультиномиальный коэффициент:** n!/(n₁!·n₂!·...·nₖ!) - перестановки с повторениями

**Паттерн распознавания на интервью:** «сколько способов выбрать X из Y» без порядка = сочетания. С порядком = перестановки. «Разложить одинаковые объекты по различимым ящикам» = stars and bars. «Хотя бы одно / не более» = включения-исключения или дополнение.

На интервью часто проверяют: можете ли перейти от DP-решения к закрытой формуле. Задача «пути в сетке» решается DP за O(mn) или формулой C(m+n,m) за O(1). Умение объяснить оба подхода - признак глубокого понимания.

Граф-задачи: двудольность и компоненты связности

Теория графов на FAANG-интервью проверяется через конкретные алгоритмические задачи. Два классических паттерна: проверка двудольности (bipartite checking) и нахождение сильно связных компонент (SCC). Оба решаются обходом графа, но с разной целью.

**Двудольный граф (Bipartite):** вершины разбиваются на два множества U и V, рёбра только между U и V. Эквивалентно: граф не содержит нечётных циклов. Алгоритм: BFS с 2-раскраской за O(V+E). **Сильно связные компоненты (SCC):** в ориентированном графе компонента, где из любой вершины достижимы все остальные. Алгоритм Косараю: два обхода DFS за O(V+E).

**Применение SCC в реальных задачах:** разрешение зависимостей пакетов (circular dependencies = один SCC), оптимизация импортов в компиляторах, определение «сильных» кластеров в социальных сетях. На интервью Meta часто спрашивают про граф дружбы.

На интервью всегда уточняйте: граф ориентированный или нет? Простой или мультиграф? Связный или нет? SCC имеет смысл только для ориентированных графов. Для неориентированных используют WCC (weakly connected components) через Union-Find.

Вероятностные задачи и E[X] на интервью

Вероятностные задачи на интервью Google/Meta проверяют понимание условной вероятности, Байеса и линейности E[X]. Часто это головоломки, которые кажутся сложными, но решаются элегантно через правильный выбор случайного пространства.

**Классические паттерны вероятностных задач на интервью:** - **Задача о встрече:** два человека приходят случайно в [0, T], ждут W минут. P(встреча)? - **Задача о монетах:** E[бросков до k орлов подряд] - **Задача о купонах:** E[попыток купить все n различных купонов] - **Задача о секретаре:** оптимальная стратегия выбора (37% rule) - **Парадокс Монти Холла:** P(выиграть при смене двери) = 2/3

**Монти Холл на интервью:** правильный ответ (2/3 при смене) важен, но ещё важнее - объяснение. Ключ: после открытия двери условная вероятность перераспределяется. P(приз за первой дверью | открыта пустая) = 1/3, P(приз за другой | открыта пустая) = 2/3. Байесовское обновление.

Задача о купонах: E[X] = n·Hₙ ≈ n·ln(n). Для n=52 (карты): E[X] ≈ 236. Это «реклама» - почему коллекционные наборы так хорошо продаются: в среднем приходится купить в 4.5 раза больше карт, чем различных типов.

Математические рассуждения под давлением интервью

На уровне Staff/Senior Engineer на Google и Meta ожидают умения доказывать корректность алгоритмов, оценивать сложность не только через Big-O, но и через нижние оценки (Omega), и объяснять почему что-то работает математически строго. Это не про заучивание теорем - это про структуру мышления.

**Техники доказательств на интервью:** - **Инвариант цикла (Loop invariant):** что истинно до/во время/после цикла - **Индукция:** если верно для n, покажи для n+1 - **Доказательство от противного:** assume A, derive contradiction - **Pigeonhole principle:** n+1 объектов в n ящиках → хотя бы два в одном - **Двойной подсчёт:** посчитать одно и то же двумя способами

**Как отвечать на «докажите это» на интервью:** 1. Назвать метод доказательства («Воспользуюсь индукцией / противоречием / инвариантом») 2. Чётко сформулировать базовый случай или инвариант 3. Показать шаг индукции или нарушение 4. Подытожить вывод одним предложением Интервьюер проверяет структуру мышления, не идеальность формулировок.

Принцип Дирихле (pigeonhole) - самый частый неожиданный инструмент на интервью. «Докажите, что в строке длиной n+1 над алфавитом {a,...,z^n} есть повторяющийся символ» - pigeonhole. «Докажите, что в любой последовательности n²+1 различных чисел есть монотонная подпоследовательность длины n+1» - тоже pigeonhole (теорема Эрдёша-Секереша).

Ключевые идеи

• **Подсчёт:** C(n,k) для неупорядоченного выбора, P(n,k) для упорядоченного, stars-and-bars для разложений, включения-исключения для ограничений.
• **Двудольность:** граф двудольный ↔ нет нечётных циклов. Проверка BFS за O(V+E). Применение: расписания, matching, 2-раскраска.
• **SCC:** алгоритм Косараю - два DFS + транспонированный граф. Применение: зависимости пакетов, компиляторы.
• **Вероятностные задачи:** задача о купонах E[X]=n·H(n), Монти Холл через байесовское обновление, E[quicksort] через индикаторы.
• **Доказательства:** инвариант цикла, индукция, Дирихле (pigeonhole), двойной подсчёт, нижние оценки через дерево решений.

Связанные темы

Эта тема - финальная точка курса, объединяющая всё в интервью-навыки:

• Discrete Math в CS — NP-полнота и вероятностные алгоритмы - теоретическая база для распознавания типа задачи на интервью
• Случайные величины — E[X] через индикаторы, задача о купонах и анализ quicksort - прямые приложения E[X] и линейности
• Комбинаторика — Формулы подсчёта (C(n,k), stars-and-bars) - фундамент для интервью-задач на подсчёт

Вопросы для размышления

• получили задачу на интервью: «Сколько способов расставить n не бьющих ферзей на доске n×n?». Как за 30 секунд определяете тип задачи и правильный подход?
• Как бы объяснили принцип Дирихле (pigeonhole) без технических терминов, если интервьюер на System Design попросил доказать, что у любой хеш-функции с m выходами есть коллизии при m+1 входах?
• На Staff Engineer интервью в Google звучит вопрос: «Докажите, что данный алгоритм распределения задач по серверам оптимален». Какую математическую технику выбрать и почему?

Связанные уроки

• alg-01-big-o