re:re:actable
Урок 014 минуты чтения

Как новичку читать алгоритмическую задачу?

На этой странице
Кратко

Новичку важно не начинать с кода. Сначала нужно понять, что дано, что нужно вернуть, какие есть ограничения и какие примеры подтверждают понимание задачи.

Вопрос

Как новичку правильно читать алгоритмическую задачу?

Шаг 1. Найди input

Input - это данные, которые функция получает на вход.

Пример:

Дан массив чисел nums и число target.
Нужно вернуть индексы двух чисел, сумма которых равна target.

Input:

nums: number[]
target: number

Сразу спроси себя:

  • массив может быть пустым?
  • числа могут быть отрицательными?
  • есть ли дубликаты?
  • массив отсортирован?
  • можно ли менять массив?

Шаг 2. Найди output

Output - это то, что нужно вернуть.

В задаче Two Sum:

вернуть индексы двух чисел

Значит результат:

number[]

Важно не перепутать:

  • вернуть индексы или значения;
  • вернуть первый ответ или все ответы;
  • вернуть true/false или сам объект;
  • вернуть длину или подстроку;
  • вернуть -1, null, пустой массив или бросить ошибку, если ответа нет.

Шаг 3. Найди constraints

Constraints - ограничения. Они подсказывают, какое решение пройдет.

1 <= nums.length <= 100000

Если n = 100000, то O(n^2) почти точно слишком медленно.

Примерная интуиция:

ОграничениеЧто обычно допустимо
n <= 20перебор 2^n, backtracking
n <= 100иногда O(n^3)
n <= 1000часто O(n^2)
n <= 100000обычно O(n log n) или O(n)
n <= 1000000чаще O(n)

Это не железный закон, но хорошая подсказка.

Шаг 4. Разбери пример руками

Для Two Sum:

nums = [2, 7, 11, 15], target = 9
answer = [0, 1]

Почему:

nums[0] + nums[1] = 2 + 7 = 9

Если пример непонятен, код писать рано.

Шаг 5. Сформулируй brute force

Brute force - самое прямое решение.

function twoSumBrute(nums: number[], target: number): number[] {
  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 []
}

Даже если brute force медленный, он полезен:

  • помогает понять задачу;
  • дает baseline;
  • проще проверить edge cases;
  • показывает, где повторная работа.

Шаг 6. Найди повторную работу

В Two Sum brute force много раз спрашивает:

есть ли число target - nums[i]?

Это можно ускорить через Map.

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>()
 
  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 []
}

Шаг 7. Проверь edge cases

Для Two Sum:

  • nums = [];
  • nums = [1];
  • есть отрицательные числа;
  • есть дубликаты;
  • ответа нет;
  • ответ использует два одинаковых значения на разных индексах.

Шаблон для новичка

1. Что дано?
2. Что вернуть?
3. Какие ограничения?
4. Есть ли сортировка?
5. Есть ли дубликаты?
6. Можно ли менять input?
7. Как работает пример?
8. Какой brute force?
9. Где повторная работа?
10. Какая структура данных ускорит операцию?

Что важно помнить: частые ошибки

  • Сразу писать код.
  • Не понять, что нужно вернуть.
  • Пропустить constraints.
  • Не спросить про пустой input.
  • Перепутать индексы и значения.
  • Не разобрать пример руками.
  • Заучивать паттерны без понимания условия.

Что отвечать на собеседовании?

Я начинаю с уточнения input/output и ограничений, затем прогоняю пример руками. После этого называю brute force, оцениваю его сложность и ищу повторную работу. Если вижу, что часто проверяю наличие значения, беру Map или Set; если работаю с contiguous subarray, думаю про sliding window или prefix sums; если есть зависимости, думаю про graph.

Мини-шпаргалка

  • Input - что дали.
  • Output - что вернуть.
  • Constraints - какое решение пройдет.
  • Example - проверка понимания.
  • Brute force - стартовая точка.
  • Повторная работа - место для оптимизации.
  • Edge cases - проверка надежности.

Документация

Tech Interview Handbook: Coding interview.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам