Как новичку читать алгоритмическую задачу?
На этой странице
Новичку важно не начинать с кода. Сначала нужно понять, что дано, что нужно вернуть, какие есть ограничения и какие примеры подтверждают понимание задачи.
Вопрос
Как новичку правильно читать алгоритмическую задачу?
Шаг 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 - проверка надежности.