Общие алгоритмические задачи

Кратко о теме

Эта подтема — сборная солянка того, что реально спрашивают на алгоритмической секции Go-собеседования. Здесь почти нет «олимпиадного» уровня: типовой формат — одна-две задачи уровня LeetCode Easy/Medium на 20–40 минут, плюс требование вслух проговорить сложность по времени и памяти. Интервьюер оценивает не столько факт «зашло/не зашло», сколько процесс: уточнил ли кандидат условие и границы входа, назвал ли сначала наивное решение и его сложность, увидел ли структуру данных, которая убирает лишний проход, аккуратно ли обработал пустой вход, один элемент, переполнение и Unicode.

Практически все задачи из этого блока сводятся к четырём приёмам. Первый — хеш-таблица вместо вложенного цикла: группировка анаграмм, поиск пар, дедупликация — везде O(n²) брутфорс схлопывается в O(n) за счёт map. Второй — два указателя / скользящее окно: палиндром, пересечение отсортированных интервалов, слияние. Третий — жадность с доказательством и сортировкой: задача про купоны, размен купюр в банкомате, покрытие интервалов; жадность требует аргумента обмена («exchange argument»), иначе это угадывание. Четвёртый — локальный признак вместо глобального обхода: подсчёт кораблей на поле не через DFS-закрашивание, а через проверку «слева и сверху не единица» — это даёт O(1) дополнительной памяти и не портит вход.

Отдельный пласт вопросов в этом блоке — не задачи, а теория, которую почему-то относят к «алгоритмам»: устройство сборщика мусора Go (трёхцветная маркировка, mark & sweep, write barrier) и семейства алгоритмов хеширования. Их спрашивают ровно потому, что GC в Go — это конкурентный трёхцветный mark-and-sweep, то есть настоящий классический алгоритм на графе, а хеширование лежит под map, под кешами и под consistent hashing в распределённых системах.

Модель трёхцветной маркировки, которую стоит держать в голове:

Ключевой инвариант: чёрный объект никогда не должен указывать на белый без того, чтобы белый был известен серым. Write barrier существует именно для поддержания этого инварианта во время конкурентной маркировки.

Вопросы и ответы

Task: F+1=?

Обрывок исходника, вопрос не восстанавливается. Скорее всего это фрагмент условия задачи с доски (переменная F и инкремент), из которого не сохранился контекст. На реальном собесе в такой ситуации правильное поведение — переспросить, а не додумывать: «уточните, что такое F и в каких границах она лежит».

Задачи уровня leetcode easy.

Коротко. На большинстве Go-вакансий алгоритмическая секция ограничена LeetCode Easy: строки, массивы, хеш-таблицы, два указателя, простая рекурсия. Ожидается рабочее решение за 15–25 минут плюс корректно названная сложность.

Глубже. Полезно закрыть узкий и предсказуемый список: Two Sum, Valid Palindrome, Valid Parentheses, Merge Two Sorted Lists, Best Time to Buy and Sell Stock, Contains Duplicate, Group Anagrams (формально Medium, но спрашивают постоянно), Move Zeroes, Reverse Linked List, Binary Search, Fizz Buzz. В Go есть специфика, на которой валятся даже те, кто решал это на Python: строка — это байты, а не символы, поэтому s[i] даёт byte, а for i, r := range s — rune со скачущим индексом; срез, переданный в функцию, разделяет массив с вызывающим, поэтому «in-place» действительно меняет данные снаружи; append может как переиспользовать, так и переаллоцировать буфер. Проговаривать O(n) времени и O(1)/O(n) памяти нужно самому, не дожидаясь вопроса.

2й тех. этап - две задачи на алгоритмы;

Коротко. Типичный формат: второй технический этап на 60–90 минут, из них две задачи — обычно одна Easy на разогрев и одна Medium, где проверяют, увидишь ли ты структуру данных, убирающую квадрат.

Глубже. Тайм-менеджмент здесь важнее эрудиции: на первую задачу стоит потратить не больше трети времени. Рабочая схема на каждую задачу — уточнить вход (границы, дубликаты, отсортированность, пустота, Unicode), вслух назвать брутфорс и его сложность, предложить улучшение и только потом писать код, затем самому прогнать 2–3 теста, включая краевые. Если решение не рождается за 5–7 минут, честно скажите «пишу пока наивный вариант, дальше буду оптимизировать» — работающий брутфорс почти всегда лучше пустого экрана. Компилируемость кода проверяют: в Go это значит настоящие импорты (sort, strings, slices), реальные сигнатуры и отсутствие неиспользуемых переменных.

