Алгоритмы для интервью

На junior достаточно нескольких базовых навыков: оценить сложность, выбрать структуру данных и написать решение в 30 строк. Практикуем именно их.

Big O: язык оценки

Big O — как растёт время (или память) с ростом данных n:

• O(1) — доступ к элементу массива, запись в объект по ключу;
• O(n) — пройти по массиву один раз;
• O(n log n) — хорошая сортировка (V8's sort);
• O(n²) — вложенные циклы. Обычно сигнал «ищи лучший путь».

Хэш-таблицы решают половину задач

// Поиск пары чисел с суммой target за 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 [];
}

Типичный разбор задачи

1. спросите про ограничения: размер входа, только числа?
2. покажите наивное решение и его сложность;
3. улучшьте до оптимального, рассуждая вслух;
4. проверьте крайние случаи: пустой массив, один элемент, дубли;
5. назовите сложность решения по времени и памяти.