Complexity на собеседовании

Собеседование в Amazon на L6: интервьюер просит распределить 200 batch-задач по 100 серверам с минимальным makespan. Junior пишет жадный алгоритм за 5 минут. Senior за 5 минут говорит 'это NP-трудно, сведение к Partition' и обсуждает 2-approximation алгоритм Грэхема. Разница в зарплате - $80k/год.

• **Google Maps** для маршрутизации использует ALT (A* + landmarks + triangle inequality) - эвристика поверх Dijkstra, ускоряющая запросы в 1000x
• **Netflix** решает задачу распределения контента по CDN-нодам как mixed-integer programming в Gurobi - подход вместо рукописных эвристик
• **OpenAI** train scheduling для GPU-кластера использует ILP-solver - формулирует задачу как линейные ограничения, не пишет алгоритм сам

Сведения (reductions)

На собеседовании в Google интервьюер просит распределить рекламные показы по серверам так, чтобы суммарная нагрузка была минимальна. Задача звучит конкретно, но опытный кандидат сразу узнаёт **bin packing** - классическую NP-трудную задачу. Этот рефлекс - 'свести знакомую сложную задачу к новой' - и есть суть **reductions**: формального преобразования A в B такого, что решение B даёт решение A.

Существуют два типа сведений. **Polynomial-time reduction (A ≤_p B)** - 'B не легче A': если есть полиномиальный алгоритм для B, есть и для A. **Karp reduction** - частный случай для decision problems. Если 3-SAT сводится к задаче X за полиномиальное время, то X тоже NP-трудна. На собеседовании важно не доказывать сведение строго, а **показать структурную аналогию**: 'это та же задача о покрытии множеств, только переменные называются по-другому'.

**Сведение vs алгоритм**: реальное собеседование редко требует написать сведение код-в-код. Достаточно показать, что задача 'эквивалентна по сложности' известной NP-трудной - и предложить approximation или heuristic.

Доказательства NP-трудности

На собеседовании на принципала Amazon задают: 'У вас 100 серверов с разной мощностью и 200 batch-задач. Минимизируйте время завершения последней задачи'. Кандидат, который сразу пишет жадный алгоритм - junior. Кандидат, который говорит: 'Это makespan scheduling, NP-трудно, докажу сведением от Partition' - senior. NP-трудность не блокирует решение, она блокирует ожидание оптимального решения.

Канонический шаблон доказательства NP-трудности: (1) Выбрать известную NP-трудную задачу X. (2) Описать преобразование экземпляра X в экземпляр вашей задачи Y за полиномиальное время. (3) Доказать эквивалентность: X имеет решение тогда и только тогда, когда Y имеет решение. На собеседовании достаточно сделать шаги 1 и 2 неформально; полное доказательство займёт 20 минут.

**Канонический набор сведений** для собеседования: 3-SAT, Vertex Cover, Independent Set, Clique, Hamiltonian Path, Subset Sum, Partition, TSP, Bin Packing, Graph Coloring. Знание этих 10 задач покрывает 90% случаев.

Дизайн алгоритмов после hardness

TSP NP-трудна, но Google Maps строит маршруты по 100 городам за секунды. Knapsack NP-трудна, но любой ML-движок решает её на feature selection. Реальные NP-трудные задачи решаются - вопрос только какой ценой. На собеседовании важно владеть **арсеналом подходов**: 2-approximation, FPTAS, branch-and-bound, LP relaxation, эвристики (greedy, simulated annealing, beam search), ILP-solvers.

**Approximation algorithms** дают гарантированный фактор от оптимума за полиномиальное время. **FPTAS (Fully Polynomial-Time Approximation Scheme)** - даже сильнее: за O(poly(n, 1/ε)) находит решение с гарантией (1+ε)·OPT. **Parameterized algorithms (FPT)** работают экспоненциально только по одному параметру k (например, по размеру vertex cover), а не по n. На малых k - это практичные алгоритмы.

**Что ответить, если интервьюер давит**: 'Какой будет апроксимационный фактор?'. Знание классических результатов: Vertex Cover - 2-approx, TSP - 1.5 (метрический), Set Cover - ln(n), Knapsack - FPTAS, Bin Packing - 11/9 + O(1).

Компромиссы (time/space/approximation)

Кандидат на собеседовании в FAANG предлагает hash table за O(1). Интервьюер: 'А память?'. O(n) - но в реальной системе с миллиардом ключей это 100 ГБ RAM. Кандидат должен видеть **компромиссы**: time vs space, exact vs approximate, throughput vs latency, fairness vs efficiency. NP-трудность - частный случай, но даже в P-задачах компромиссы решают всё.

Классический пример - **Bloom filter**: жертвует точностью (false positives) ради 10x экономии памяти и O(1) checks. **Approximate counters (HyperLogLog)** считают unique users в стриме с погрешностью 2% за 16 КБ вместо ГБ HashSet. **Probabilistic data structures** - целый класс структур для компромисса space-vs-accuracy.

**Принцип на собеседовании**: всегда задавать уточняющий вопрос про bounds и SLO. 'Сколько уникальных значений? Какой допустимый error rate? Какая память доступна?' - это перевод задачи из абстрактной в конкретную, что отличает senior от junior.

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

• **Reductions** - инструмент распознавания: задача сводится к TSP/Knapsack/SAT? значит, в NP-трудных
• **Hardness-доказательство** на собеседовании - не формальное, а структурная аналогия с канонической задачей за 2 минуты
• **Арсенал после hardness**: approximation (Christofides 1.5x для TSP), FPTAS для Knapsack, ILP-solvers (Gurobi, CPLEX) для произвольных задач
• **Probabilistic structures (Bloom, HLL)** - компромисс точность vs память: 0.8% погрешности ценой 500 000x экономии
• Главный сигнал senior: задаёт уточняющие вопросы про SLO и bounds, переводит абстрактную задачу в конкретную

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

Возвращаясь к собеседованию в FAANG: умение распознать NP-трудность и предложить approximation - граница между junior и senior. Эта тема связана с:

• P, NP и классы сложности — База для понимания NP-трудности; без неё reductions становятся механическим упражнением без смысла
• Approximation алгоритмы — Конкретные техники (LP-relaxation, primal-dual, дерандомизация) для построения approximation с гарантиями

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

• На реальном собеседовании времени 45 минут. Сколько уделить hardness-доказательству, а сколько - алгоритму? Где проходит граница 'достаточно' для интервьюера?
• Если задача NP-трудна, но интервьюер ожидает 'оптимальный' ответ - что это: проверка на знание сложности или ожидание брутфорса для маленьких n? Как распознать намерение?
• Современные ML-методы (GNN-based combinatorial optimization) решают TSP лучше Christofides на конкретных распределениях данных. Меняет ли это подход к собеседованиям через 5 лет?

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

• cplx-04 — P vs NP - базовый вопрос для решения задач на собеседовании
• cplx-07 — NP-полные задачи часто встречаются в задачах на интервью
• alg-22-backtracking — Бэктрекинг - стандартный инструмент для NP-задач на интервью
• alg-01-big-o — Big O - основной язык анализа на техническом интервью