Как это можно исправить?

Обрывок исходника, вопрос не восстанавливается — он всегда задаётся вторым шагом после «вот твой код / вот проблема». Общий каркас ответа, если такой вопрос прилетает: сначала назвать, что именно сломано (сложность, гонка, утечка, некорректность на краевом входе), затем предложить конкретное изменение и назвать его цену. В контексте этого блока чаще всего «исправить» означает одно из трёх: заменить вложенный цикл на map и получить O(n) вместо O(n²); заранее отсортировать и перейти на два указателя; либо избавиться от копирования данных, предварительно выделив ёмкость через make([]T, 0, n).

Как работает трехцветный алгоритм в сборщике мусора Go? В чем суть пометки и очистки с его помощью?

Коротко. Все объекты кучи логически делятся на три множества: белые (ещё не достигнутые), серые (достигнутые, но чьи поля ещё не просканированы) и чёрные (достигнутые и полностью просканированные). Сборщик красит корни в серый, затем по очереди берёт серый объект, красит все его белые ссылки в серый и сам становится чёрным; когда серых не осталось, всё оставшееся белое — мусор, и его память переиспользуется на фазе sweep.

Глубже. Сложность обхода — O(размер живого графа), поэтому цена маркировки зависит от количества живых объектов, а не от размера кучи целиком. В Go маркировка идёт конкурентно с работающими горутинами, и это создаёт проблему: мутатор может записать ссылку на белый объект в уже почёрневший объект и одновременно удалить последнюю ссылку на этот белый из серого — тогда живой объект будет ошибочно собран. Защита — write barrier. С Go 1.8 используется гибридный барьер Yuasa + Dijkstra: при записи указателя в серый красится и старое значение поля (deletion barrier, Yuasa), и новое (insertion barrier, Dijkstra). Это позволило убрать повторное сканирование стеков в STW и снизить паузы до сотен микросекунд. Цвет физически хранится не в объекте, а в битах разметки спана плюс очередь работ (gcw — work buffers): «серый» = «лежит в очереди сканирования». Сам sweep ленивый: спаны подметаются по мере запроса памяти под аллокацию, а не одним махом. Go-сборщик не перемещает объекты (non-moving), поэтому фрагментация решается size-классами аллокатора, а не компактизацией, и указатели остаются валидными для cgo.

Напиши функцию которая проверят слово на палиндром.

Коротко. Два указателя с концов навстречу; для корректной работы с русским текстом и любым не-ASCII строку надо разложить в []rune, а не сравнивать байты.

Глубже. Байтовая версия s[i] == s[len(s)-1-i] для строки «шалаш» даст неверный результат сравнения посимвольно (каждая буква занимает 2 байта) — формально для целой строки байтовый разворот палиндрома из многобайтовых символов совпадёт, но как только добавляется приведение регистра или пропуск не-букв, байтовый подход ломается. Правильный вариант:

package main

import (
  "unicode"
)

// IsPalindrome проверяет слово на палиндром, игнорируя регистр,
// пробелы и знаки препинания.
func IsPalindrome(s string) bool {
  runes := make([]rune, 0, len(s))
  for _, r := range s {
    if unicode.IsLetter(r) || unicode.IsDigit(r) {
      runes = append(runes, unicode.ToLower(r))
    }
  }
  for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
    if runes[i] != runes[j] {
      return false
    }
  }
  return true
}

Сложность — O(n) по времени и O(n) по памяти из-за среза рун. Если попросят O(1) памяти, можно идти по строке двумя указателями с utf8.DecodeRuneInString и utf8.DecodeLastRuneInString. Отдельно стоит упомянуть, что «настоящая» Unicode-корректность требует нормализации (golang.org/x/text/unicode/norm), потому что «й» может быть как одной руной, так и «и» + комбинирующая бреве; на собесе достаточно назвать этот нюанс, реализовывать его не просят.

Какие есть алгоритмы хэширования?

Коротко. Их делят на четыре класса по назначению: криптографические (SHA-2, SHA-3, BLAKE2/BLAKE3), некриптографические быстрые для хеш-таблиц (FNV-1a, MurmurHash3, xxHash, wyhash), функции для паролей с намеренным замедлением (bcrypt, scrypt, Argon2id, PBKDF2) и контрольные суммы для обнаружения помех (CRC32, Adler-32).

