Подход к задаче на собесе

Техническое собеседование по алгоритмам — это не экзамен на знание наизусть, а проверка инженерного мышления: умеете ли вы декомпозировать задачу, оценивать варианты решения, выбирать оптимальный и обосновывать свой выбор. Интервьюер оценивает процесс, а не только финальный код. В этой главе разбираем системный пятишаговый подход, отличающий Senior от Middle.

Когда применять / Мотивация

Этот фреймворк нужен на любом алгоритмическом собесе уровня Middle+ и в ежедневной работе при проектировании решений. Junior сразу кодит, Middle обдумывает решение, Senior проговаривает 2–3 варианта с trade-off’ами до первой строки кода. Это демонстрирует зрелость: на продакшене вы не пишете код, не обсудив архитектуру с командой.

Тот же навык всплывает в реальной разработке:

• проектирование индекса БД — выбор между B-tree (порядок) и hash (точные ключи);
• оптимизация поиска в коде — линейное сканирование с кешем vs бинарная структура;
• архитектура системы — где нужна амортизированная O(1) (Redis hash), а где достаточно O(log n) (B-tree в PostgreSQL).

Tech Lead регулярно объясняет junior’ам, почему Set быстрее массива для проверки существования — это тот же навык, что и на алгоритмических собесах.

Идея / Как работает

Задачу решаем в 5 этапов:

1. Уточнение требований — размер входа n, диапазоны значений, ограничения по памяти, частота вызовов (онлайн/оффлайн), допустимые edge cases.
2. Brute-force — озвучиваем наивное решение и его сложность, даже если оно O(n³). Это показывает, что вы поняли задачу.
3. Оптимизация — называем 2–3 улучшенных подхода, сравниваем Big-O, выбираем лучший с обоснованием.
4. Код — пишем чистое решение с комментариями к ключевым строкам.
5. Edge cases — обсуждаем пустой вход, дубликаты, переполнения, граничные условия.

Senior-вопрос

«Что важнее — минимизировать время или память?» — этот вопрос на старте показывает системное мышление и сразу выводит обсуждение на уровень trade-off’ов.

Реализация

Возьмём классическую задачу Two Sum: найти индексы двух чисел в массиве, сумма которых равна target. Покажем эволюцию мышления через три подхода — это типичная структура рассуждения на Senior-собесе.

Подход 1: Brute-force O(n²)

Перебираем все пары индексов и проверяем сумму.

// Brute-force — два вложенных цикла
function twoSumBrute(nums: number[], target: number): [number, number] | null {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return null;
}

Время O(n²), память O(1). При n = 10⁵ получим 10¹⁰ операций — недопустимо.

Подход 2: Sort + Two Pointers O(n log n)

Сортируем массив, затем два указателя сходятся к ответу. Сумма меньше target → двигаем left вправо, больше → right влево.

function twoSumSorted(nums: number[], target: number): [number, number] | null {
  // Сохраняем исходные индексы перед сортировкой
  const indexed = nums.map((val, idx) => [val, idx] as const);
  indexed.sort((a, b) => a[0] - b[0]);

  let left = 0, right = indexed.length - 1;
  while (left < right) {
    const sum = indexed[left][0] + indexed[right][0];
    if (sum === target) return [indexed[left][1], indexed[right][1]];
    if (sum < target) left++;
    else right--;
  }
  return null;
}

Время O(n log n) из-за сортировки, память O(n) для пар [value, index].

Подход 3: Hash Map O(n) — оптимально

Один проход. Для каждого nums[i] ищем complement = target - nums[i] в hash map.

function twoSumHash(nums: number[], target: number): [number, number] | null {
  const map = new Map<number, number>(); // число → его индекс
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    map.set(nums[i], i);
  }
  return null;
}

Время O(n), память O(n).

Трассировка подхода 3

Вход: nums = [1, 4, 3, 7], target = 10.

Начало: map = {}
i=0: nums[0]=1, complement=9, map не содержит 9 → map.set(1, 0)
     map = {1:0}
