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

Дейкстра доказал свой shortest path алгоритм за 20 минут на салфетке в кафе. С тех пор LeetCode задают его триллионам кандидатов - и почти никто не понимает, что это была оптимизационная задача.

• Twitter feed: 100M DAU × 300 follows = 30B fan-out связей. Pure push - 1B записей на твит celebrity. Hybrid push+pull снижает write amplification в 100x.
• Google PageRank - линейная задача оптимизации на 100B страниц: $r = (1 - d) \cdot \mathbf{1} + d M r$. Power iteration сходится за 50-100 итераций.
• AWS spot instance + checkpointing экономит 60% от on-demand. Ценой: вероятность interruption ~5% в час. Это явный Pareto trade-off.
• Dynamic batching на GPU inference: max_batch=32, max_wait_ms=10. Throughput вырастает в 4x, P99 latency - всего на 10 ms.

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

• Optimization in ML and Production

Алгоритмические задачи как оптимизация

## Shortest Path - это оптимизационная задача Dijkstra's algorithm решает задачу оптимизации: ``` min sum_{(u,v) in path} w(u,v) subject to: path начинается в s path заканчивается в t path - связный (каждый узел соединён с следующим) Dijkstra = жадная оптимизация по принципу nearest unvisited: Инвариант: d[v] - минимальная стоимость пути от s до v Шаг: взять v* = argmin_{v} d[v] среди непосещённых → Greedy choice property: d[v*] уже оптимально! ``` ## Knapsack - это ILP ``` Knapsack problem: max sum_i v_i * x_i (максимизировать ценность) s.t. sum_i w_i * x_i <= W (ограничение по весу) x_i in {0, 1} (бинарные переменные) → Это Integer Linear Programming (ILP) с n бинарными переменными! 0-1 Knapsack DP = Branch & Bound с конкретной структурой: dp[i][w] = max value with first i items and capacity w Интерпретация через оптимизацию: dp[i][w] = relaxed subproblem: solve ILP on items 1..i with capacity w, already fixed ``` ## A* как эвристическая оптимизация ``` A* search минимизирует: f(n) = g(n) + h(n) где: g(n) = фактическая стоимость пути от start до n h(n) = эвристика (оценка стоимости от n до goal) Обычный Dijkstra: h(n) = 0 (нет эвристики) A* с h = Euclidean distance: быстрее для геометрических графов Гарантия оптимальности: если h(n) <= реальное расстояние (h - admissible), A* находит оптимальный путь. → A* = оптимизация f(n) с admissible lower bound аналог: нижняя граница в Branch & Bound! ``` ## LeetCode задачи через линзу оптимизации ```python # Задача: Jump Game II (LC #45) # Найти минимальное число прыжков до конца массива # → Optimization: min jumps s.t. достичь конец def jump(nums): """Greedy: на каждом шаге максимизировать reach""" n = len(nums) jumps = 0 # число прыжков (objective) current_end = 0 # текущая граница текущего прыжка farthest = 0 # максимально достижимая позиция for i in range(n - 1): # Максимизировать reach при каждой позиции farthest = max(farthest, i + nums[i]) if i == current_end: # конец текущего прыжка jumps += 1 current_end = farthest return jumps # Почему greedy оптимален? # Это exchange argument: # Если оптимальное решение делает прыжок X короче нашего greedy, # мы можем заменить его на наш (не хуже) → greedy = optimal # Задача: Coin Change (LC #322) # → Unbounded Knapsack (разновидность ILP) # → DP = точный алгоритм для специальной структуры ILP def coinChange(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 for coin in coins: for x in range(coin, amount + 1): dp[x] = min(dp[x], dp[x - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1 ``` ## Интервью: как говорить об оптимизации ``` Вопрос: «Почему этот алгоритм оптимален?» НЕ НАДО: «Я протестировал на примерах и он работает» НАДО (3 способа доказать оптимальность): 1. Exchange argument: «Предположим, существует лучшее решение. Я могу показать, что мы можем «обменять» шаги и получить решение не хуже нашего greedy.» 2. Optimal substructure: «Задача имеет optimal substructure: оптимальное решение задачи содержит оптимальные решения подзадач. → Динамическое программирование применимо.» 3. Lower bound: «Вот нижняя граница для любого алгоритма: [bound]. Наш алгоритм достигает этой границы → он оптимален.» ```

System Design как задача оптимизации