Глубже. Путать классы — самая частая ошибка: SHA-256 для хранения паролей не годится, потому что она быстрая, и перебор на GPU идёт миллиардами хешей в секунду; для паролей нужен Argon2id или bcrypt с солью и параметром стоимости. MD5 и SHA-1 сломаны по коллизиям (реальные атаки: chosen-prefix для обоих) и допустимы только как некриптографический чексум легаси-данных. Для проверки подлинности сообщения нужен не «хеш от данных+ключа», а HMAC (crypto/hmac), иначе на Merkle–Damgård-функциях работает length-extension атака; SHA-3 и BLAKE2 к ней невосприимчивы по конструкции. В стандартной библиотеке Go: crypto/sha256, crypto/sha512, golang.org/x/crypto/sha3, hash/fnv, hash/crc32, hash/maphash (сидированный хеш для собственных хеш-таблиц), golang.org/x/crypto/bcrypt и argon2. Внутри рантайма хеш для map сидируется случайным значением при старте процесса — это защита от hash-flooding DoS, поэтому порядок обхода map не определён, а на amd64 с AES-NI хеш считается на аппаратных инструкциях. В Go 1.24 реализация map переехала на Swiss Tables, что изменило раскладку бакетов и ускорило поиск, но контракт по недетерминированному порядку обхода остался прежним. Для распределённых систем отдельно называют consistent hashing (кольцо с виртуальными нодами) и rendezvous hashing (HRW) — они минимизируют переезд ключей при изменении числа шардов.

Какой алгоритм у сборки мусора? Есть ли там этапы сборки?

Коротко. В Go это конкурентный трёхцветный mark-and-sweep: неперемещающий (non-moving), непоколенческий (non-generational), с двумя короткими stop-the-world паузами. Этапы: sweep termination → concurrent mark (с write barrier) → mark termination → concurrent sweep.

Глубже. Разберём по фазам. Sweep termination — короткий STW, добивается подметание предыдущего цикла, включается write barrier. Concurrent mark — основная фаза: помощники маркировки работают параллельно с приложением, GC-воркеры целятся примерно на 25% CPU; если горутина аллоцирует быстрее, чем идёт маркировка, она получает mark assist и сама платит маркировкой пропорционально аллокации. Mark termination — второй STW, обычно десятки-сотни микросекунд: завершается маркировка, выключается write barrier. Concurrent sweep — освобождение белых спанов, ленивое, по мере аллокаций.

Момент запуска определяет pacer: цель — начать цикл так, чтобы к его концу куча выросла на GOGC процентов от размера живой кучи после прошлой сборки (по умолчанию GOGC=100, то есть удвоение). С Go 1.19 добавлен GOMEMLIMIT — мягкий лимит на общий объём памяти рантайма; при приближении к нему GC начинает работать чаще, вплоть до непрерывной работы, но OOM это не гарантирует предотвратить, лимит именно мягкий. Начиная с Go 1.24 объекты с финализаторами и новый runtime.AddCleanup обрабатываются аккуратнее, чем старый SetFinalizer, который умел продлевать жизнь объекта на лишний цикл. Что стоит сказать явно: Go не делает компактизацию, поэтому «дефрагментация кучи» — не про Go; и GC не возвращает память ОС мгновенно — освобождённые страницы отдаются через madvise(MADV_FREE/MADV_DONTNEED) фоновым scavenger’ом.

Написать метод (класс и импорты не нужны) на вход которого приходит список слов. На выходе надо вернуть список слов, где каждый подписок содержит слова анаграммы (одинаковые слова слева направо и справа налево).

Коротко. Группировка анаграмм: для каждого слова считаем канонический ключ (отсортированные буквы или счётчик букв) и складываем слова в map[string][]string; на выходе — значения этой мапы. Время O(n·k log k), где k — длина слова, память O(n·k).

Глубже. Обратите внимание: пояснение в скобках («одинаковые слова слева направо и справа налево») описывает палиндром, а не анаграмму — это несоответствие в условии стоит проговорить на собесе и уточнить, что нужно. Анаграммы — это слова из одного мультимножества букв («кот» и «ток»). Каноничная реализация:

package main

import "sort"

func GroupAnagrams(words []string) [][]string {
  groups := make(map[string][]string, len(words))
  for _, w := range words {
    runes := []rune(w)
    sort.Slice(runes, func(i, j int) bool { return runes[i] < runes[j] })
    key := string(runes)
    groups[key] = append(groups[key], w)
  }
  res := make([][]string, 0, len(groups))
  for _, g := range groups {
    res = append(res, g)
  }
  return res
}

Если алфавит ограничен (например, только строчная латиница), ключ можно строить за O(k) как массив из 26 счётчиков, сериализованный в строку, — получится O(n·k) суммарно. Порядок групп в результате недетерминирован, потому что обход map в Go случайный: если тесты сравнивают результат буквально, надо отсортировать выход. Для Unicode сортировка рун корректнее сортировки байтов, а при реальной работе с текстом ещё и регистр с нормализацией нужно привести заранее.

