Как делать dry run, трассировку и таблицу состояний?
На этой странице
Dry run - ручной прогон алгоритма на маленьком примере. Он помогает понять решение до кода, найти ошибки после кода и спокойно объяснить алгоритм на собеседовании.
Вопрос
Как делать dry run, трассировку и таблицу состояний?
Что такое dry run
Dry run - это когда ты берешь небольшой input и руками проходишь алгоритм шаг за шагом.
Например:
nums = [2, 1, 5, 1, 3, 2], k = 3Задача: максимальная сумма подмассива длины k.
Плохой dry run
Ну тут окно двигается и ответ 9.Такой прогон не помогает найти ошибку.
Хороший dry run
Нужно выписать состояние:
| Шаг | right | Добавили | Убрали | sum | best |
|---|---|---|---|---|---|
| initial | 0..2 | 2+1+5 | - | 8 | 8 |
| 1 | 3 | 1 | 2 | 7 | 8 |
| 2 | 4 | 3 | 1 | 9 | 9 |
| 3 | 5 | 2 | 5 | 6 | 9 |
Итог: 9.
Пример кода
function maxSumFixed(nums: number[], k: number): number {
let sum = 0
for (let i = 0; i < k; i++) {
sum += nums[i]
}
let best = sum
for (let right = k; right < nums.length; right++) {
sum += nums[right]
sum -= nums[right - k]
best = Math.max(best, sum)
}
return best
}Таблица подтверждает каждую строку:
sum += nums[right]- добавили новый правый элемент;sum -= nums[right - k]- убрали элемент, который вышел из окна;best = Math.max(best, sum)- обновили лучший ответ.
Dry run для Map
Задача Two Sum:
nums = [2, 7, 11, 15], target = 9| i | nums[i] | need | seen до проверки | Действие |
|---|---|---|---|---|
| 0 | 2 | 7 | {} | 7 нет, записали 2 -> 0 |
| 1 | 7 | 2 | {2: 0} | 2 есть, ответ [0, 1] |
Так проще увидеть, почему сначала проверяем need, а потом добавляем текущее число. Если сделать наоборот, можно ошибиться на target = 2 * nums[i].
Dry run для binary search
function binarySearch(nums: number[], target: number): number {
let left = 0
let right = nums.length - 1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (nums[mid] === target) return mid
if (nums[mid] < target) left = mid + 1
else right = mid - 1
}
return -1
}Пример:
nums = [1, 3, 5, 7, 9], target = 7| left | right | mid | nums[mid] | Действие |
|---|---|---|---|---|
| 0 | 4 | 2 | 5 | 5 < 7, left = 3 |
| 3 | 4 | 3 | 7 | нашли |
Для binary search dry run особенно важен, потому что ошибки часто в:
left <= rightvsleft < right;mid + 1;mid - 1;- возвращаемом значении.
Что записывать в таблицу
Для разных паттернов разные состояния:
| Паттерн | Что записывать |
|---|---|
| Two pointers | left, right, текущая сумма/условие |
| Sliding window | границы окна, состояние окна, лучший ответ |
| Stack | содержимое stack, текущий элемент |
| BFS | queue, visited, distance |
| DFS | node, visited/path, recursion depth |
| DP | индекс/state, значение dp, transition |
| Heap | heap после push/pop |
| Backtracking | choice, path, result, undo |
Когда делать dry run
До кода:
- чтобы понять задачу;
- чтобы проверить идею;
- чтобы объяснить интервьюеру подход.
После кода:
- чтобы найти off-by-one;
- чтобы проверить edge cases;
- чтобы убедиться, что state обновляется в правильном порядке.
Что важно помнить: частые ошибки
- Прогонять только happy path.
- Не записывать состояние явно.
- Выбирать слишком большой пример.
- Не проверять пустой input.
- Не проверять минимальный размер.
- Не прогонять случай, где ответ не найден.
- Не сверять dry run со строками кода.
Что отвечать на собеседовании?
Я делаю dry run на маленьком примере и выписываю состояние алгоритма: индексы, окно, Map, Set, queue, stack или dp. Это помогает проверить идею до кода и найти ошибки после кода. Для сложных паттернов я строю таблицу, где каждая строка соответствует одному шагу цикла или рекурсии.
Мини-шпаргалка
- Dry run = ручной прогон.
- Маленький пример лучше большого.
- Пиши состояние явно.
- Для
Mapзаписывай состояние до и после шага. - Для binary search записывай
left/right/mid. - Для DP записывай
stateиtransition. - Dry run ловит off-by-one лучше, чем угадывание.
Документация
Python Tutor (визуализация выполнения, поддерживает JavaScript).