## Каждый system design вопрос - это multi-objective optimization ``` Пример: «Спроектируй Twitter feed» Objectives (конкурирующие): min latency(read) (время загрузки ленты) min cost(storage) (стоимость хранения) max consistency(data) (актуальность данных) max availability (SLA uptime) Constraints: DAU = 100M users avg follows = 300 tweets/day = 500M → Это Pareto optimization! Нет одного «правильного» решения, есть Pareto-оптимальные архитектуры. ``` ## Pull vs Push: явный trade-off ```python # PULL модель (compute on read): # latency_read ~ O(follows) = O(300) <- медленно для больших follows # storage = O(tweets only) # consistency = perfect (always fresh) # PUSH модель (fan-out on write): # latency_read ~ O(1) <- мгновенно # storage = O(DAU * follows) ~ 30B записей # latency_write ~ O(follows) = O(300) <- медленно для celebrity # Hybrid (реальный Twitter/Meta подход): def get_feed(user_id): # Кэш для обычных пользователей (PUSH) cached_feed = redis.get(f'feed:{user_id}') if cached_feed: return cached_feed # Для celebrity followers - pull on demand celeb_tweets = [] for celeb in get_celebrities_following(user_id): celeb_tweets.extend(db.get_recent_tweets(celeb, limit=10)) # Merge с кэшированной частью regular_feed = redis.get(f'feed_regular:{user_id}') or [] merged = merge_sorted(regular_feed, celeb_tweets)[:100] return merged # Это именно Pareto-компромисс: # regular users -> push (O(1) read) # celebrities -> pull (avoid O(300M) fan-out) ``` ## Reduce latency: типичные интервью вопросы ``` Вопрос: «Как уменьшить latency нашей рекомендательной системы с 500мс до 50мс?» Оптимизационный фрейм: min latency s.t. accuracy >= threshold Стратегии (каждая - точка на Pareto фронте): 1. Кэширование предподсчитанных рекомендаций: latency: O(1) read, cost: O(DAU * recs) storage trade-off: staleness vs freshness 2. Модель меньшего размера (distillation): latency: model_size * constant trade-off: accuracy vs speed 3. Approximate Nearest Neighbor (HNSW, FAISS): exact k-NN: O(N*d), HNSW: O(log N * d) trade-off: recall % vs speed 4. Two-stage ranking (candidate retrieval + reranking): Stage 1 (retrieval): fast, low precision, 1000 candidates Stage 2 (reranking): slow, high precision, top 10 trade-off: quality vs throughput FAANG ответ структура: 1. Определить bottleneck (где именно 500мс тратятся?) 2. Предложить 2-3 Pareto-оптимальных точки 3. Выбрать с явным обоснованием trade-off ``` ## Reduce cost: оптимизация инфраструктуры ```python # Классическая задача: оптимизировать стоимость ML pipeline # Формализация: # min cost(instance_type, count) # s.t. throughput >= 1000 req/sec # latency_p99 <= 100 ms # Типичные решения-решения на Pareto фронте: # 1. Spot instances (AWS) + checkpointing: config = { 'instance_type': 'g4dn.xlarge', # $0.526/h vs $1.204/h on-demand 'pricing': 'spot', 'spot_price': 0.20, # ~60% дешевле 'interruption_handling': True, # автоматический перезапуск 'checkpoint_freq': '10min' # потерять max 10 мин работы } # 2. Batching requests (throughput-latency trade-off): def dynamic_batching(request_queue, max_batch=32, max_wait_ms=10): """ Накапливать запросы до max_batch или max_wait_ms. GPU throughput растёт линейно с batch, latency растёт незначительно. """ batch = [] deadline = time.time() + max_wait_ms / 1000 while len(batch) < max_batch and time.time() < deadline: if queue.not_empty(): batch.append(queue.get()) return process_batch(batch) # один inference call # 3. Cache popular predictions (Pareto: accuracy vs freshness): # Если 20% запросов покрывают 80% users (Zipf law), # кэшируем топ-20% → 80% cache hit rate → 80% меньше compute ```

Инженерные решения как constrained optimization