Решить задачу leetcode easy;

Коротко. См. выше про «Задачи уровня leetcode easy» — тот же формат. Отличие лишь в том, что здесь речь про одну конкретную задачу в моменте: главное — не начинать писать код до того, как вслух сформулирован алгоритм и его сложность.

Глубже. Практический протокол на 20 минут: 2 минуты — уточняющие вопросы и примеры входа, включая пустой и вырожденный; 3 минуты — озвучить брутфорс, его O(…), и оптимизацию; 10 минут — код; 5 минут — прогон на примерах руками и обсуждение краевых случаев. Если ошиблись — исправляйте молча-вслух («вижу, здесь выйду за границу среза, добавлю проверку»), это плюс, а не минус.

Брутфорс - плохое решение;

Коротко. Брутфорс — правильная стартовая точка, но плохой финальный ответ: его надо назвать, оценить сложность и тут же предложить, за счёт чего он схлопывается — предвычисленной хеш-таблицы, сортировки, двух указателей, префиксных сумм или динамики.

Глубже. Полезно держать в голове таблицу «что за что меняем»: вложенный цикл поиска пары → map с уже увиденными значениями (O(n²) → O(n) время, O(n) память); повторный подсчёт суммы на подотрезке → префиксные суммы (O(n·k) → O(n)); поиск в неотсортированных данных много раз → однократная сортировка + бинарный поиск (O(n·q) → O(n log n + q log n)); перебор всех подмножеств → жадность с доказательством обмена или DP по состояниям. Обратная сторона: если n мало и ограничено (скажем, n ≤ 100), брутфорс может быть правильным ответом — и умение это сказать («здесь O(n²) укладывается, усложнять незачем») ценится не меньше, чем оптимизация. Ещё одна частая подмена: «оптимизировал» константу, но асимптотика осталась квадратичной — интервьюер спрашивает именно про порядок роста.

Пройтись по массиву, уменьшая цены товаров больше K на максимальное кол-во купонов. Далее отсортировать по убыванию массив и вычитать также максимум K купонов из каждой цены. Оставшийся массив сложить и вернуть в result;

Коротко. Это описание жадного решения задачи «минимизировать итоговую сумму, имея ограниченное число купонов»: сортируем цены по убыванию и тратим купоны на самые дорогие позиции, пока купоны не кончатся или скидка не перестанет давать выигрыш. Сложность O(n log n) на сортировку плюс O(n) на проход.

Глубже. Жадность здесь требует доказательства обменом: если купон фиксированно снижает цену на величину d (с обрезкой снизу нулём), то выигрыш от купона на позиции с ценой p равен min(p, d), и он монотонно не убывает по p — значит, отдавать купоны дорогим товарам не хуже любой другой раскладки. Из этого сразу следуют краевые случаи: купон бессмысленен на товаре дешевле порога (выигрыш меньше d), поэтому цены ниже d обрабатывать не нужно; цена не должна уходить в минус; купонов может быть больше, чем товаров, и наоборот. Если по условию на один товар можно класть несколько купонов и скидка мультипликативная (например, каждый купон делит цену пополам), жадность по исходной сортировке ломается — нужна max-куча: каждый раз берём текущий максимум, применяем купон, кладём обратно, итого O(m log n) для m купонов. Именно этот переход «сортировка → куча» интервьюер обычно и хочет услышать. Формулировка в условии («уменьшая цены товаров больше K на максимальное кол-во купонов») смешивает два прохода — на собесе стоит сначала переформулировать задачу своими словами и зафиксировать модель скидки, иначе решаете не ту задачу.

Закрашивание - плохое решение. То есть проверять по горизонтали и по вертикали последовательности единиц, затем считать непрерывные последовательности. Проверять клетку слева и сверху от каждой 1, если там не 1, значит мы увидели 1 корабль.

Коротко. Классическая задача подсчёта кораблей на поле (LeetCode 419). Вместо DFS/BFS с закрашиванием достаточно за один проход считать «носы» кораблей: клетка '1', у которой сверху и слева не '1', — это начало нового корабля. O(m·n) времени, O(1) дополнительной памяти, вход не портится.

Глубже. Приём работает при стандартном ограничении задачи: корабли — прямые линии шириной в одну клетку (горизонтальные или вертикальные) и разделены хотя бы одной пустой клеткой, то есть не соприкасаются. Без этого условия соседние корабли слипнутся, и локальный признак сломается — тогда нужен полноценный обход компонент связности (DFS/BFS или DSU). Это ровно тот нюанс, который надо озвучить вслух.

