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

Как делать 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ДобавилиУбралиsumbest
initial0..22+1+5-88
131278
243199
352569

Итог: 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
inums[i]needseen до проверкиДействие
027{}7 нет, записали 2 -> 0
172{2: 0}2 есть, ответ [0, 1]

Так проще увидеть, почему сначала проверяем need, а потом добавляем текущее число. Если сделать наоборот, можно ошибиться на target = 2 * nums[i].

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
leftrightmidnums[mid]Действие
04255 < 7, left = 3
3437нашли

Для binary search dry run особенно важен, потому что ошибки часто в:

  • left <= right vs left < right;
  • mid + 1;
  • mid - 1;
  • возвращаемом значении.

Что записывать в таблицу

Для разных паттернов разные состояния:

ПаттернЧто записывать
Two pointersleft, right, текущая сумма/условие
Sliding windowграницы окна, состояние окна, лучший ответ
Stackсодержимое stack, текущий элемент
BFSqueue, visited, distance
DFSnode, visited/path, recursion depth
DPиндекс/state, значение dp, transition
Heapheap после push/pop
Backtrackingchoice, 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).

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

Поиск

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