Как пройти техническое собеседование: алгоритмы и структуры данных

Введение

Техническое собеседование в крупных IT-компаниях почти всегда включает блок по алгоритмам и структурам данных. Даже если в реальной работе вы редко пишете свой quicksort, на интервью ожидают, что вы понимаете асимптотику, умеете рассуждать вслух и аккуратно превращать идею в код. В этой статье разберём, как системно подготовиться к таким собеседованиям, какие темы обязательны, и как решать задачи без ступора у доски.

Что обычно спрашивают

Типичный набор тем для middle-разработчика:

• массивы, строки, хэш-таблицы;
• стек, очередь, дек;
• связные списки;
• деревья и графы (DFS, BFS);
• сортировки и бинарный поиск;
• динамическое программирование;
• жадные алгоритмы;
• базовая оценка сложности по времени и памяти (Big O).

Задачи делятся на три уровня: easy (разминка), medium (основная часть собеседования) и hard (фильтр для senior). Стратегия — уверенно решать все easy, большинство medium и понимать подход к hard.

Big O: язык, на котором говорит интервьюер

Прежде чем писать код, всегда называйте сложность. Это показывает, что вы думаете про эффективность, а не только про корректность.

// O(n^2) — наивный поиск пары с заданной суммой
function twoSumNaive(nums, target) {
  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) — то же самое, но через хэш-таблицу
function twoSum(nums, target) {
  const seen = new Map(); // значение -> индекс
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return null;
}

Когда переходите от O(n^2) к O(n), вслух проговаривайте: «жертвую памятью O(n) ради линейного времени». Интервьюер любит такие компромиссы.

Хэш-таблицы и частотный анализ

Большая часть medium-задач на массивах и строках решается через Map или Set. Анаграммы, подсчёт уникальных, поиск дубликатов, скользящее окно — везде хэш.

// Проверка, являются ли строки анаграммами. O(n) по времени и памяти
function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const freq = new Map();
  for (const ch of a) freq.set(ch, (freq.get(ch) ?? 0) + 1);
  for (const ch of b) {
    const left = (freq.get(ch) ?? 0) - 1;
    if (left < 0) return false;
    freq.set(ch, left);
  }
  return true;
}

Двухуказательная техника и скользящее окно

Эти приёмы превращают квадратичные решения в линейные на отсортированных массивах и строках.

// Длина самой длинной подстроки без повторов. O(n)
function lengthOfLongestSubstring(s) {
  const lastIndex = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    // сдвигаем левую границу, если символ уже встречался в окне
    if (lastIndex.has(ch) && lastIndex.get(ch) >= left) {
      left = lastIndex.get(ch) + 1;
    }
    lastIndex.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Деревья и обход графов

DFS и BFS — обязательный минимум. Дерево — это частный случай графа без циклов, поэтому шаблон один.

// BFS по дереву: возвращает значения по уровням
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length > 0) {
    const level = [];
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Для DFS на практике используют рекурсию или явный стек — оба варианта стоит уметь писать.

Динамическое программирование

DP пугает, но 80% задач сводятся к шаблону «состояние + переход». Начинайте с рекурсии с мемоизацией, потом переходите к табличному решению.

// Классика: число способов подняться по лестнице. O(n) времени, O(1) памяти
function climbStairs(n) {
  if (n <= 2) return n;
  let prev = 1;
  let curr = 2;
  for (let i = 3; i <= n; i++) {
    const next = prev + curr; // переход состояния
    prev = curr;
    curr = next;
  }
  return curr;
}

Как вести себя на интервью

Алгоритм решения задачи у доски:

1. Уточните вход и выход, спросите про граничные случаи.
2. Проговорите наивное решение и его сложность.
3. Предложите оптимизацию и обоснуйте, почему она работает.
4. Пишите код небольшими блоками, комментируйте вслух.
5. Прогоните пример руками, найдите off-by-one.
6. Назовите итоговую сложность по времени и памяти.

Молчаливое программирование — главная ошибка. Интервьюер оценивает ход мыслей, а не только результат.

Частые ошибки

• Сразу бросаться писать код, не уточнив условие и ограничения на вход.
• Игнорировать пустой массив, одну букву в строке, null в корне дерева.
• Путать Map и обычный объект и из-за этого ловить O(n) на каждом доступе.
• Использовать array.shift() в горячем цикле, превращая O(n) в O(n^2).
• Не проверять решение на тестовом примере перед тем, как сказать «готово».
• Заучивать решения наизусть вместо понимания идеи — на чуть изменённой задаче такой подход разваливается.

Заключение

Подготовка к секции алгоритмов — это не зубрёжка LeetCode, а тренировка мышления: распознавание паттернов, оценка сложности, умение проговаривать решение. Решайте задачи каждый день по чуть-чуть, разбирайте чужие решения и обязательно пишите код руками, а не только в голове. Через пару месяцев такого режима технические собеседования перестают быть лотереей и превращаются в предсказуемый разговор по знакомым шаблонам.