package main

func CountBattleships(board [][]byte) int {
  count := 0
  for i := range board {
    for j := range board[i] {
      if board[i][j] != '1' {
        continue
      }
      if i > 0 && board[i-1][j] == '1' {
        continue // продолжение вертикального корабля
      }
      if j > 0 && board[i][j-1] == '1' {
        continue // продолжение горизонтального корабля
      }
      count++
    }
  }
  return count
}

Почему «закрашивание — плохое решение»: рекурсивный DFS мутирует входную матрицу (или требует O(m·n) памяти под visited), а на большом поле из одних единиц уходит в глубину O(m·n) по стеку. Итеративный BFS решает вопрос со стеком, но память под очередь и visited остаётся. Локальный признак даёт тот же ответ в одну строчку условий.

Есть интервалы времен двух пользователей которые играют в онлайн игру. Задача - найти пересечения по времени когда эти пользователи могли бы поиграть вместе:

Коротко. Если оба списка интервалов отсортированы и непересекающиеся внутри себя — два указателя: пересечение текущей пары равно [max(startA, startB), min(endA, endB)], оно валидно если левая граница не больше правой; дальше сдвигаем указатель у того интервала, который заканчивается раньше. O(n + m) времени, O(1) дополнительной памяти.

Глубже. Если исходные списки не отсортированы — сначала сортировка по началу, O(n log n + m log m). Уточняющие вопросы, которые надо задать до кода: интервалы полуоткрытые [start, end) или закрытые (от этого зависит, считается ли касание в точке пересечением — обычно нет, и условие становится строгим lo < hi); могут ли интервалы внутри одного списка пересекаться (тогда сначала их надо смёржить); нужны ли пересечения короче какого-то минимума (в игровом контексте «поиграть вместе 1 секунду» смысла не имеет). Обобщение на k пользователей: либо последовательно пересекать результат с очередным списком, либо sweep line — все границы в один массив событий (+1 на открытии, −1 на закрытии), сортировка и поиск отрезков, где счётчик равен k.

package main

type Interval struct{ Start, End int }

// Intersect возвращает пересечения двух отсортированных списков
// непересекающихся полуоткрытых интервалов [Start, End).
func Intersect(a, b []Interval) []Interval {
  res := make([]Interval, 0, len(a)+len(b))
  i, j := 0, 0
  for i < len(a) && j < len(b) {
    lo := max(a[i].Start, b[j].Start)
    hi := min(a[i].End, b[j].End)
    if lo < hi {
      res = append(res, Interval{lo, hi})
    }
    if a[i].End < b[j].End {
      i++
    } else {
      j++
    }
  }
  return res
}

Встроенные min/max для упорядоченных типов доступны без импортов начиная с Go 1.21.

Изначально банкомат пуст;

Коротко. Это первая строка условия задачи «спроектировать банкомат»: стартовое состояние — нулевые счётчики по всем номиналам, то есть любая попытка снятия до первого внесения обязана быть отклонена.

Глубже. Из «изначально пуст» вытекает структура состояния: не список купюр, а фиксированный массив счётчиков по пяти номиналам, например type ATM struct { counts [5]int64 } с константой var denoms = [5]int64{500, 200, 100, 50, 20} (номиналы удобно держать по убыванию, а тип брать int64: количество купюр доходит до 10⁹, и int32 не хватит на произведение). Инициализация нулями в Go бесплатна: zero value структуры уже валиден, конструктор не обязателен. На собесе стоит сразу спросить, нужна ли потокобезопасность: если банкомат дёргают конкурентно, всё состояние прячется за sync.Mutex, потому что операция «проверить и списать» неатомарна по своей природе, и atomic по отдельным счётчикам её не спасёт.

Можно вносить купюры любого номинала;

Коротко. Операция Deposit принимает набор купюр по номиналам и просто увеличивает соответствующие счётчики — O(1) при пяти фиксированных номиналах, без всякой сортировки.

Глубже. Здесь два подводных камня. Первый — «любого номинала» надо уточнить: любого из списка допустимых (20/50/100/200/500) или вообще произвольного? Если строго из списка, депозит с неизвестным номиналом должен отклоняться, а не молча игнорироваться. Второй — переполнение: счётчик до 10⁹ купюр по 500 даёт 5·10¹¹, что не влезает в int32, но спокойно влезает в int64; на 64-битных платформах int в Go тоже 64-битный, но полагаться на это в коде, который может собираться под 32-битную архитектуру, не стоит — лучше явный int64. Общая сумма в банкомате при максимальном заполнении — порядка 8.7·10¹¹, тоже int64.