## Любое инженерное решение - это оптимизационная задача Формулировка решения через язык оптимизации даёт: 1. Явно заданная objective function (что оптимизируется) 2. Названные constraints (что нельзя нарушать) 3. Явные trade-offs ## Выбор базы данных: formalized ``` Задача: выбрать БД для хранения пользовательских сессий (100K RPS) Objective: min latency_read Constraints: availability >= 99.9% (SLA) durability = strong (нельзя терять сессии) cost <= $X/month ops_complexity <= medium (команда из 3 человек) Кандидаты на Pareto фронте: Redis: latency=0.1ms, consistency=eventual, cost=high Postgres: latency=1ms, consistency=strong, cost=low DynamoDB: latency=0.5ms, consistency=eventual, cost=medium Cassandra: latency=0.3ms, consistency=tunable, cost=medium Ответ зависит от relative importance objectives: Если latency critical: Redis (+ persistence включена) Если cost critical + strong consistency: Postgres + read replicas Если global scale: DynamoDB ``` ## Microservices vs Monolith: optimization problem ```python # Это задача организационной/архитектурной оптимизации objectives = [ 'deployment_velocity', # скорость деплоя фич 'operational_complexity', # сложность эксплуатации 'team_autonomy', # независимость команд 'latency', # network hops между сервисами 'cost' # инфраструктура + DevOps время ] # Monolith: # deployment_velocity: low (всё деплоится вместе) # operational_complexity: low (один процесс) # team_autonomy: low (shared codebase conflicts) # latency: zero (in-process calls) # cost: low # Microservices: # deployment_velocity: high (independent deploys) # operational_complexity: high (service mesh, observability) # team_autonomy: high (own repo/deploy/runtime) # latency: higher (network + serialization) # cost: higher (more infra) # Решение зависит от constraints: def choose_architecture(team_size, product_maturity, traffic): if team_size < 10 and product_maturity == 'early': return 'monolith' # преждевременная оптимизация - зло elif team_size > 50 and traffic > '100k rps': return 'microservices' else: return 'modular_monolith' # Pareto-оптимальный компромисс ``` ## Типичные FAANG вопросы с optimization framing ``` Вопрос: «Как бы оптимизировать нашу ML inference pipeline?» Структура ответа: 1. Сначала: определить objective и constraints «Что оптимизируется? Latency P99? Cost? Throughput? При каких constraints на accuracy и availability?» 2. Measurement first: «Без профилирования bottleneck неизвестен. Первый шаг: добавить трейсинг и найти самый медленный компонент.» 3. Pareto анализ: «Несколько точек на Pareto фронте: a) Кэш предсказаний: latency O(1), accuracy -3% b) Model distillation: latency -50%, accuracy -1% c) INT8 quantization: latency -60%, accuracy -0.5% d) Увеличить replicas: latency -0%, cost +50%» 4. Recommendation с explicit trade-off: «Рекомендую INT8 quantization (c) - лучший latency/accuracy trade-off. Если accuracy нельзя трогать - model distillation (b). Кэш (a) подходит только если запросы повторяются (персонализация исключена).» Вопрос: «Как принять решение деплоить фичу на 100%?» Optimization framing: Objective: max(engagement_delta) Constraint: error_rate <= baseline, latency <= +10ms, P(harm) < 0.001 Method: A/B test → sequential hypothesis testing (minimize sample size s.t. statistical power >= 0.8, alpha <= 0.05) ``` ## Паттерн ответа на любой engineering question ``` 1. Clarify objectives: «Что максимизируем/минимизируем?» «Какие hard constraints vs soft preferences?» 2. Establish baseline: «Что сейчас? Нужны числа перед оптимизацией.» 3. Enumerate Pareto-optimal solutions: «N решений с разными trade-offs: [решение] → [objective улучшение] при [constraint cost]» 4. Recommend with reasoning: «Выбор [X] потому что [objective priority], при условии [constraint]. При [изменение контекста] пересмотр в сторону [Y].» ```

Связь с предыдущим

В Optimization в ML и Production проявилось, как разворачивать модели быстрее - SAM, QAT, fusion. Этот урок переносит ту же оптимизационную линзу на алгоритмические задачи и system design. Greedy, DP, A* - всё это специальные случаи оптимизации с гарантиями. System design - то же самое, только Pareto-фронт расположен в пространстве latency/cost/consistency.

• Optimization в ML и Production — ML-оптимизация - частный случай. Та же линза работает на алгоритмах и архитектуре
• Алгоритмы и сложность — Big-O измеряет, насколько алгоритм оптимален относительно lower bound

Итоги

• Любой LeetCode greedy = оптимизация с exchange argument. Без доказательства - просто угадывание.
• 0-1 Knapsack DP - это точное решение ILP для специальной структуры с псевдополиномиальной сложностью O(n·W).
• A* = Dijkstra с admissible lower bound. Branch & Bound в чистом виде.
• System design - multi-objective optimization. Pareto front (latency, cost, consistency) - нет одного 'правильного' решения.
• Twitter feed = celebrity problem: fan-out O(followers) у Маска. Hybrid push+pull - Pareto-оптимальный компромисс.
• Сильный кандидат: clarify objectives → measure baseline → enumerate Pareto-options → recommend with explicit trade-off.

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

• Если все алгоритмы интервью можно описать как оптимизацию, что меняется в подходе к решению нового LeetCode-вопроса?
• В каких ситуациях monolith Pareto-доминирует над microservices, и какие константы (team size, traffic) запускают переход?
• Можно ли применить optimization framing к non-technical decisions (приоритизация фич, найм)? Где этот подход ломается?

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

• opt-15 — Вопросы на собеседовании опираются на ML/Production знания
• ml-09-gradient-descent — Gradient descent - обязательная тема собеседований по ML
• alg-01-big-o — Сложность алгоритмов - базовый вопрос на интервью
• db-11-query-optimization — Query optimization - частый вопрос на backend-интервью
• dl-09 — Сравнение AdamW и SGD - классический вопрос про оптимизацию
• calc-01-sequences