Алгоритмы и структуры данных: как готовиться к собеседованию

Введение

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

Зачем нужны алгоритмы на собеседовании

Собеседующие редко ожидают, что кандидат помнит наизусть код быстрой сортировки. Важнее показать процесс мышления: как разбить задачу на подзадачи, оценить сложность по времени и памяти, предложить несколько вариантов решения и выбрать оптимальный. Алгоритмические задачи — это способ проверить именно этот навык, а не знание конкретного API.

Сложность алгоритмов: Big O

Big O описывает, как растёт время выполнения или расход памяти при увеличении размера входных данных. На собеседовании важно уметь быстро прикинуть сложность своего решения.

Основные классы сложности

• O(1) — константное время, не зависит от размера данных
• O(log n) — логарифмическая сложность, типична для бинарного поиска
• O(n) — линейная сложность, один проход по данным
• O(n log n) — типична для эффективных сортировок
• O(n^2) — вложенные циклы по одним и тем же данным

// O(n) — один проход по массиву
function sum(arr) {
  let total = 0;
  for (const num of arr) {
    total += num;
  }
  return total;
}

Массивы и хеш-таблицы

Хеш-таблица (в JS — Map или обычный объект) даёт доступ к элементу за O(1) в среднем случае. Это делает её главным инструментом для задач на поиск дубликатов, подсчёт частот и проверку наличия элемента.

Пример: поиск дубликатов

function hasDuplicate(arr) {
  // используем Set для хранения уже увиденных значений
  const seen = new Set();
  for (const item of arr) {
    if (seen.has(item)) {
      return true;
    }
    seen.add(item);
  }
  return false;
}

Такое решение работает за O(n) по времени и O(n) по памяти, что почти всегда лучше, чем вложенный цикл со сложностью O(n^2).

Стек и очередь

Стек работает по принципу LIFO (последний пришёл — первый вышел), очередь — по принципу FIFO (первый пришёл — первый вышел). В JavaScript стек легко реализовать через массив и методы push/pop, а очередь — через push/shift.

class Stack {
  constructor() {
    this.items = [];
  }

  push(value) {
    this.items.push(value);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }
}

Стек часто используют для задач на проверку сбалансированности скобок, а очередь — для обхода графа в ширину.

Связный список

Связный список хранит элементы в узлах, каждый из которых ссылается на следующий. В отличие от массива, вставка в начало списка занимает O(1), а не O(n).

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function addToFront(head, value) {
  const node = new ListNode(value);
  node.next = head;
  return node;
}

Деревья и графы

Дерево — частный случай графа без циклов, где каждый узел имеет одного родителя. Бинарное дерево поиска позволяет искать, вставлять и удалять элементы за O(log n) при сбалансированной структуре.

Обход дерева в глубину

function dfs(node, result = []) {
  if (!node) {
    return result;
  }
  result.push(node.value);
  dfs(node.left, result);
  dfs(node.right, result);
  return result;
}

Графы часто представляют списком смежности и обходят либо в глубину (DFS, через рекурсию или стек), либо в ширину (BFS, через очередь). BFS удобен, когда нужно найти кратчайший путь в невзвешенном графе.

Сортировки и поиск

Знание базовых сортировок помогает объяснить выбор алгоритма и его сложность. Быстрая сортировка (quicksort) в среднем работает за O(n log n), но в худшем случае деградирует до O(n^2).

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const [pivot, ...rest] = arr;
  const left = rest.filter((item) => item < pivot);
  const right = rest.filter((item) => item >= pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}

Бинарный поиск — ещё один базовый инструмент, который работает за O(log n), но требует отсортированного массива.

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
      return mid;
    }
    if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

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

• Кандидаты сразу пишут код, не обсудив сложность и граничные случаи
• Использование вложенных циклов там, где хеш-таблица дала бы O(n)
• Игнорирование памяти: решение быстрое по времени, но требует O(n^2) памяти
• Отсутствие проверки пустого массива, null или дублирующихся значений
• Путаница между сложностью в среднем и в худшем случае, особенно для quicksort

Заключение

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