При снятии банкомат выдает сумму, используя купюры большего номинала;

Коротко. Требование «сначала крупные» — это жадность сверху вниз: идём от 500 к 20 и на каждом номинале берём k = min(доступно, остаток/номинал). Но чистая жадность может ошибочно отказать в выдаче, поэтому нужен откат.

Глубже. Контрпример на этих же номиналах: сумма 60 при бесконечном запасе купюр. Жадность возьмёт 50, останется 10 — и ни одна купюра не подходит, выдаётся отказ. При этом решение существует: 20+20+20. То есть «предпочитать крупные» нельзя понимать как «брать максимум крупных без оглядки»; корректная формулировка — «среди всех выполнимых раскладов выбрать лексикографически максимальный по количеству крупных купюр». Реализуется это DFS по пяти номиналам сверху вниз с откатом: на уровне номинала пробуем максимальное количество, затем на единицу меньше и так далее. Чтобы перебор не взорвался, окно отката на каждом уровне достаточно сделать небольшим (единицы вариантов): интуиция в том, что если бы мы взяли сильно меньше крупных купюр, разницу пришлось бы добирать мелкими, а любую группу мелких, сумма которой кратна крупному номиналу, можно свернуть обратно в крупную — то есть «сильно недобирать» крупные никогда не требуется. Глубина 5, ветвление константное, значит вся выдача — O(1) на запрос независимо от 10⁹ купюр: считаем через целочисленное деление, а не циклом по купюрам.

package main

var denoms = [5]int64{500, 200, 100, 50, 20} // по убыванию

type ATM struct {
  counts [5]int64 // количество купюр, порядок совпадает с denoms
}

// plan пытается набрать sum, предпочитая крупные купюры.
// Возвращает раскладку и признак успеха; состояние не меняет.
func (a *ATM) plan(sum int64) ([5]int64, bool) {
  var take [5]int64
  var dfs func(i int, rem int64) bool
  dfs = func(i int, rem int64) bool {
    if rem == 0 {
      return true
    }
    if i == len(denoms) {
      return false
    }
    maxK := rem / denoms[i]
    if maxK > a.counts[i] {
      maxK = a.counts[i]
    }
    const window = 32 // окно отката
    lo := maxK - window
    if lo < 0 {
      lo = 0
    }
    for k := maxK; k >= lo; k-- {
      take[i] = k
      if dfs(i+1, rem-k*denoms[i]) {
        return true
      }
    }
    take[i] = 0
    return false
  }
  ok := dfs(0, sum)
  return take, ok
}

Если запрошенную сумму нельзя выдать, операция отклоняется, и состояние банкомата не меняется.

Коротко. Это требование транзакционности: сначала полностью рассчитываем раскладку на копии состояния, и только при успехе применяем её к реальным счётчикам. Никаких частичных списаний по ходу перебора.

Глубже. Отсюда следует, почему в коде выше plan возвращает раскладку, а не мутирует a.counts: списание делается отдельным шагом commit после ok == true. Альтернатива — мутировать и откатывать при неудаче — работает, но при рекурсивном откате легко потерять инвариант, особенно если позже добавится конкурентность. Три случая отказа, которые надо перечислить вслух: сумма превышает общий остаток в банкомате; сумма в принципе непредставима в данных номиналах (на этих номиналах — всё, что не кратно 10, а также 10 и 30); сумма представима, но конкретного набора купюр не хватает. Тестировать имеет смысл именно третий случай — он ловит баги в откате. Плюс мелочи: sum <= 0 — ошибка аргумента, а не отказ выдачи; при конкурентном доступе весь блок «plan + commit» должен быть под одним мьютексом, иначе два клиента одновременно «спланируют» одни и те же купюры.

Номиналы: [20, 50, 100, 200, 500];

Коротко. Пять фиксированных номиналов означают, что размерность задачи константная: любые проходы по номиналам — это O(1), а не O(n), и всё решение сводится к пяти целочисленным делениям с небольшим откатом.