i=1: nums[1]=4, complement=6, map не содержит 6 → map.set(4, 1)
     map = {1:0, 4:1}
i=2: nums[2]=3, complement=7, map не содержит 7 → map.set(3, 2)
     map = {1:0, 4:1, 3:2}
i=3: nums[3]=7, complement=3, map содержит 3 (индекс 2)
     → return [2, 3]

Сложность

Подход	Время	Память	Когда использовать
Brute-force	O(n²)	O(1)	n ≤ 100, простота важнее скорости
Sort + Two Pointers	O(n log n)	O(n)	Массив уже отсортирован или не дозволено доп. памяти
Hash Map	O(n)	O(n)	Оптимально для больших n

Hash-решение — линейное время, это физический минимум: мы обязаны прочитать все элементы массива хотя бы раз.

Типичные ошибки и подводные камни

• Пустой массив: nums = [] → возвращаем null. Защитная проверка nums.length < 2 в начале функции.
• Один элемент: пара невозможна. Но задача требует разные индексы, поэтому [5, 5] с target=10 → валидно ([0, 1]).
• Дубликаты: [3, 3], target=6 → правильный ответ [0, 1]. Hash-решение корректно: сначала сохраняем 3:0, потом находим complement=3 и возвращаем [0, 1].
• Нет решения: [1, 2], target=10 → return null. Не забудьте обработать.
• Отрицательные числа: hash работает с любыми числами, проблем нет.
• Порядок возврата: некоторые задачи требуют [меньший, больший]. Hash-решение гарантирует это автоматически.

Главные грехи на собесе

1. Сразу писать код, не проговорив подход.
2. Не называть Big-O своего решения.
3. Не задавать уточняющих вопросов: при n ≤ 100 даже O(n³) приемлемо, при n ≤ 10⁶ — нужно ≤ O(n log n).

Follow-up вопросы интервьюера

• Почему hash, а не sort + two pointers? Hash — O(n), sort — O(n log n). При n = 10⁶ разница 10⁶ vs 2·10⁷ операций. Trade-off: hash требует O(n) памяти, two pointers — O(1) при сортировке на месте.
• Что если массив уже отсортирован? Two pointers лучше: O(n) времени, O(1) памяти, без hash.
• Найти ВСЕ уникальные пары с суммой target. Сортируем + two pointers + пропуск дубликатов: while (left < right && nums[left] === nums[left+1]) left++;
• Three Sum — все тройки с суммой 0. Сортируем, фиксируем nums[i], для подмассива применяем two sum за O(n). Итого O(n²).
• Огромный массив, не влезает в память. External merge sort + two pointers по отсортированным блокам, либо потоковая обработка с hash map (если уникальных значений мало).
• Обобщение до k-Sum. Рекурсивно сводим k-Sum к (k-1)-Sum фиксацией первого элемента. Сложность O(n^(k-1)).

Формулы для быстрой оценки

• log₂(10⁶) ≈ 20, log₂(10⁹) ≈ 30 — глубина бинарного поиска/дерева.
• 2¹⁰ = 1024 ≈ 10³ — оценка памяти.
• Лимит CPU: ~10⁸ простых операций за 1 секунду.
• n log n при n=10⁶ ≈ 2·10⁷ операций — укладывается в секунду.
• n² при n=10⁴ — граница, при n=10⁵ — TLE.

Чеклист на собес

• Уточнил размер n, диапазоны, ограничения памяти.
• Озвучил brute-force и его Big-O.
• Предложил 2–3 оптимизации с обоснованием.
• Назвал Big-O финального решения до написания кода.
• Перечислил edge cases и обсудил их обработку.
• Написал чистый код с комментариями.
• Прогнал решение на простом примере (трассировка).
• Проговорил trade-off’ы time vs space.

Golden rule

Код должен быть правильным, читаемым и объяснённым. Идеально оптимизированное решение, которое вы не можете пояснить или не учли edge cases — хуже простого, но проработанного. Интервьюер оценивает процесс мышления, а не только результат.