Глубже. Стоит заметить структуру набора: все номиналы кратны 10, поэтому задачу можно нормировать делением на 10 → [2, 5, 10, 20, 50], и сразу видно, что суммы, не кратные 10, невыдаваемы. Дальше 100, 200 и 500 кратны 20 и 50 не полностью (500 = 25·20 = 10·50, 200 = 10·20 = 4·50, 100 = 5·20 = 2·50 — все кратны), а мелкая пара {20, 50} порождает множество достижимых сумм: 20, 40, и все кратные 10 начиная с 50 — недостижимы только 10 и 30. Это даёт готовый быстрый предикат «представима ли сумма вообще». Также важно: этот набор номиналов не канонический для жадного размена (пример с 60 выше), в отличие от, скажем, [1, 5, 10, 25], — то есть простое «бери самую крупную» здесь доказуемо неверно, и именно это интервьюер обычно ждёт услышать.

Количество купьер каждого номинала: от 0 до 10⁹;

Коротко. До 10⁹ купюр на номинал — это прямой запрет на любой алгоритм, который перебирает купюры по одной или строит DP по сумме: считать нужно целочисленным делением, а состояние хранить счётчиками.

Глубже. Наивные подходы, которые здесь падают: DP «монетный размен» с массивом на 10⁹ ячеек — не влезет ни по памяти, ни по времени; цикл for count > 0 { ... } на списании — до миллиарда итераций; хранение среза с миллиардом элементов-купюр — терабайты. Правильно: k := min(available, remaining/denom), списание counts[i] -= k. По типам — int64 обязателен: 10⁹ купюр по 500 = 5·10¹¹ уже за пределами int32, а сумма произведений по всем номиналам достигает ~8.7·10¹¹. Также «от 0» означает, что пустой номинал — легальное состояние, и код не должен делить или предполагать наличие хотя бы одной купюры.

Сумма снятия: от 1 до 10⁹;

Коротко. Верхняя граница 10⁹ подтверждает: алгоритм должен быть O(1) по сумме, то есть арифметика вместо перебора; а нижняя граница 1 гарантирует, что тесты будут проверять заведомо невыдаваемые суммы (1, 10, 30).

Глубже. Полный список ранних отказов, который стоит написать до основного алгоритма: sum % 10 != 0 → отказ; sum == 10 || sum == 30 → отказ (непредставимо в {20, 50}-подрешётке); sum > totalCash → отказ. Эти три проверки закрывают большинство негативных тестов за O(1) и не дают перебору уходить в бессмысленную работу. Замечание про типы: sum до 10⁹ влезает в int32 впритык, но промежуточные произведения k * denom — нет, поэтому по всему коду держим int64. И про производительность: при O(1) на операцию банкомат выдерживает любое реалистичное число запросов, узким местом станет мьютекс, а не алгоритм.

Опишите алгоритм действий при инциденте в продакшене. Вы приходите на работу и узнаете, что система упала. С чего начнете, как будете действовать? Расскажите обобщенно.

Коротко. Порядок такой: подтвердить и оценить масштаб по метрикам, объявить инцидент и назначить роли, сначала митигировать (откат релиза, фича-флаг, переключение трафика), потом уже искать корневую причину, восстановить и проверить по метрикам, затем безблеймовый постмортем с конкретными action items. Главный принцип — «стоп кровотечению раньше, чем диагноз».

Глубже. Это поведенческий вопрос, здесь оценивают не факты, а структуру мышления, поэтому стройте ответ по шагам и подкрепляйте одним примером из своего опыта.

Что интервьюер хочет услышать. Первое — не паниковать и не лезть чинить руками: сначала посмотреть дашборды (error rate, latency p99, saturation — то есть RED/USE-метрики), понять, что именно «упало» и для скольких пользователей. Второе — коммуникация: сообщить в канал инцидентов, назначить incident commander (если это вы — явно это сказать), отделить того, кто чинит, от того, кто пишет статусы; поставить в известность саппорт/бизнес. Третье — митигация раньше диагностики: если инцидент совпал по времени с деплоем, откатываемся, не разбираясь; если это фича-флаг — выключаем; если один инстанс/AZ — уводим трафик; если внешняя зависимость — включаем деградацию/circuit breaker. Четвёртое — диагностика по фактам: логи и трейсы вокруг timestamp начала, дифф последнего релиза, изменения конфигов и инфраструктуры, графики зависимостей (БД, кеш, брокер), в Go-сервисе — pprof (goroutine-дамп на предмет дедлоков и утечки горутин, heap на предмет OOM). Пятое — подтверждённое восстановление: не «вроде работает», а метрики вернулись в норму и держатся N минут. Шестое — постмортем без поиска виноватых: таймлайн, корневая причина через «5 почему», что сработало, что нет, и конкретные задачи с исполнителями и сроками — включая «почему мы узнали не от мониторинга, а от пользователей».

Типичные ошибки в ответе: начать с «я бы посмотрел логи» (это середина процесса, а не начало); забыть про коммуникацию с бизнесом; сразу искать root cause, оставляя прод лежать; обещать «найду виноватого»; не упомянуть проверку, что фикс действительно помог; не сказать про предотвращение повторов (алерты, тесты, раннеры, канареечный деплой). Хорошим тоном будет упомянуть градацию severity и то, что для SEV-1 порядок действий отличается от мелкой деградации.

Как работает алгоритм Mark and Sweep?

Коротко. Две фазы: mark — обход графа объектов от корней (стеки горутин, глобальные переменные, регистры) с пометкой всего достижимого; sweep — проход по куче, где всё непомеченное признаётся мусором и его память возвращается в аллокатор. Всё, что не достижимо от корней, считается мусором по определению — циклические ссылки при этом собираются корректно, в отличие от подсчёта ссылок.

Глубже. См. выше про трёхцветный алгоритм — трёхцветная маркировка это и есть способ сделать фазу mark инкрементальной и конкурентной: цвет объекта кодирует, дошли ли мы до него и просканировали ли его поля, что позволяет прерывать и возобновлять обход. Классический наивный mark-and-sweep целиком останавливает мир на обе фазы, и пауза пропорциональна размеру кучи; Go этого избегает — маркировка идёт параллельно с приложением под защитой write barrier, а подметание ленивое и размазано по последующим аллокациям.

Что важно назвать про сильные и слабые стороны алгоритма. Плюсы: собирает циклы, не требует накладных расходов на каждую операцию с указателем (в отличие от reference counting), не перемещает объекты — значит адреса стабильны, что критично для cgo и unsafe. Минусы: без компактизации остаётся фрагментация (в Go смягчается size-классами mcache/mcentral/mheap), а стоимость маркировки растёт с числом живых объектов — поэтому «много мелких живых объектов» бьёт по GC сильнее, чем «мало больших». Отсюда стандартные советы по оптимизации: уменьшать количество указателей в структурах (объекты без указателей рантайм не сканирует вовсе), переиспользовать буферы через sync.Pool, преаллоцировать срезы и мапы, крутить GOGC/GOMEMLIMIT вместо микрооптимизаций кода.

Частые ошибки на собесе

• Сразу писать код, не уточнив границы входа и не назвав сложность — интервьюер почти всегда снижает оценку именно за это, а не за неоптимальный алгоритм.
• Считать, что жадность «очевидно работает». На номиналах [20, 50, 100, 200, 500] жадность сверху вниз даёт отказ на сумме 60, хотя решение (20+20+20) существует; аналогично ломается жадность в задаче про купоны при мультипликативной скидке.
• Путать классы хеш-функций: предлагать SHA-256 для хранения паролей (нужен bcrypt/Argon2id), считать MD5 «просто устаревшей, но безопасной», делать MAC как hash(key + msg) вместо HMAC.
• Работать со строкой как с массивом символов: s[i] в Go — это байт, поэтому байтовое сравнение ломает палиндромы и анаграммы на кириллице; нужен []rune или utf8-декодирование.
• Говорить, что GC в Go поколенческий или что он «дефрагментирует кучу». Он непоколенческий и неперемещающий; ещё частая ошибка — не знать, зачем нужен write barrier, и не уметь объяснить инвариант «чёрный не указывает на белый».
• В задаче про подсчёт кораблей уходить в DFS-закрашивание, мутируя вход, и не замечать, что локальная проверка «слева и сверху» даёт O(1) памяти — а также не оговаривать, что этот приём требует, чтобы корабли не соприкасались.
• В задачах с большими границами (10⁹ купюр, сумма до 10⁹) писать циклы по единицам или DP по сумме и не следить за типами — int32 переполняется уже на 10⁹ купюр по 500.
• На вопрос об инциденте начинать с «посмотрел бы логи» вместо оценки масштаба, объявления инцидента и митигации; забывать про подтверждение восстановления и безблеймовый постмортем.

Что почитать

• A Guide to the Go Garbage Collector — официальное руководство: pacer, GOGC, GOMEMLIMIT, метрики и практические рекомендации.
• runtime/mgc.go — исходник сборщика с большим вводным комментарием, где по шагам расписаны фазы цикла и гибридный write barrier.
• Go 1.24 Release Notes — переход map на Swiss Tables, runtime.AddCleanup и прочие изменения рантайма.
• Effective Go: Strings, bytes, runes and characters — обязательное чтение перед любой строковой задачей на Go.
• Google SRE Book: Managing Incidents и Postmortem Culture — каркас ответа на вопрос про инцидент в продакшене.