Алгоритмы и лайвкодинг

Формально g(n) = O(f(n)), если существуют c > 0 и n₀ такие, что g(n) ≤ c·f(n) при всех n ≥ n₀. То есть O читается как «не хуже, чем», Ω как «не лучше, чем», Θ как «ровно такого порядка». На собесе почти всегда говорят «O», подразумевая Θ; проговорить разницу одной фразой уже плюс.

Пространственная сложность

Считается дополнительная (auxiliary) память, то есть всё, что алгоритм выделяет сверх входных данных. Про что забывают: глубина рекурсии (каждый кадр стека занимает память), мапы для мемоизации, промежуточные слайсы от append, копия строки при []rune(s). Фраза «решение in-place, O(1) дополнительной памяти» сразу показывает, что ты понимаешь разницу.

Как это звучит на собесе

func twoSum(nums []int, target int) (int, int) {
    seen := make(map[int]int, len(nums))
    for i, v := range nums {
        if j, ok := seen[target-v]; ok {
            return j, i
        }
        seen[v] = i
    }
    return -1, -1
}
// twoSum([]int{2, 7, 11, 15}, 9) → 0, 1
// twoSum([]int{1, 2}, 100)       → -1, -1

«n здесь длина nums. Один проход, внутри одна проверка мапы и одна запись, обе амортизированно O(1). Итого O(n) по времени. По памяти мапа, в худшем случае на все n элементов, то есть O(n). Худший случай по времени формально O(n²), если все ключи дадут коллизии, но в Go хеш рандомизирован сидом, так что практически это O(n).»

Шкала, которую надо чувствовать

Слайс устроен как заголовок из трёх слов (ptr, len, cap) над непрерывным массивом. Отсюда всё поведение:

Что такое амортизация

Амортизированная сложность означает среднюю стоимость операции в длинной серии, а не среднее по случайным входам. Когда cap исчерпан, growslice выделяет новый массив (примерно вдвое больше для небольших слайсов, с плавным коэффициентом, стремящимся к 1.25, после 256 элементов) и копирует туда всё, а это O(n). Но такое случается тем реже, чем больше слайс: суммарное копирование при n вставках складывается в геометрическую прогрессию n + n/2 + n/4 + … < 2n, то есть O(n) на всю серию, O(1) на операцию.

Откуда берётся O(1)

Хеш-функция раскидывает ключи по бакетам примерно равномерно, а load factor (в старой мапе 6.5 элементов на бакет из 8 слотов) ограничивает длину линейного поиска внутри бакета константой. При превышении фактора таблица удваивается, и данные переезжают инкрементально, по паре бакетов на каждую операцию, чтобы не было длинной паузы. В Go 1.24 мапу переписали на Swiss Tables: группа из 8 слотов с байтами-метаданными, которые сканируются одним махом: на amd64 это SIMD-инструкция, на остальных — трюк с 64-битным словом. Асимптотика та же, константа и память лучше.

Откуда берётся O(n)

• Патологические коллизии. Если все ключи дают один и тот же бакет, поиск вырождается в перебор. В Go это нельзя вызвать снаружи: при старте процесса генерируется случайный seed, поэтому одна и та же последовательность ключей на разных запусках раскладывается по-разному, и это защита от HashDoS.
• Плохой хеш у своего типа ключа. Только для языков, где хеш пишет пользователь. В Go хеш для comparable-типов генерирует компилятор, так что испортить его ты не можешь, зато можешь выбрать тяжёлый ключ (длинная строка, большая структура).

Скрытые расходы, о которых стоит сказать

m := map[string]int{}
m[longKey] = 1   // хеш считается по всем байтам ключа: O(len(key))
                 // при коллизии ещё и побайтовое сравнение строк

// Мапу нельзя обойти в порядке ключей: порядок итерации намеренно рандомизирован
for k := range m { ... }   // порядок каждый раз другой

// Отсортированный обход стоит O(n log n):
keys := slices.Sorted(maps.Keys(m))   // Go 1.23: итератор + сортировка

Почему на практике список проигрывает

• Кэш. Процессор читает память линиями по 64 байта и умеет предсказывать последовательный доступ. Слайс из int даёт 8 значений на линию и работающий префетч. Список прыгает по случайному адресу на каждом шаге, префетч бесполезен. На обходе это 10–50× при одинаковой O(n).
• Аллокации и GC. Миллион узлов даёт миллион объектов, которые GC обязан просканировать (они содержат указатели). Слайс из миллиона int остаётся одним объектом, и для []int GC вообще не сканирует содержимое, потому что в типе нет указателей.
• Оверхед. container/list хранит значения в any, добавляя боксинг и косвенность.

Когда список всё-таки нужен

• LRU-кэш: мапа даёт узел за O(1), список переставляет его в голову за O(1). Слайсом так не сделать, мешает сдвиг O(n).
• Очередь задач с удалением из середины по хендлу (например, планировщик таймеров).
• Структуры, где нельзя инвалидировать указатели на элементы при росте: у слайса append может переселить массив, и все &s[i] станут указывать на старую память.

Стек

stack := []int{}
stack = append(stack, v)             // push
top := stack[len(stack)-1]           // peek
stack = stack[:len(stack)-1]         // pop
// если T содержит указатели, обнули слот перед укорачиванием:
// stack[len(stack)-1] = nil

Очередь: почему наивный вариант плох

q = q[1:] двигает вперёд ptr и уменьшает len, но массив под слайсом остаётся живым целиком, пока жив хоть один слайс на него. В цикле enqueue/dequeue underlying array растёт монотонно: обработали миллион задач — держим память под миллион, хотя в очереди три элемента. Формально это не «утечка» (память достижима), но ведёт себя именно так.

Кольцевой буфер

Храним массив фиксированного размера плюс head и size. Хвост вычисляется как (head + size) % cap, поэтому индексы «заворачиваются» через ноль и память переиспользуется. Все четыре операции стоят O(1), рост амортизированно O(1).

type Queue[T any] struct {
    buf        []T
    head, size int
}

func (q *Queue[T]) Push(v T) {
    if q.size == len(q.buf) {
        q.grow()
    }
    q.buf[(q.head+q.size)%len(q.buf)] = v
    q.size++
}

func (q *Queue[T]) Pop() (T, bool) {
    var zero T
    if q.size == 0 {
        return zero, false
    }
    v := q.buf[q.head]
    q.buf[q.head] = zero                 // иначе буфер держит объект
    q.head = (q.head + 1) % len(q.buf)
    q.size--
    return v, true
}
// var q Queue[string]   (grow такой же, как у Deque выше)
// q.Push("a"); q.Push("b"); q.Push("c")
// Pop подряд: "a" "b" "c", затем ("", false)

BST

Инвариант: в левом поддереве ключи меньше корня, в правом больше. Поиск, вставка и удаление стоят O(h). Проблема в том, что h зависит от порядка вставки: если добавлять уже отсортированные данные (тот самый автоинкрементный ID), каждое новое значение уходит вправо, и дерево становится связным списком с O(n) на всё.

Лечат это самобалансирующиеся деревья: AVL (разница высот поддеревьев не больше 1; строже балансирует, значит быстрее читает, но больше поворотов при записи) и красно-чёрное (слабее балансирует, зато дешевле вставка; на нём построены std::map в C++ и TreeMap в Java). В стандартной библиотеке Go сбалансированного дерева нет, есть мапа и sort.

Почему B-tree в базах

• Читается всегда целая страница. Диск и буферный кэш работают блоками по 8–16 КБ. Читать один узел BST с двумя указателями — значит потратить целое чтение страницы ради пары байт.
• Коэффициент ветвления. В страницу 8 КБ влезают сотни ключей, поэтому у B-tree ветвление ~100–500, а высота на миллиард строк всего 3–4. У BST на том же объёме log₂ 10⁹ ≈ 30. Получается 30 обращений против 4.
• B+tree и range scan. В B+tree данные лежат только в листьях, а листья связаны в двусвязный список. Поэтому WHERE x BETWEEN a AND b сводится к одному спуску и последовательному проходу по листьям, а ORDER BY по индексу вообще не требует сортировки.
• Заполнение страниц и fillfactor. B-tree держит узлы заполненными минимум наполовину, что ограничивает фрагментацию и число расщеплений.

Устройство

Каждый узел хранит переходы по символам и флаг «здесь заканчивается слово». Слова с общим префиксом делят один и тот же путь: «go», «gopher», «gorm» идут по общей ветке g → o и расходятся дальше. Ключ не хранится целиком нигде, он «размазан» по рёбрам.

Где применяют

• Поисковые подсказки / автодополнение. Спуск по введённому префиксу за O(L), затем обход поддерева. Часто в узлах ещё хранят топ-k популярных продолжений, чтобы не обходить поддерево целиком.
• Роутинг HTTP. httprouter и chi держат сжатый trie (radix tree) и разбирают пути вида /users/:id/orders за один проход по URL, без регулярок.
• IP-маршрутизация (longest prefix match), словари T9, проверка орфографии, поиск запрещённых слов (Aho–Corasick это trie плюс суффиксные ссылки).

Главная проблема и её решение

Наивный trie расходует память дико: на каждое слово почти столько узлов, сколько в нём символов, а в каждом узле сидит мапа или массив на весь алфавит. Отсюда radix tree (он же patricia): цепочки узлов с одним ребёнком склеиваются в один узел с целой подстрокой на ребре. Для URL-роутера или IP-таблицы это сокращает число узлов на порядок.

Механика

• Push: положить в конец массива и «всплывать» (sift up), меняясь местами с родителем, пока нарушается инвариант. Максимум log n обменов.
• Pop: минимум лежит в a[0]. Забираем его, переносим последний элемент в корень, сокращаем длину и «топим» (sift down), меняясь с меньшим из детей.
• Init: sift down для всех узлов с n/2 - 1 вниз до 0. Это O(n), а не O(n log n): у большинства узлов маленькая высота, и сумма высот всех узлов линейна.
• Fix(i): элемент изменился, восстанавливаем инвариант из позиции i за O(log n). Именно так делают «изменить приоритет» в очереди с приоритетами.

container/heap: пакет даёт алгоритмы, хранилище — твоё

// Очередь с приоритетами по задачам
type Item struct {
    Value    string
    Priority int
    index    int   // позиция в куче, нужна для heap.Fix / heap.Remove
}

type PQ []*Item

func (pq PQ) Len() int { return len(pq) }
// Больший Priority = выше приоритет → max-heap: знак ">"
func (pq PQ) Less(i, j int) bool { return pq[i].Priority > pq[j].Priority }
func (pq PQ) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index, pq[j].index = i, j     // синхронизируем index
}

func (pq *PQ) Push(x any) {
    it := x.(*Item)
    it.index = len(*pq)
    *pq = append(*pq, it)
}

func (pq *PQ) Pop() any {
    old := *pq
    n := len(old)
    it := old[n-1]
    old[n-1] = nil      // помогаем GC
    it.index = -1
    *pq = old[:n-1]
    return it
}

func main() {
    pq := &PQ{}
    heap.Init(pq)
    heap.Push(pq, &Item{Value: "low", Priority: 1})
    heap.Push(pq, &Item{Value: "high", Priority: 9})

    top := (*pq)[0]                 // максимум за O(1), без извлечения
    top.Priority = 0
    heap.Fix(pq, top.index)         // приоритет изменился, чиним за O(log n)

    it := heap.Pop(pq).(*Item)      // O(log n)
    _ = it
}

Представление

// Список смежности берут почти всегда
type Graph map[int][]int
// или, если вершины плотно занумерованы 0..V-1, быстрее и компактнее:
adj := make([][]int, V)
adj[u] = append(adj[u], v)

// Матрица смежности нужна на плотных графах с частыми проверками "есть ребро?"
m := make([][]bool, V)
for i := range m { m[i] = make([]bool, V) }
m[u][v] = true

Реальные графы (соцсеть, дорожная сеть, зависимости сервисов) разрежены: E ≪ V². Матрица на 10⁵ вершин займёт 10¹⁰ ячеек, то есть неприменима. Поэтому по умолчанию список.

BFS: очередь, уровни, кратчайший путь

// Кратчайший путь в невзвешенном графе + восстановление маршрута
func ShortestPath(g Graph, from, to int) []int {
    if from == to {
        return []int{from}
    }
    prev := map[int]int{from: -1}
    queue := []int{from}
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        for _, v := range g[u] {
            if _, seen := prev[v]; seen {
                continue
            }
            prev[v] = u                 // помечаем при добавлении, иначе дубли в очереди
            if v == to {
                // разворачиваем путь назад по prev
                path := []int{to}
                for x := u; x != -1; x = prev[x] {
                    path = append(path, x)
                }
                slices.Reverse(path)
                return path
            }
            queue = append(queue, v)
        }
    }
    return nil
}
// g := Graph{1: {2, 3}, 2: {4}, 3: {4, 5}, 4: {5}, 5: nil}
// ShortestPath(g, 1, 5) → [1 3 5]   — два ребра, а не три через 2→4→5
// ShortestPath(g, 1, 1) → [1]
// ShortestPath(g, 5, 1) → [] (nil)  — граф ориентированный, пути назад нет

Обход «по уровням» (сколько шагов до вершины) получается, если замерить длину очереди в начале итерации: levelSize := len(queue), и сделать ровно столько извлечений. Тот же приём, что и в задаче «BFS по уровням дерева».

DFS: рекурсия или явный стек

// Поиск цикла в ориентированном графе: три цвета
const (white = 0; grey = 1; black = 2)

func hasCycle(g Graph, V int) bool {
    color := make([]int, V)
    var dfs func(u int) bool
    dfs = func(u int) bool {
        color[u] = grey                 // вошли, ещё не вышли
        for _, v := range g[u] {
            if color[v] == grey {       // ребро в "серую" вершину = обратное ребро = цикл
                return true
            }
            if color[v] == white && dfs(v) {
                return true
            }
        }
        color[u] = black
        return false
    }
    for u := 0; u < V; u++ {
        if color[u] == white && dfs(u) {
            return true
        }
    }
    return false
}
// hasCycle(Graph{0: {1}, 1: {2}, 2: {0}}, 3) → true    — 0→1→2→0
// hasCycle(Graph{0: {1}, 1: {2}},          3) → false

Минимальный набор, который надо назвать

• Вставками работает за O(n²), но на почти отсортированных данных сваливается в O(n) и держит минимальную константу на коротких массивах. Поэтому живёт внутри всех промышленных гибридов.
• Слиянием даёт гарантированные O(n log n), стабильна, требует O(n) памяти. Основа внешней сортировки (когда данные не влезают в память) и легко распараллеливается.
• Быстрая: O(n log n) в среднем, O(n²) в худшем (отсортированный вход при наивном выборе опорного), in-place, лучшая константа.
• Пирамидальная гарантирует O(n log n) и O(1) памяти, нестабильна, константа хуже quicksort. Её держат как страховку от вырождения quicksort.
• Подсчётом / поразрядная обходит барьер O(n log n) за O(n + k), потому что не сравнивает элементы, а использует структуру ключа. Работает для целых в ограниченном диапазоне.

Почему O(n log n) — барьер

Любая сортировка сравнением — это дерево решений: каждое сравнение даёт один бит информации, а различить нужно n! перестановок. Высота дерева не меньше log₂(n!) ≈ n log₂ n − 1.44n. Отсюда нижняя оценка. Counting/radix её не нарушают — они просто не сравнивают.

Что внутри Go

Стабильность

Сортировка стабильна, если элементы с равными ключами сохраняют исходный относительный порядок. Практический смысл — сортировка по нескольким полям в несколько проходов: сначала по имени, затем стабильно по отделу — и внутри отдела имена останутся отсортированными. Ещё стабильность важна для воспроизводимости вывода (диффы, отчёты).

// Порядок равных элементов у нестабильной сортировки не определён:
// сегодня он один, а после смены версии Go может стать другим.
// Нужен предсказуемый — бери стабильную:
slices.SortStableFunc(rows, func(a, b Row) int { return cmp.Compare(a.Dept, b.Dept) })

// Либо один компаратор на все ключи — тогда стабильность не нужна:
slices.SortFunc(rows, func(a, b Row) int {
    if c := cmp.Compare(a.Dept, b.Dept); c != 0 {
        return c
    }
    return cmp.Compare(a.Name, b.Name)
})

// Найти индекс target или -1
func Search(a []int, target int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        switch {
        case a[mid] == target:
            return mid
        case a[mid] < target:
            lo = mid + 1
        default:
            hi = mid - 1
        }
    }
    return -1
}

// Первая позиция, где a[i] >= target (lower bound). Универсальнее.
func LowerBound(a []int, target int) int {
    lo, hi := 0, len(a)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if a[mid] < target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

// Первая позиция, где a[i] > target (upper bound) — тот же код со строгим сравнением
// количество вхождений target = UpperBound(a, t) - LowerBound(a, t)
// a := []int{1, 3, 3, 5, 8}
// Search(a, 5) → 3       Search(a, 4) → -1
// LowerBound(a, 3) → 1   LowerBound(a, 4) → 3   LowerBound(a, 9) → 5

Где ошибаются

1. (lo+hi)/2 вместо lo + (hi-lo)/2. В Go int 64-битный, реально не переполнится, но это каноничная ошибка (в JDK жила девять лет), и её проверяют.
2. lo < hi при замкнутом отрезке [lo, hi] — пропускается последний кандидат, когда lo == hi.
3. lo = mid вместо lo = mid + 1 в полуинтервальной версии — при hi - lo == 1 получается mid == lo, отрезок не сокращается, бесконечный цикл.
4. Не спросили, отсортирован ли вход. Бинарный поиск требует монотонности — без неё ответ мусор.
5. Забыли про дубликаты: «найти любой» и «найти первый» — разные задачи, и именно поэтому lower bound надёжнее.

Стандартная библиотека

i := sort.SearchInts(a, x)           // lower bound; если не нашли — позиция вставки
i = sort.Search(len(a), func(i int) bool { return a[i] >= x })

idx, ok := slices.BinarySearch(a, x)                  // Go 1.21+
idx, ok = slices.BinarySearchFunc(users, u, cmpByID)  // с компаратором

sort.Search(n, f) возвращает наименьшее i из [0, n), для которого f(i) == true (или n, если такого нет), и требует, чтобы f была монотонной: false…false,true…true. Немонотонный предикат не вызовет паники — просто вернёт неверный результат.

Базовая механика

1. Считаем h = hash(key).
2. Младшие биты h дают номер бакета: bucket = h & (2^B - 1).
3. Внутри бакета ищем слот. Чтобы не сравнивать ключи целиком, сначала сверяем короткий «отпечаток» хеша (старшие 8 бит — tophash в старой мапе, control byte в Swiss Tables). Полное сравнение ключей — только при совпадении отпечатка.

Коллизии: две школы

Что специфично для Go

• Рандомизация хеша. Seed генерируется при старте процесса, поэтому одна и та же последовательность ключей раскладывается по-разному на разных запусках. Это защита от HashDoS и одновременно причина, по которой порядок итерации нельзя считать стабильным (плюс рантайм ещё и стартует итерацию со случайного бакета).
• Инкрементальный рост. При превышении load factor выделяется вдвое больший массив, но перенос делается по чуть-чуть на каждой записи (evacuate), чтобы не было длинной паузы на одной операции.
• Рост «вширь» без увеличения размера. Если элементов немного, а overflow-бакетов развелось много (последствия массовых удалений), мапа делает same-size grow — просто уплотняется.
• Мапа не потокобезопасна и специально ловит конкурентную запись: fatal error: concurrent map writes — это не паника, её нельзя перехватить через recover.
• Значения мапы неадресуемы: &m[k] запрещено, а m[k].field = v для структуры не скомпилируется — потому что при росте бакеты переезжают и адрес был бы недействителен. Обходной путь — map[K]*V или «прочитал, изменил, записал обратно».

Идея

В лоб получаются два вложенных цикла, O(n²). Ускорение классическое: внутренний цикл «есть ли где-то нужное число» заменяем на хеш-поиск за O(1). Порядок важен: сначала проверяем, потом кладём текущий элемент в мапу. Так один и тот же элемент не будет использован дважды, и не нужен отдельный костыль if i != j.

func twoSum(nums []int, target int) (int, int, bool) {
    seen := make(map[int]int, len(nums)) // значение -> его индекс
    for i, v := range nums {
        if j, ok := seen[target-v]; ok {
            return j, i, true            // j всегда меньше i
        }
        seen[v] = i                      // кладём после проверки
    }
    return 0, 0, false
}
// twoSum([]int{2, 7, 11, 15}, 9) → 0 1 true
// twoSum([]int{3, 2, 4}, 6)      → 1 2 true
// twoSum([]int{3, 3}, 6)         → 0 1 true
// twoSum([]int{1, 2, 5}, 100)    → 0 0 false

Сложность

Время O(n) — один проход, каждая операция с мапой в среднем O(1). Память O(n) на мапу. Предварительная аллокация make(map[int]int, len(nums)) убирает несколько рехеширований, и такую мелочь интервьюер замечает.

Подводные камни

• Дубликаты. nums = [3,3], target = 6. При «сначала заполнить мапу, потом искать» второй 3 перезатрёт индекс первого, и решение вернёт (1,1). Порядок «проверил → записал» это чинит автоматически.
• Что возвращать при отсутствии пары. Идиоматично вернуть (int, int, bool) или ошибку, а не (-1,-1). Проговори это вслух, это вопрос про контракт.
• Переполнение target - v для крайних int64 достаточно упомянуть вслух.

Добивки, которые обычно задают

• «А если слайс отсортирован?» Тогда два указателя с концов: O(n) времени и O(1) памяти — строго лучше мапы. Именно этого ответа и ждут.
• «А three sum?» Отсортировать (O(n log n)), зафиксировать первый элемент циклом и на остатке применить два указателя: суммарно O(n²) времени, O(1) доп. памяти. Не забыть пропуск дубликатов, иначе тройки повторятся.
• «А если надо все пары, а не одну?» map[int][]int и продолжать проход.

Идея

Скобки сводятся к вложенности, а вложенность к LIFO. В Go стек не нужен как тип: слайс уже стек. Роль push играет append, peek читается как st[len(st)-1], pop пишется как st = st[:len(st)-1].

func validParens(s string) bool {
    pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
    st := make([]rune, 0, len(s)) // ёмкость сразу: больше len(s) не понадобится

    for _, r := range s {
        switch r {
        case '(', '[', '{':
            st = append(st, r)
        case ')', ']', '}':
            if len(st) == 0 || st[len(st)-1] != pairs[r] {
                return false      // либо закрыли пустоту, либо не ту скобку
            }
            st = st[:len(st)-1]
        default:
            // другие символы игнорируем; уточни у интервьюера, так ли надо
        }
    }
    return len(st) == 0            // незакрытые остались -> невалидно
}
// "()[]{}" → true     "([{}])" → true     "a(b)c" → true
// "(]"     → false    "([)]"   → false
// "("      → false    ""       → true  ← пустая строка валидна, это стоит проговорить

Сложность

Время O(n), память O(n) в худшем случае (строка "(((((").

Подводные камни

• Забыть проверку len(st) == 0 перед взятием вершины — паника index out of range на строке ")". Это ошибка номер один.
• Забыть финальную проверку пустоты стека — тогда "((" считается валидной.
• Ветка default. Если по условию строка может содержать буквы, надо спросить: игнорировать или считать невалидной. Выберешь молча, получишь минус.
• st = st[:len(st)-1] не отдаёт память, но для скобок это неважно; если бы в стеке лежали указатели, стоило бы занулять снятый элемент.

Два решения и когда какое

// Через сортировку: O(n log n)
func isAnagramSort(a, b string) bool {
    ra, rb := []rune(a), []rune(b)
    if len(ra) != len(rb) {
        return false
    }
    slices.Sort(ra)
    slices.Sort(rb)
    return slices.Equal(ra, rb)
}
// isAnagramSort("аргон", "орган") → true
// isAnagramSort("go", "og")       → true
// isAnagramSort("abc", "abd")     → false

// Через частоты: O(n), одна мапа
func isAnagram(a, b string) bool {
    ra, rb := []rune(a), []rune(b)
    if len(ra) != len(rb) {
        return false
    }
    cnt := make(map[rune]int, len(ra))
    for _, r := range ra {
        cnt[r]++
    }
    for _, r := range rb {
        cnt[r]--
        if cnt[r] == 0 {
            delete(cnt, r)
        }
    }
    return len(cnt) == 0
}
// isAnagram("аргон", "орган") → true     isAnagram("", "")     → true
// isAnagram("abc", "abd")     → false    isAnagram("aab","abb") → false

Почему len(ra) != len(rb), а не len(a) != len(b)

len(string) возвращает длину в байтах. Строки "ab" и "я" имеют разное число символов, но "я" занимает 2 байта — и такой проверкой можно случайно пропустить или отсечь неверно. На тексте только из ASCII разницы нет, на русском она вылезает. Ранняя проверка длин при этом полезна: она отсекает большинство пар за O(1).

Оптимизация для ASCII

// Если в условии только строчные a..z, хватит массива:
func isAnagramASCII(a, b string) bool {
    if len(a) != len(b) {
        return false
    }
    var cnt [26]int          // на стеке, без аллокаций и хеширования
    for i := 0; i < len(a); i++ {
        cnt[a[i]-'a']++
        cnt[b[i]-'a']--
    }
    for _, c := range cnt {
        if c != 0 {
            return false
        }
    }
    return true
}
// isAnagramASCII("listen", "silent") → true
// isAnagramASCII("abc", "abd")       → false
// isAnagramASCII("aab", "abb")       → false

Массив на 26 позиций быстрее мапы в разы: нет хеширования, нет аллокаций, всё в кэше. Но это решение под конкретное условие — обязательно скажи, что оно ломается на любом не-ASCII вводе. Мидла от джуна отличает как раз умение назвать границы применимости своей оптимизации.

Добивки

• «Сгруппируй анаграммы в списке слов». Ключом группы служит отсортированная строка или канонический счётчик; map[string][]string, O(n·k log k).
• «Регистр и пробелы?» Вопрос к контракту: strings.ToLower плюс фильтрация.
• «Юникод-нормализация?» "é" может быть одной руной U+00E9 или двумя (e + U+0301). Формально нужна NFC-нормализация через golang.org/x/text/unicode/norm. Скажи про неё вслух, это сильный ход.

Почему именно два прохода

Мапа не хранит порядок вставки, и в Go порядок итерации по ней намеренно рандомизирован. Поэтому «пройти по мапе и найти единичку» даёт случайный ответ, а не первый. Порядок нам даёт сама строка — по ней и идём второй раз.

// возвращаем руну и её байтовый индекс
func firstUniq(s string) (rune, int, bool) {
    cnt := make(map[rune]int, len(s))
    for _, r := range s {
        cnt[r]++
    }
    for i, r := range s {   // i считает байты, а не символы
        if cnt[r] == 1 {
            return r, i, true
        }
    }
    return 0, 0, false
}
// firstUniq("swiss")  → 'w', 1, true
// firstUniq("привет") → 'п', 0, true   ← индекс байтовый: для "ивет" он был бы 4, а не 2
// firstUniq("aabb")   → 0, 0, false

Вариант в один проход

Хранить в мапе не счётчик, а первую позицию, и помечать повторы «минус единицей»; затем один раз пробежать по мапе и взять минимальную позицию. По строке идём один раз, но добавляется проход по мапе — суммарно та же O(n), зато порядок восстанавливается минимумом, а не итерацией.

func firstUniqOnePass(s string) (rune, bool) {
    type info struct {
        pos int
        cnt int
    }
    seen := make(map[rune]*info, len(s))
    for i, r := range s {
        if in, ok := seen[r]; ok {
            in.cnt++
        } else {
            seen[r] = &info{pos: i, cnt: 1}
        }
    }
    best, res, found := len(s), rune(0), false
    for r, in := range seen {
        if in.cnt == 1 && in.pos < best {
            best, res, found = in.pos, r, true
        }
    }
    return res, found
}
// firstUniqOnePass("swiss")  → 'w', true
// firstUniqOnePass("привет") → 'п', true
// firstUniqOnePass("aabb")   → 0, false

Сложность и грабли

• Время O(n), память O(k) по числу различных символов (для ASCII это константа 128).
• Главная ловушка Go: написать for i := 0; i < len(s); i++ { cnt[s[i]]++ }. Это счёт по байтам: русская буква распадётся на два «символа», и функция начнёт врать.
• Индекс из range байтовый. Если по условию нужен «номер символа», заводи отдельный счётчик или работай с []rune.

Базовый вариант

func isPalindrome(s string) bool {
    r := []rune(s)
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        if r[i] != r[j] {
            return false
        }
    }
    return true
}
// isPalindrome("шалаш") → true    isPalindrome("топот") → true
// isPalindrome("Шалаш") → false   ← регистр не нормализуется
// isPalindrome("go")    → false

Условие цикла i < j, а не i <= j: при нечётной длине средний символ сравнивать сам с собой бессмысленно. Оба варианта работают, но < выдаёт аккуратность.

Полный вариант: нормализация «на месте»

func isPalindromeClean(s string) bool {
    r := []rune(strings.ToLower(s))

    // фильтруем in-place: переиспользуем тот же массив, без второй аллокации
    keep := r[:0]
    for _, c := range r {
        if unicode.IsLetter(c) || unicode.IsDigit(c) {
            keep = append(keep, c)
        }
    }

    for i, j := 0, len(keep)-1; i < j; i, j = i+1, j-1 {
        if keep[i] != keep[j] {
            return false
        }
    }
    return true
}
// isPalindromeClean("А роза упала на лапу Азора")   → true
// isPalindromeClean("A man, a plan, a canal: Panama") → true
// isPalindromeClean("hello")                        → false

Приём keep := r[:0] фильтрует слайс без выделения нового массива: пишем поверх исходного, потому что пишущий индекс никогда не обгоняет читающий. Это тот самый «Go-специфичный» штрих, который замечают.

Добивки

• «Без аллокации []rune?» Можно идти utf8.DecodeRuneInString слева и utf8.DecodeLastRuneInString справа, тогда O(1) памяти на любой строке.
• «Палиндром ли число, без перевода в строку?» Разворачиваем половину числа арифметикой: rev = rev*10 + n%10.
• «Можно удалить один символ — палиндром?» Те же два указателя: при первом несовпадении пробуем пропустить левый или правый и проверить остаток. По-прежнему O(n).

Слайс — честный in-place

func reverse[T any](s []T) {          // дженерик с Go 1.18
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}
// в стандартной библиотеке с Go 1.21 это уже есть: slices.Reverse(s)
// a := []int{1, 2, 3, 4};      reverse(a) → a стал [4 3 2 1]
// s := []string{"a","b","c"};  reverse(s) → s стал [c b a]

Строка — только через копию

func reverseString(s string) string {
    r := []rune(s)                    // аллокация: 4 байта на руну
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        r[i], r[j] = r[j], r[i]
    }
    return string(r)                  // ещё одна аллокация
}
// reverseString("привет") → "тевирп"
// reverseString("Go!")    → "!oG"
// reverseString("")       → ""

Две аллокации неизбежны: строка иммутабельна, её данные лежат в read-only секции или разделяются другими строками. Попытка []byte(s)[0] = 'x' компилируется, но меняет копию, а не строку.

Три уровня «правильности»

Смежная задача: развернуть слова в предложении

func reverseWords(s string) string {
    w := strings.Fields(s)   // Fields сам схлопывает любые пробельные последовательности
    slices.Reverse(w)
    return strings.Join(w, " ")
}
// reverseWords("  привет   мир  из Go ") → "Go из мир привет"
// reverseWords("one")                    → "one"

strings.Fields вместо strings.Split(s, " ") здесь не придирка: Split на двойном пробеле даст пустые элементы.

func mergeSorted(a, b []int) []int {
    out := make([]int, 0, len(a)+len(b)) // ровно один раз аллоцируем нужный размер
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {               // именно <=, иначе теряется стабильность
            out = append(out, a[i])
            i++
        } else {
            out = append(out, b[j])
            j++
        }
    }
    out = append(out, a[i:]...)          // один из двух хвостов пуст
    out = append(out, b[j:]...)
    return out
}
// mergeSorted([]int{1, 3, 5}, []int{2, 3, 8, 9}) → [1 2 3 3 5 8 9]
// mergeSorted(nil, []int{1, 2})                  → [1 2]
// mergeSorted([]int{1, 2}, nil)                  → [1 2]

Почему <=, а не <

При равных элементах <= берёт элемент из a первым, то есть сохраняет относительный порядок «сначала первый слайс». Для int разницы не видно, а для структур с ключом это ровно стабильность слияния, и на ней держится стабильная merge sort. Скажешь это — станет видно, что понимаешь, а не заучил.

Сложность

Время O(n+m), память O(n+m) под результат. Дополнительной памяти сверх результата нет. Без make с ёмкостью было бы log₂(n+m) реаллокаций с копированием — всё ещё O(n+m) амортизированно, но с константой в несколько раз хуже.

Вариант «слить в первый слайс, места хватает»

Классическая добивка (LeetCode 88): a длиной m+n, первые m элементов значимы. Слева направо идти нельзя — затрём непрочитанное. Идём справа налево, записывая максимумы в конец:

func mergeInPlace(a []int, m int, b []int, n int) {
    i, j, k := m-1, n-1, m+n-1
    for j >= 0 {                       // b кончился, всё уже на месте
        if i >= 0 && a[i] > b[j] {
            a[k] = a[i]
            i--
        } else {
            a[k] = b[j]
            j--
        }
        k--
    }
}
// a := []int{1, 3, 5, 0, 0, 0}; b := []int{2, 4, 6}
// mergeInPlace(a, 3, b, 3) → a стал [1 2 3 4 5 6]

O(n+m) времени и O(1) дополнительной памяти. Условие цикла j >= 0, а не i >= 0 || j >= 0: когда b исчерпан, остаток a уже лежит на своих местах и копировать его незачем.

Добивки

• «Слить k отсортированных слайсов». Куча из k голов: O(N log k), где N это суммарная длина. Наивно попарно выйдет O(N·k).
• «А если это потоки/каналы?» Та же логика, но на каналах, и это уже тема 1.3.

Общий случай: множество на мапе

func intersect(a, b []int) []int {
    if len(a) > len(b) {
        a, b = b, a          // мапу строим по меньшему слайсу: память O(min(n,m))
    }
    set := make(map[int]struct{}, len(a))
    for _, v := range a {
        set[v] = struct{}{}  // struct{} не занимает места, в отличие от bool
    }
    out := make([]int, 0, len(a))
    for _, v := range b {
        if _, ok := set[v]; ok {
            out = append(out, v)
            delete(set, v)   // чтобы дубликаты b не размножили результат
        }
    }
    return out
}
// intersect([]int{1, 2, 2, 3}, []int{2, 2, 3, 4}) → [2 3]  ← дубль двойки не размножился
// intersect([]int{1, 2}, []int{3, 4})             → []

Два штриха, за которые ставят плюс: строим мапу по короткому слайсу и берём map[T]struct{} как множество. struct{} нулевого размера, поэтому множество из миллиона int весит столько же, сколько ключи, без байта на значение.

Отсортированный случай: два указателя

func intersectSorted(a, b []int) []int {
    var out []int
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        switch {
        case a[i] < b[j]:
            i++
        case a[i] > b[j]:
            j++
        default:
            // пропускаем повтор, если хотим уникальные значения
            if len(out) == 0 || out[len(out)-1] != a[i] {
                out = append(out, a[i])
            }
            i++
            j++
        }
    }
    return out
}
// intersectSorted([]int{1, 2, 2, 3}, []int{2, 2, 3, 4}) → [2 3]
// intersectSorted([]int{1, 2}, []int{3, 4})             → [] (nil)

Сравнение

func dedupSorted(a []int) []int {
    if len(a) < 2 {
        return a
    }
    k := 1                          // длина уже собранного уникального префикса
    for i := 1; i < len(a); i++ {
        if a[i] != a[k-1] {         // сравниваем с последним записанным, не с a[i-1]
            a[k] = a[i]
            k++
        }
    }
    return a[:k]
}
// a := []int{1, 1, 2, 3, 3, 3, 4}
// dedupSorted(a) → [1 2 3 4]
// но сам a теперь [1 2 3 4 3 3 4] — функция пишет поверх входного слайса.
// Вызывающего предупреди: результат смотрит в тот же массив.

Что здесь важно объяснить

• Сравниваем с a[k-1], то есть с последним записанным. Вариант с a[i-1] тоже работает для отсортированного входа, но ломается, как только задачу расширяют до «оставить не более двух одинаковых».
• Функция возвращает a[:k], а не меняет длину у вызывающего: длина живёт в заголовке слайса, а он передан по значению. Про возврат часто забывают.
• Элементы за k остаются в массиве как мусор. Для int это безобидно, а на указателях или структурах с указателями выходит утечка: GC не соберёт объекты, на которые ссылается хвост. Правильно занулить: clear(a[k:]) (Go 1.21).

Обобщённая фильтрация тем же приёмом

// Общий идиоматичный шаблон «оставить подходящие, без новой аллокации»
out := a[:0]
for _, v := range a {
    if keep(v) {
        out = append(out, v)
    }
}
clear(a[len(out):])  // обнулить хвост, если в слайсе указатели
a = out

Дубликаты в НЕотсортированном слайсе

func dedupAny[T comparable](a []T) []T {
    seen := make(map[T]struct{}, len(a))
    out := a[:0]
    for _, v := range a {
        if _, ok := seen[v]; ok {
            continue
        }
        seen[v] = struct{}{}
        out = append(out, v)
    }
    return out
}
// dedupAny([]string{"b", "a", "b", "c", "a"}) → [b a c]   ← порядок первого вхождения
// dedupAny([]int{3, 1, 3, 1})                 → [3 1]
// Вход, как и в dedupSorted, портится: out указывает на a[:0].

O(n) времени, O(n) памяти, порядок первого появления сохраняется. Для отсортированного входа мапа не нужна: O(1) памяти. Разницу обязательно проговори — на ней и строится вопрос. В стандартной библиотеке с Go 1.21 есть slices.Compact, ровно первый вариант.

func maxSumK(a []int, k int) (int, bool) {
    if k <= 0 || len(a) < k {
        return 0, false            // невалидный вход: контракт обговори заранее
    }
    sum := 0
    for _, v := range a[:k] {
        sum += v
    }
    best := sum
    for i := k; i < len(a); i++ {
        sum += a[i] - a[i-k]       // вошёл a[i], вышел a[i-k]
        if sum > best {
            best = sum
        }
    }
    return best, true
}
// maxSumK([]int{2, 1, 5, 1, 3, 2}, 3) → 9, true    ← 5+1+3
// maxSumK([]int{-1, -2, -3}, 2)       → -3, true   ← -1-2, «максимум» может быть отрицательным
// maxSumK([]int{1, 2}, 5)             → 0, false   ← k больше длины

Почему нельзя инициализировать best := 0

Если все числа отрицательные, ноль окажется «лучшим» и функция вернёт неправильный ответ. Стартовать надо от первого реального окна. Это классическая ловушка, которую интервьюер проверяет тестом [-5,-2,-9], k = 2 (правильный ответ −7).

Сложность

Наивно: n-k+1 окон по O(k) каждое, итого O(n·k). Инкрементально выходит O(n), потому что каждый элемент ровно один раз входит в окно и ровно один раз выходит. Память O(1): никаких структур, только sum и best.

Родственные задачи, которые часто дают следом

• Максимальная сумма подмассива произвольной длины решается алгоритмом Кадане, тоже O(n): cur = max(v, cur+v); best = max(best, cur).
• Минимальная длина подмассива с суммой ≥ target при положительных числах берётся окном переменной длины: расширяем правым, сжимаем левым, пока сумма достаточна.
• Среднее по окну / скользящий максимум. Для максимума нужна монотонная дека (deque на слайсе), тоже O(n) — красивая добивка, если останется время.
• Префиксные суммы как альтернатива: pre[i+1] = pre[i] + a[i], тогда сумма любого отрезка считается за O(1), а память O(n). Полезно, когда запросов много.

Решение

func longestUnique(s string) int {
    rs := []rune(s)                       // работаем в рунах: индексы сравнимы
    last := make(map[rune]int, len(rs))   // руна -> её последний индекс
    best, left := 0, 0

    for i, r := range rs {
        if j, ok := last[r]; ok && j >= left {
            left = j + 1                  // прыжок, а не сдвиг на единицу
        }
        last[r] = i
        if n := i - left + 1; n > best {
            best = n
        }
    }
    return best
}
// longestUnique("abcabcbb") → 3   ("abc")
// longestUnique("bbbbb")    → 1
// longestUnique("pwwkew")   → 3   ("wke")
// longestUnique("абвабв")   → 3   ← руны, а не байты
// longestUnique("")         → 0

Две тонкости, на которых валятся

• Проверка j >= left. В мапе остаются позиции символов, которые уже вышли из окна. Без этой проверки левая граница может уехать назад, окно «расширится» задним числом и ответ будет завышен. Тест: "abba" — без проверки получится 3 вместо 2.
• Прыжок вместо сдвига. left = j + 1 сразу выкидывает весь префикс до повторившегося символа. Вариант «сдвигать left по одному, пока повтор не уйдёт» тоже даёт O(n) амортизированно, но требует мапы счётчиков:

// Вариант со счётчиками, обобщается на «не более k повторов»
func longestUniqueCount(s string) int {
    rs := []rune(s)
    cnt := make(map[rune]int, len(rs))
    best, left := 0, 0
    for right, r := range rs {
        cnt[r]++
        for cnt[r] > 1 {          // сжимаем окно, пока нарушено условие
            cnt[rs[left]]--
            left++
        }
        if n := right - left + 1; n > best {
            best = n
        }
    }
    return best
}
// Ответы те же: "abcabcbb" → 3, "bbbbb" → 1, "pwwkew" → 3, "абвабв" → 3, "" → 0

Почему это O(n), хотя циклов два

Внутренний for двигает только left, а left монотонно растёт и не может превысить n. Суммарно оба указателя делают не больше 2n шагов. Этот аргумент про амортизацию надо уметь произнести вслух. «Два вложенных цикла» пугают интервьюера, пока ты не объяснишь.

Память и вариации

Память O(k), где k это размер алфавита в окне. Для ASCII можно заменить мапу на [128]int и получить константную память. Естественные добивки: «верни саму подстроку, а не длину» (string(rs[bestLeft:bestLeft+best])), «не более двух различных символов», «не более k повторов». Всё это тот же каркас окна, меняется только условие сжатия.

type Interval struct {
    Start, End int
}

func mergeIntervals(in []Interval) []Interval {
    if len(in) == 0 {
        return nil
    }
    s := make([]Interval, len(in))
    copy(s, in)                       // не портим вход вызывающего
    slices.SortFunc(s, func(a, b Interval) int {
        return cmp.Compare(a.Start, b.Start)
    })

    out := make([]Interval, 0, len(s))
    out = append(out, s[0])
    for _, cur := range s[1:] {
        last := &out[len(out)-1]      // указатель на последний собранный интервал
        if cur.Start <= last.End {    // пересекаются или касаются
            if cur.End > last.End {
                last.End = cur.End    // расширяем; не присваиваем cur.End вслепую
            }
        } else {
            out = append(out, cur)
        }
    }
    return out
}
// in := []Interval{{1, 3}, {8, 10}, {2, 6}, {15, 18}}
// mergeIntervals(in) → [{1 6} {8 10} {15 18}]
// in после вызова   → [{1 3} {8 10} {2 6} {15 18}] ← вход не тронут, это и была цель copy
// mergeIntervals([]Interval{{1, 4}, {4, 5}}) → [{1 5}]  ← касание тоже склеиваем
// mergeIntervals(nil)                        → [] (nil)

Почему сортировка по началу решает задачу

После сортировки любой следующий интервал начинается не раньше текущего. Значит, пересечение возможно только с последним собранным: если он не пересекается, то и все предыдущие (они кончаются ещё левее) не пересекутся. Отсюда один линейный проход после сортировки, без вложенного перебора.

Сложность

Сортировка доминирует, отсюда O(n log n); сам проход O(n). Память O(n) под копию и результат. Если вход портить разрешено, копию можно не делать и получить O(1) дополнительной памяти сверх результата.

Три места, где ошибаются

• last.End = cur.End без сравнения. Для [1,10] и [2,3] получится [1,3], интервал «схлопнется». Нужно max(last.End, cur.End).
• < вместо <=. Вопрос к контракту: считать ли [1,2] и [2,3] пересекающимися. Для закрытых интервалов да, для полуинтервалов [start, end) нет. Спроси.
• Берём &out[len(out)-1], а потом append в том же шаге. В коде выше этого нет (ветки взаимоисключающие), но если перепутать — указатель повиснет на старом массиве после реаллокации, и изменение потеряется. Классическая Go-ловушка.

Добивки

• «Вставить один интервал в уже объединённый список». Бинарный поиск позиции плюс локальное слияние: O(log n + k).
• «Сколько переговорок нужно для списка встреч?» Это та же сортировка, но по событиям: +1 на начало, -1 на конец, максимум префиксной суммы. Либо мин-куча концов, тоже O(n log n).
• «Найти свободные окна». Дополнение к объединённым интервалам, тот же проход.

Три реализации

// 1) Наивная рекурсия: O(fib(n)) вызовов, экспонента
func fibRec(n int) int {
    if n < 2 {
        return n
    }
    return fibRec(n-1) + fibRec(n-2)
}

// 2) Мемоизация (top-down динамика): O(n) времени, O(n) памяти
func fibMemo(n int, memo map[int]int) int {
    if n < 2 {
        return n
    }
    if v, ok := memo[n]; ok {
        return v
    }
    v := fibMemo(n-1, memo) + fibMemo(n-2, memo)
    memo[n] = v
    return v
}

// 3) Итерация (bottom-up): O(n) времени, O(1) памяти — лучший выбор
func fib(n int) int {
    a, b := 0, 1
    for i := 0; i < n; i++ {
        a, b = b, a+b
    }
    return a
}
// fibRec(10) = fibMemo(10, map[int]int{}) = fib(10) = 55
// fib(0..9): 0 1 1 2 3 5 8 13 21 34
// fib(50) = 12586269025
// fibMemo(90, ...) = 2880067194370816120 — а fib(93) уже переполнит int64

Почему наивная рекурсия экспоненциальна

Дерево вызовов fib(5) считает fib(3) дважды, fib(2) трижды. Число листьев дерева равно самому fib(n), а он растёт как φⁿ/√5, где φ ≈ 1.618. Отсюда и O(1.618ⁿ): fib(50) наивно это порядка 2·10⁹ вызовов, секунды работы; fib(90) считался бы годами. Память при этом O(n), это глубина стека.

Факториал: другая история

func factIter(n int) int {
    r := 1
    for i := 2; i <= n; i++ {
        r *= i
    }
    return r
}
// factIter(0) → 1        factIter(1)  → 1
// factIter(5) → 120      factIter(10) → 3628800
// factIter(20) → 2432902008176640000  ← последнее значение, влезающее в int64
// factIter(21) → -4249290049419214848 ← молча переполнилось, без паники и ошибки

Здесь рекурсия не экспоненциальна: каждая подзадача вызывается ровно один раз, всего O(n) вызовов. Разница только в памяти: рекурсия тратит O(n) на стек, итерация обходится O(1). Факториал ломается на другом, на переполнении: 21! уже не влезает в int64, и Go молча вернёт мусор без всякой паники. Правильный ответ на собесе: «до 20 включительно считаю в int64, дальше math/big».

Как это спрашивают на самом деле

Задачу про Фибоначчи почти всегда дают как предлог поговорить про динамическое программирование: «а если нужно посчитать fib(n) mod m?», «а сколькими способами подняться по лестнице, шагая на 1 или 2 ступени?» (это тот же Фибоначчи), «а если шагов может быть до k?» (окно сумм длины k). Отвечать надо не про рекурсию, а про перекрывающиеся подзадачи.

Почему именно эта пара структур

• Мапа даёт поиск по ключу за O(1) в среднем, но не хранит порядок обращений.
• Двусвязный список даёт вставку и удаление произвольного узла за O(1), если у нас уже есть указатель на узел. Односвязного не хватит: чтобы вырезать узел, нужен его предшественник.
• Мапа как раз хранит указатели на узлы — вот он, тот самый «уже есть указатель». Две структуры покрывают слабости друг друга.

Полная реализация

package lru

type node struct {
    key        string
    val        any
    prev, next *node
}

type Cache struct {
    capacity   int
    items      map[string]*node
    head, tail *node // стражи: сами по себе данных не хранят
}

func New(capacity int) *Cache {
    if capacity <= 0 {
        panic("lru: capacity must be positive")
    }
    h, t := &node{}, &node{}
    h.next, t.prev = t, h            // пустой список: head <-> tail
    return &Cache{
        capacity: capacity,
        items:    make(map[string]*node, capacity),
        head:     h,
        tail:     t,
    }
}

// --- примитивы списка: ровно три строки каждый, ни одной проверки на nil ---

func (c *Cache) unlink(n *node) {
    n.prev.next = n.next
    n.next.prev = n.prev
    n.prev, n.next = nil, nil        // помогаем GC и ловим повторное использование
}

func (c *Cache) pushFront(n *node) {
    n.prev = c.head
    n.next = c.head.next
    c.head.next.prev = n
    c.head.next = n
}

func (c *Cache) moveToFront(n *node) {
    c.unlink(n)
    c.pushFront(n)
}

// --- публичный API ---

func (c *Cache) Get(key string) (any, bool) {
    n, ok := c.items[key]
    if !ok {
        return nil, false
    }
    c.moveToFront(n)                 // Get обязан обновлять свежесть
    return n.val, true
}

func (c *Cache) Put(key string, val any) {
    if n, ok := c.items[key]; ok {   // ключ уже есть: обновить значение и порядок
        n.val = val
        c.moveToFront(n)
        return
    }
    if len(c.items) == c.capacity {  // места нет: выселяем самый давний
        victim := c.tail.prev
        c.unlink(victim)
        delete(c.items, victim.key)  // забыть это = утечка памяти
    }
    n := &node{key: key, val: val}
    c.items[key] = n
    c.pushFront(n)
}

func (c *Cache) Len() int { return len(c.items) }

func (c *Cache) Remove(key string) bool {
    n, ok := c.items[key]
    if !ok {
        return false
    }
    c.unlink(n)
    delete(c.items, key)
    return true
}
// c := New(2)
// c.Put("a", 1); c.Put("b", 2)
// c.Get("a")  → 1, true      ← и этим Get освежает "a"
// c.Put("c", 3)              ← места нет, выселяется "b" (самый давний), а не "a"
// c.Get("b")  → <nil>, false
// c.Get("a")  → 1, true
// c.Get("c")  → 3, true
// c.Len() → 2   c.Remove("a") → true   c.Remove("zzz") → false   c.Len() → 1

Разбор по шагам: что происходит на каждой операции

Память O(capacity): по одному узлу на элемент плюс запись в мапе. Никаких проходов по списку нигде нет, поэтому «O(1) на обе операции» тут не преувеличение.

Зачем стражи и что будет без них

Без пустых head/tail каждая операция обрастает проверками: «список пуст?», «удаляем первый?», «удаляем последний?», «остался один элемент?». Это четыре ветки в unlink и три в pushFront — и почти гарантированный баг на собесе под давлением. Со стражами n.prev и n.next никогда не nil у реального узла, поэтому обе функции пишутся в три строки без единого if. Это ровно тот приём, ради которого задачу и дают.

Вариант на container/list

import "container/list"

type entry struct {
    key string
    val any
}

type Cache struct {
    capacity int
    ll       *list.List               // хранит *entry
    items    map[string]*list.Element
}

func (c *Cache) Get(key string) (any, bool) {
    el, ok := c.items[key]
    if !ok {
        return nil, false
    }
    c.ll.MoveToFront(el)
    return el.Value.(*entry).val, true
}

func (c *Cache) Put(key string, val any) {
    if el, ok := c.items[key]; ok {
        el.Value.(*entry).val = val
        c.ll.MoveToFront(el)
        return
    }
    if c.ll.Len() == c.capacity {
        back := c.ll.Back()
        c.ll.Remove(back)
        delete(c.items, back.Value.(*entry).key)
    }
    c.items[key] = c.ll.PushFront(&entry{key: key, val: val})
}

Короче и меньше шансов ошибиться, но интервьюер обычно просит «руками», чтобы посмотреть, понимаешь ли ты, что container/list делает внутри. Стоит написать свою версию, а про container/list упомянуть как «в проде взял бы её или hashicorp/golang-lru». В мапе при этом лежит *list.Element, а ключ дублируется внутри значения: иначе при вытеснении из Back() неоткуда узнать, что удалять из мапы.

Потокобезопасность

type SafeCache struct {
    mu sync.Mutex   // именно Mutex, не RWMutex
    c  *Cache
}

func (s *SafeCache) Get(key string) (any, bool) {
    s.mu.Lock()
    defer s.mu.Unlock()
    return s.c.Get(key)
}

Что ещё спрашивают сверху

• TTL. Добавить expiresAt time.Time в узел и проверять при Get (ленивое истечение) плюс фоновая чистка. Точное истечение по времени требует ещё и кучи по срокам.
• Метрики. hits/misses/evictions покажут, что ты думаешь про наблюдаемость.
• Колбэк на вытеснение onEvict func(key, val), чтобы закрывать ресурсы.
• «А LFU?» Другая структура: счётчики частот плюс списки по частотам (алгоритм O(1) от Ketan Shah). Или приближение через Count-Min Sketch, как в TinyLFU.
• «Почему не просто мапа с временем последнего доступа?» Потому что поиск жертвы станет O(n): придётся перебирать все ключи, чтобы найти минимум.

Вариант 1: куча размера k

import "container/heap"

type minHeap []int

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i] < h[j] }   // мин-куча
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() any {
    old := *h
    n := len(old)
    v := old[n-1]
    *h = old[:n-1]
    return v
}

func kthLargest(nums []int, k int) (int, bool) {
    if k <= 0 || k > len(nums) {
        return 0, false
    }
    h := &minHeap{}
    heap.Init(h)
    for _, v := range nums {
        heap.Push(h, v)
        if h.Len() > k {
            heap.Pop(h)      // выбрасываем самый маленький из k+1
        }
    }
    return (*h)[0], true     // на вершине мин-кучи лежит k-й по величине
}
// kthLargest([]int{3, 2, 1, 5, 6, 4}, 2)          → 5, true
// kthLargest([]int{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4) → 4, true  ← дубликаты считаются
// kthLargest([]int{1}, 5)                         → 0, false

Тут легко запутаться, и это стоит проговорить вслух: для k-го по величине нужна мин-куча. В ней всегда лежат k самых больших элементов, а на вершине оказывается наименьший из них, то есть ровно k-й по величине. Симметрично: k-й наименьший ищут макс-кучей.

Вариант 2: quickselect

// Портит входной слайс, об этом надо предупредить вызывающего.
func kthLargestQS(a []int, k int) int {
    target := len(a) - k               // индекс в порядке по возрастанию
    lo, hi := 0, len(a)-1
    for {
        p := partition(a, lo, hi)
        switch {
        case p == target:
            return a[p]
        case p < target:
            lo = p + 1                 // рекурсия только в одну половину
        default:
            hi = p - 1
        }
    }
}

func partition(a []int, lo, hi int) int {
    r := lo + rand.IntN(hi-lo+1)       // рандомный пивот спасает от O(n^2)
    a[r], a[hi] = a[hi], a[r]
    pivot := a[hi]
    i := lo
    for j := lo; j < hi; j++ {
        if a[j] < pivot {
            a[i], a[j] = a[j], a[i]
            i++
        }
    }
    a[i], a[hi] = a[hi], a[i]
    return i
}
// a := []int{3, 2, 1, 5, 6, 4}
// kthLargestQS(a, 2) → 5 — ответ детерминирован,
// а вот сам a после вызова каждый раз разный: [2 1 3 4 5 6], [3 2 1 4 5 6], [1 2 3 4 5 6],
// [1 2 4 3 5 6]… — восемь прогонов подряд дали четыре разные перестановки.
// Пивот случайный, поэтому перестановки внутри слайса от запуска к запуску не совпадают.

Почему в среднем O(n): после разбиения мы идём только в одну половину, поэтому работа складывается как n + n/2 + n/4 + … = 2n. Худший случай O(n²) наступает, когда пивот всё время оказывается краем, а рандомизация такой сценарий практически исключает. Гарантированный O(n) даёт «median of medians», но на собесе его писать не просят, достаточно назвать.

Добивки

• «Топ-k из миллиарда записей». Куча размера k на каждом шарде, потом слияние k-элементных куч. Ответ уже звучит архитектурно, и его любят.
• «Медиана потока». Две кучи: макс-куча меньшей половины и мин-куча большей, балансируем размеры. Вставка O(log n), медиана O(1).
• «Почему container/heap просит Push/Pop на указателе?» Потому что они меняют длину слайса, а Len/Less/ Swap — нет. Классическая ловушка: определить все пять на значении и получить «куча не растёт».

Три DFS-обхода: разница в одной строке

type Node struct {
    Val         int
    Left, Right *Node
}

func inorder(n *Node, out *[]int) {
    if n == nil {
        return
    }
    inorder(n.Left, out)
    *out = append(*out, n.Val)   // посетить между детьми
    inorder(n.Right, out)
}

func preorder(n *Node, out *[]int) {
    if n == nil {
        return
    }
    *out = append(*out, n.Val)   // посетить до детей
    preorder(n.Left, out)
    preorder(n.Right, out)
}

func postorder(n *Node, out *[]int) {
    if n == nil {
        return
    }
    postorder(n.Left, out)
    postorder(n.Right, out)
    *out = append(*out, n.Val)   // посетить после детей
}
//        1
//       / \
//      2   3          t := &Node{1, &Node{2, &Node{Val: 4}, &Node{Val: 5}}, &Node{Val: 3}}
//     / \
//    4   5
//
// inorder   → [4 2 5 1 3]
// preorder  → [1 2 4 5 3]
// postorder → [4 5 2 3 1]

Зачем каждый из них нужен на практике

• in-order для BST даёт отсортированную последовательность. Отсюда и лучшая проверка «а точно ли это BST»: обходим in-order и смотрим, что каждый следующий строго больше предыдущего.
• pre-order годится для сериализации: запишем его с маркерами nil, и дерево восстановится однозначно.
• post-order освобождает ресурсы и считает всё «снизу вверх»: размер поддерева, высота, суммы. Ребёнок обработан раньше родителя, ровно это и нужно.
• BFS даёт кратчайший путь в невзвешенном графе и всё, что связано с «уровнями»: вид справа, средние по уровням, ширина дерева.

Глубина и BFS по уровням

// Максимальная глубина устроена как post-order:
// сначала считаем детей, потом себя.
func maxDepth(n *Node) int {
    if n == nil {
        return 0
    }
    l, r := maxDepth(n.Left), maxDepth(n.Right)
    return 1 + max(l, r)          // max появился как builtin в Go 1.21
}

// BFS по уровням: отдельный слайс на каждый уровень.
func levelOrder(root *Node) [][]int {
    if root == nil {
        return nil                 // не забыть про пустое дерево
    }
    var res [][]int
    queue := []*Node{root}
    for len(queue) > 0 {
        n := len(queue)            // фиксируем размер уровня до цикла
        level := make([]int, 0, n)
        for i := 0; i < n; i++ {
            cur := queue[0]
            queue = queue[1:]      // на маленьких деревьях приемлемо
            level = append(level, cur.Val)
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
        }
        res = append(res, level)
    }
    return res
}
// На том же дереве (1; 2,3; 4,5):
// maxDepth(t)    → 3        maxDepth(nil)    → 0
// levelOrder(t)  → [[1] [2 3] [4 5]]
// levelOrder(nil) → [] (nil)

Итеративный in-order — на случай «а без рекурсии?»

func inorderIter(root *Node) []int {
    var res []int
    var stack []*Node
    cur := root
    for cur != nil || len(stack) > 0 {
        for cur != nil {           // спускаемся максимально влево
            stack = append(stack, cur)
            cur = cur.Left
        }
        cur = stack[len(stack)-1]  // взяли самый левый непосещённый
        stack = stack[:len(stack)-1]
        res = append(res, cur.Val)
        cur = cur.Right            // и переключились на правое поддерево
    }
    return res
}
// inorderIter(t)   → [4 2 5 1 3]  — ровно то же, что и рекурсия
// inorderIter(nil) → [] (nil)

Смысл ровно тот же, что у рекурсии, только стек вызовов мы держим руками. Это честный ответ на «а если дерево глубиной миллион и стек переполнится». Правда, в Go горутинный стек растёт динамически до maxstacksize (1 ГБ на 64-битных), так что практически рекурсия выдерживает очень глубокие деревья.

Здесь h означает высоту дерева (для сбалансированного O(log n), для вырожденного O(n)), w — максимальную ширину уровня, у полного дерева это примерно n/2. Отсюда вывод, который на собесе звучит неожиданно: BFS на широком дереве съедает больше памяти, чем DFS, хотя интуиция часто говорит обратное.

Добивки

• «Проверь, что это BST». Критерий «левый ребёнок меньше родителя» тут неверен. Нужен либо in-order с проверкой возрастания, либо рекурсия с передачей диапазона (min, max) вниз.
• «Найди наименьшего общего предка (LCA)». В BST спускаемся от корня, пока оба значения по одну сторону; в обычном дереве идём post-order и возвращаем «нашёл кого-то из двух».
• «Сериализуй и десериализуй дерево». pre-order с явными # вместо nil; обратно читаем поток тем же порядком.

Базовая версия

type ListNode struct {
    Val  int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {   // оба условия обязательны
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false                            // дошли до nil, цикла нет
}
// 1→2→3→4→2 (хвост замкнут на второй узел):  hasCycle(head) → true
// 1→2→3     (обычный список):                hasCycle(head) → false
// hasCycle(nil)                                              → false

Вход в цикл и его длина

// Возвращает узел-вход в цикл и длину цикла; (nil, 0) если цикла нет.
func detectCycle(head *ListNode) (*ListNode, int) {
    slow, fast := head, head
    met := false
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
        if slow == fast {
            met = true
            break
        }
    }
    if !met {
        return nil, 0
    }

    // Длина цикла: крутим один указатель до возврата в точку встречи.
    length := 1
    for p := slow.Next; p != slow; p = p.Next {
        length++
    }

    // Вход: один из головы, второй с места встречи, оба по одному шагу.
    p := head
    for p != slow {
        p, slow = p.Next, slow.Next
    }
    return p, length
}
// Список 1→2→3→4→ back to 2:
// detectCycle(head) → узел со значением 2, длина цикла 3
// Список 1→2 без цикла:
// detectCycle(head) → nil, 0

Альтернатива «мапой» и почему она хуже

func hasCycleMap(head *ListNode) bool {
    seen := make(map[*ListNode]struct{})
    for n := head; n != nil; n = n.Next {
        if _, ok := seen[n]; ok {
            return true
        }
        seen[n] = struct{}{}
    }
    return false
}
// 1→2→3→ back to 2:  hasCycleMap(head) → true
// 1 (один узел):     hasCycleMap(head) → false
// hasCycleMap(nil)                     → false

Работает и пишется за 30 секунд, но это O(n) памяти против O(1) у Флойда. На собесе такое решение стоит назвать первым («в лоб можно мапой указателей, O(n) памяти») и сразу предложить улучшение до O(1). Интервьюеру нравится именно эта последовательность: сначала рабочее, потом оптимальное.

Где это встречается за пределами литкода

Тот же алгоритм (он же «cycle detection») ищет период в псевдослучайных последовательностях, работает в ро-методе Полларда для факторизации и ловит зацикливание, когда разворачиваются символические ссылки или редиректы — везде, где состояние нельзя запомнить целиком, но можно шагать по нему дважды с разной скоростью. Одна фраза про это заметно поднимает впечатление от ответа.

Добивки

• «Найди середину списка». Тот же приём: когда быстрый дошёл до конца, медленный ровно посередине.
• «Найди k-й с конца за один проход». Разнести указатели на k и двигать вместе.
• «Пересекаются ли два списка?» Два указателя, каждый после конца своего списка перепрыгивает на голову чужого; встретятся они в точке пересечения или оба в nil.

Наглядно: одна и та же строка тремя способами

s := "привет"

fmt.Println(len(s))                    // 12  — это байты, не символы
fmt.Println(utf8.RuneCountInString(s)) // 6   — вот это символы
fmt.Println(len([]rune(s)))            // 6   — то же, но с аллокацией

fmt.Printf("%c %T\n", s[0], s[0])      // Ð uint8 — половинка буквы «п».
                                       // Именно uint8: byte — это псевдоним, %T печатает базовый тип
for i, r := range s {
    fmt.Printf("%d:%c ", i, r)         // 0:п 2:р 4:и 6:в 8:е 10:т
}                                      // индексы прыгают через 2, это байтовые смещения

Классические задачи и правильные решения

// 1) Развернуть строку. Наивное s[len(s)-1-i] сломает UTF-8.
func reverse(s string) string {
    r := []rune(s)                       // одна аллокация, зато корректно
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        r[i], r[j] = r[j], r[i]
    }
    return string(r)
}

// 2) Палиндром без аллокации: два указателя по рунам через DecodeRuneInString.
func isPalindrome(s string) bool {
    for len(s) > 0 {
        r1, size1 := utf8.DecodeRuneInString(s)
        r2, size2 := utf8.DecodeLastRuneInString(s)
        if unicode.ToLower(r1) != unicode.ToLower(r2) {
            return false
        }
        if len(s) == size1 {             // осталась одна руна, центр
            break
        }
        s = s[size1 : len(s)-size2]
    }
    return true
}

// 3) Частоты символов. Ключ обязательно rune, не byte.
func freq(s string) map[rune]int {
    m := make(map[rune]int)
    for _, r := range s {                // range сам декодирует
        m[r]++
    }
    return m
}

// 4) Обрезать строку до N символов, а не байт. Типичная задача «превью».
func truncate(s string, n int) string {
    if utf8.RuneCountInString(s) <= n {
        return s
    }
    cnt := 0
    for i := range s {                   // i — байтовое смещение начала руны
        if cnt == n {
            return s[:i]                 // режем строго по границе руны
        }
        cnt++
    }
    return s
}
// reverse("привет, Go!")   → "!oG ,тевирп"
// isPalindrome("шАлаШ")    → true    ← ToLower внутри, регистр не мешает
// isPalindrome("привет")   → false
// isPalindrome("А роза упала на лапу Азора") → false — пробелы и заглавные эта функция
//                                             не чистит, для них нужен вариант с фильтром
// freq("абба")             → map[1072:2 1073:2]  ← ключи-руны печатаются числами
// truncate("привет, мир", 6) → "привет"
// truncate("go", 6)          → "go"
// truncate("привет", 0)      → ""

Добивки

• «Сколько памяти займёт []rune(s)?» 4 байта на руну (rune = int32), то есть для ASCII-строки выйдет вчетверо больше исходной.
• «Что будет при конвертации невалидного UTF-8 в []rune?» Каждый невалидный байт превратится в U+FFFD (replacement character), паники не будет.
• «Строка в Go — это что в памяти?» Двухсловный заголовок: {ptr *byte, len int}, 16 байт на 64-битной платформе. Подстрока s[a:b] не копирует байты, а делает новый заголовок на тот же массив, отсюда, кстати, и эффект «маленькая подстрока удерживает в памяти большой буфер».
• «Почему строки неизменяемы?» Это позволяет свободно копировать заголовок, класть строки в ключи мапы и не бояться гонок при передаче между горутинами.

Полная реализация: собрать все результаты и все ошибки

type Job struct {
    ID  int
    Arg string
}

type Result struct {
    JobID int
    Val   string
    Err   error
}

// Pool обрабатывает jobs не более чем workers горутинами.
// Возвращает результаты в порядке завершения и объединённую ошибку.
func Pool(
    ctx context.Context,
    jobs []Job,
    workers int,
    do func(context.Context, Job) (string, error),
) ([]Result, error) {

    if workers <= 0 {
        workers = 1
    }
    if workers > len(jobs) {
        workers = len(jobs)          // не плодим горутины без работы
    }
    if len(jobs) == 0 {
        return nil, nil              // ранний выход: без задач и работать не над чем
    }

    tasks := make(chan Job)
    results := make(chan Result)

    var wg sync.WaitGroup
    wg.Add(workers)
    for i := 0; i < workers; i++ {
        go func() {
            defer wg.Done()
            for j := range tasks {
                val, err := do(ctx, j)
                select {
                case results <- Result{JobID: j.ID, Val: val, Err: err}:
                case <-ctx.Done():
                    return           // читателя больше нет — уходим, а не виснем
                }
            }
        }()
    }

    // Продюсер: единственный писатель в tasks, поэтому закрывает его сам.
    go func() {
        defer close(tasks)
        for _, j := range jobs {
            select {
            case tasks <- j:
            case <-ctx.Done():
                return
            }
        }
    }()

    // Сторож: писателей в results много, закрыть должен кто-то один.
    go func() {
        wg.Wait()
        close(results)
    }()

    out := make([]Result, 0, len(jobs))
    var errs []error
    for r := range results {         // дочитываем до конца, иначе утекут горутины
        out = append(out, r)
        if r.Err != nil {
            errs = append(errs, fmt.Errorf("job %d: %w", r.JobID, r.Err))
        }
    }
    if err := ctx.Err(); err != nil {
        errs = append(errs, err)     // отменили на середине, это тоже результат
    }
    return out, errors.Join(errs...) // Join вернёт nil, если errs пуст
}
// jobs = 5 штук, workers = 3, третья задача возвращает ошибку.
// Характерный прогон:
//   {3  сломался}
//   {2 B <nil>}
//   {1 A <nil>}
//   {5 E <nil>}
//   {4 "D" <nil>}
//   err: job 3: сломался
// Порядок строк меняется от запуска к запуску, это результаты в порядке завершения.
// Стабильно только одно: все 5 результатов на месте и err не nil.

Вариант «fail-fast»: первая ошибка отменяет остальное

Меняется ровно одна вещь: заводим производный ctx с cancel и дёргаем его на первой ошибке. Воркеры увидят отмену в своём select и в do(ctx, ...), продюсер перестанет подавать задачи.

func PoolFailFast(ctx context.Context, jobs []Job, workers int,
    do func(context.Context, Job) (string, error)) ([]Result, error) {

    ctx, cancel := context.WithCancel(ctx)
    defer cancel()                   // иначе утечёт сам context

    // ... тот же запуск воркеров и продюсера с новым ctx ...

    var out []Result
    var firstErr error
    for r := range results {
        if r.Err != nil && firstErr == nil {
            firstErr = r.Err
            cancel()                 // сигнал всем остальным: сворачиваемся
            continue                 // но канал дочитываем до конца
        }
        out = append(out, r)
    }
    return out, firstErr
}

Если нужен порядок результатов — не сортируй, пиши по индексу

// Результаты строго в порядке входного слайса, без канала результатов вообще.
out := make([]Result, len(jobs))     // длина фиксирована, реаллокаций не будет
var wg sync.WaitGroup
sem := make(chan struct{}, workers)  // ограничитель параллельности

for i, j := range jobs {
    wg.Add(1)
    go func(i int, j Job) {          // до Go 1.22 параметры обязательны
        defer wg.Done()
        sem <- struct{}{}
        defer func() { <-sem }()
        val, err := do(ctx, j)
        out[i] = Result{JobID: j.ID, Val: val, Err: err}  // свой слот, гонки нет
    }(i, j)
}
wg.Wait()
// Те же 5 задач и 3 воркера, но результат теперь детерминирован по порядку:
// [{1 A <nil>} {2 B <nil>} {3  сломался} {4 D <nil>} {5 E <nil>}]
// Сколько раз ни запусти, порядок тот же: каждый пишет в свой out[i].

Запись в out[i] из разных горутин безопасна: элементы слайса не пересекаются в памяти, а сам заголовок слайса никто не меняет (длина зафиксирована при make). Это одно из немногих мест, где «общая переменная без мьютекса» работает корректно, и объяснить это вслух дорогого стоит. И ни одного append: он меняет заголовок и превращает всё в гонку.

Где обычно ошибаются

• wg.Add(1) внутри горутины. Планировщик может не успеть запустить горутину до wg.Wait(), и Wait вернётся на пустом счётчике. Add всегда зови в вызывающей горутине, до go.
• Забыт ранний выход при len(jobs) == 0. Тогда workers = 0, wg.Wait() возвращается сразу, канал закрывается, так что тут всё сойдётся. А вот если workers не обрезали и он отрицательный, wg.Add паникует: sync: negative WaitGroup counter. А при нуле воркеров функция молча вернёт пустой результат, и продюсер повиснет навсегда. Границы проверить всё равно придётся.
• Общая переменная err вместо канала. if err != nil { globalErr = err } из нескольких горутин даёт гонку, которую -race поймает мгновенно. Ошибка должна ехать как поле результата.
• defer cancel() забыт в fail-fast варианте. context.WithCancel регистрирует дочерний контекст у родителя; без cancel он висит там до завершения родителя. go vet это ловит (lostcancel).
• Буферизованный results «чтобы не блокировались». Это маскировка проблемы, а не решение. Буфер размера len(jobs) действительно уберёт блокировку, но съест память и спрячет то, что select с ctx не написан. Интервьюер это заметит.

Добивки, которые задаст интервьюер

• «А если задачи приходят потоком, а не слайсом?» Сигнатура меняется на jobs <-chan Job, продюсер не нужен вообще — воркеры читают внешний канал напрямую. Закрывать его будет вызывающий, а мы просто выйдем из range.
• «Как ограничить не число воркеров, а RPS?» Это уже rate limiter, а не pool: добавляем <-limiter.C перед вызовом do. Пул ограничивает одновременность, лимитер бьёт по частоте. Оси разные, и путают их постоянно: типичная ошибка проектирования.
• «Что если воркер паникует?» Без recover падает весь процесс. В воркере ставим defer func(){ if r := recover(); r != nil { results <- Result{Err: fmt.Errorf("panic: %v", r)} } }() — и обязательно тоже под select с ctx, иначе паника превратится в утечку.
• «Сколько воркеров брать?» Для CPU-bound бери runtime.GOMAXPROCS(0). Для IO-bound сильно больше, ограничение диктует не CPU, а внешний ресурс: пул соединений БД, лимит стороннего API. Ответ «зависит от того, во что упирается задача» лучше любого числа.
• «Как протестируешь, что горутины не текут?» go.uber.org/goleak в TestMain, плюс go test -race. Ещё можно сравнить runtime.NumGoroutine() до и после с небольшим ожиданием.
• «Перепиши на errgroup». g, ctx := errgroup.WithContext(ctx), g.SetLimit(workers), в цикле g.Go(...), в конце g.Wait(). Он даст ровно fail-fast семантику и первую ошибку.

Каноническая реализация

// Merge сливает произвольное число входных каналов в один.
// Закрывается, когда закрылись все входы. Отмена ctx спасает пишущего,
// но не читающего: range по входу отмену не видит.
func Merge[T any](ctx context.Context, ins ...<-chan T) <-chan T {
    out := make(chan T)

    var wg sync.WaitGroup
    wg.Add(len(ins))

    for _, in := range ins {
        go func(in <-chan T) {       // параметр нужен до Go 1.22
            defer wg.Done()
            for v := range in {      // выходим, когда вход закрыт
                select {
                case out <- v:
                case <-ctx.Done():   // читатель ушёл, не виснем
                    return
                }
            }
        }(in)
    }

    go func() {                      // единственный, кто имеет право на close
        wg.Wait()
        close(out)
    }()

    return out
}
// Merge(ctx, src(1,2,3), src(10,20,30), src(100,200)) — шесть прогонов подряд:
//   1 2 100 10 3 20 200 30
//   1 10 100 2 20 200 3 30
//   10 100 1 20 200 2 30 3
//   1 2 10 100 3 20 200 30
//   100 10 1 200 20 2 30 3
//   1 2 100 3 10 200 20 30
// Гарантируется только состав (все 8 значений) и порядок внутри каждого входа.
// Как входы чередуются между собой, решает планировщик.

Возвращаем <-chan T, а не chan T. Это не косметика: направленный тип на уровне компилятора запрещает вызывающему писать в канал и закрывать его. Половина проблем с «кто закрыл канал» решается именно типом. Скажи это вслух: деталь уровня «писал такое в проде».

Вариант без горутины на канал: reflect.Select

Если N известно только в рантайме и горутин жалко, есть reflect.Select — он делает динамический select по слайсу SelectCase. Одна горутина вместо N. На собесе это отличная «добивка сверху», но в проде почти не нужна: горутина стоит ~2–8 КБ стека, а рефлексия обходится примерно вдвое дороже на каждой операции.

func MergeReflect[T any](ins ...<-chan T) <-chan T {
    out := make(chan T)
    go func() {
        defer close(out)
        cases := make([]reflect.SelectCase, len(ins))
        for i, in := range ins {
            cases[i] = reflect.SelectCase{
                Dir:  reflect.SelectRecv,
                Chan: reflect.ValueOf(in),
            }
        }
        for len(cases) > 0 {
            i, v, ok := reflect.Select(cases)
            if !ok {                          // канал закрыт, убираем из набора
                cases = append(cases[:i], cases[i+1:]...)
                continue
            }
            out <- v.Interface().(T)
        }
    }()
    return out
}

Без строки, которая удаляет кейс, закрытый канал будет отдавать нулевое значение с ok == false в бесконечном цикле и займёт ядро на 100%. Это классическая ловушка select по закрытому каналу, и в статическом select она лечится присваиванием ch = nil: nil-канал в select блокируется навсегда и тем самым «выключает» ветку. Приём с ch = nil стоит назвать, даже если тебя не спрашивали: он выдаёт человека, который писал реальные pipeline.

Где обычно ошибаются

• close(out) внутри горутины-читателя входа. Первая же закрывшаяся ветка закроет общий канал, остальные упадут с паникой на записи.
• defer close(out) в Merge напрямую. Функция возвращает управление сразу, канал закроется до того, как что-то в него попадёт.
• Нет select с ctx.Done() на записи. Работает, пока потребитель читает всё. Как только он выходит по первому найденному элементу — N горутин зависают навсегда. Это самая частая утечка в реальных кодовых базах.
• Захват in без параметра до Go 1.22. Все горутины читают последний канал, остальные не читает никто: данные оттуда пропадают, а -race ещё и показывает гонку на самой переменной цикла.
• Ожидание порядка. Fan-in ничего не гарантирует про порядок. Нужен порядок, значит это уже не fan-in, а слияние с приоритетом (куча по ключу) или нумерация элементов.

Добивки, которые задаст интервьюер

• «А если один вход завис навсегда и не закрывается?» Merge никогда не закроет out. И ctx с таймаутом тут не поможет, пока приём не обёрнут в select: горутина стоит в range и отмену не видит. Признать эту зависимость важнее, чем героически её обходить.
• «Как сделать fan-out обратно?» Fan-out получается, когда N горутин читают из одного канала (ровно наш worker pool). Симметрия «fan-out → работа → fan-in» и есть базовый конкурентный паттерн Go.
• «Что если входов тысячи?» Тысячу горутин рантайм переварит (несколько мегабайт), но на десятках тысяч уже стоит подумать про reflect.Select или про иерархическое слияние: сливать по 8 каналов в дерево глубины log₈ N.
• «Сделай так, чтобы out закрывался при отмене ctx». В этом виде не закроется: ctx.Done() стоит только в ветке записи, а горутина висит на range in и отмену не видит. Чтобы закрывался, приём тоже надо развернуть в select с ctx.Done() — вот тогда wg.Wait() вернётся и сторож закроет канал.
• «Зачем возвращать <-chan, а не chan?» Компилятор запретит вызывающему писать и закрывать. Владение выражено типом, а не комментарием.

Минимальная версия, которую пишут на доске

sem := make(chan struct{}, K)        // ёмкость = число разрешений

for _, u := range urls {
    wg.Add(1)
    go func(u string) {
        defer wg.Done()
        sem <- struct{}{}            // Acquire: блокируется, когда занято K мест
        defer func() { <-sem }()     // Release строго через defer
        call(u)
    }(u)
}
wg.Wait()

struct{}{}, а не bool: пустая структура занимает ноль байт, и весь буфер канала на K разрешений не стоит ничего. Это мелочь, но её замечают.

Нормальный семафор: с context, TryAcquire и весами

type Semaphore chan struct{}

func NewSemaphore(n int) Semaphore { return make(Semaphore, n) }

// Acquire ждёт свободный слот или отмены контекста.
func (s Semaphore) Acquire(ctx context.Context) error {
    select {
    case s <- struct{}{}:
        return nil
    case <-ctx.Done():
        return ctx.Err()             // слот не занят, Release звать нельзя
    }
}

// TryAcquire не ждёт: либо взял, либо сразу false.
func (s Semaphore) TryAcquire() bool {
    select {
    case s <- struct{}{}:
        return true
    default:                         // default делает select неблокирующим
        return false
    }
}

func (s Semaphore) Release() { <-s }

// Занято прямо сейчас / всего слотов.
func (s Semaphore) InUse() int { return len(s) }
func (s Semaphore) Cap() int   { return cap(s) }

Как это выглядит в реальном клиенте внешнего API

type Client struct {
    http *http.Client
    sem  Semaphore                   // не более K одновременных запросов
}

func (c *Client) Get(ctx context.Context, url string) (*Response, error) {
    if err := c.sem.Acquire(ctx); err != nil {
        return nil, fmt.Errorf("ожидание слота: %w", err)
    }
    defer c.sem.Release()            // defer сразу после успешного Acquire, иначе утечёт слот

    req, err := http.NewRequestWithContext(ctx, http.MethodGet, url, nil)
    if err != nil {
        return nil, err
    }
    resp, err := c.http.Do(req)
    ...
}

Семафор vs worker pool — в чём реально разница

Последнюю строку спрашивают чаще всего, и она же самая важная. Если задач миллион и ты пишешь go на каждую, семафор ограничит одновременные вызовы API, но не спасёт от миллиона горутин, ждущих в очереди. Память улетит. Тут нужен именно пул: он создаёт обратное давление на продюсера через небуферизованный канал.

Где обычно ошибаются

• Release не через defer. Любой ранний return или паника — и слот потерян навсегда. Через несколько ошибок пропускная способность падает до нуля, и программа «зависает» без единой явной блокировки.
• Acquire без context. Тогда при перегрузке внешнего API горутины будут ждать вечно, и отменить их нечем.
• Release после неуспешного Acquire. Семафор начинает пропускать больше K.
• len(sem) для проверки «есть ли место» перед записью. Классический check-then-act: между проверкой и записью состояние изменится. Правильно и неблокирующе это делает select с default.
• Путать семафор с rate limiter. Семафор ограничивает сколько одновременно, лимитер считает, сколько в секунду. Если API говорит «100 rps», семафор на 100 не даст гарантии: при времени ответа 10 мс это будет 10 000 rps.

Добивки, которые задаст интервьюер

• «Сделай взвешенный семафор» (одна задача занимает n слотов). На канале это неудобно: Acquire(n) по n записей не атомарен и даёт дедлоки при конкуренции. Нужен sync.Cond или готовый golang.org/x/sync/semaphore.Weighted — внутри у него мьютекс и список ожидающих.
• «Справедлив ли такой семафор?» Нет. Go не гарантирует FIFO среди горутин, заблокированных на канале — на практике планировщик обслуживает их близко к FIFO, но это деталь реализации, а не контракт. Нужна честность, заводи очередь заявок явно.
• «Как узнать текущую загрузку?» len(sem) покажет занятые слоты, cap(sem) все. Годится для метрики, не годится для решения (гонка).
• «Можно ли то же самое одной строкой?» errgroup.Group.SetLimit(K), внутри у него такой же буферизованный канал.
• «Что если K нужно менять на лету?» Ёмкость канала неизменна. Либо пересоздавать семафор под мьютексом, либо переходить на sync.Cond с обычным счётчиком.

Полный рабочий pipeline

// Стадия 1: генератор. Единственная стадия без входного канала.
func gen(ctx context.Context, nums ...int) <-chan int {
    out := make(chan int)
    go func() {
        defer close(out)             // владелец канала закрывает его сам
        for _, n := range nums {
            select {
            case out <- n:
            case <-ctx.Done():
                return               // defer всё равно закроет out
            }
        }
    }()
    return out
}

// Стадия 2: фильтр. Сигнатура один-в-один как у любой другой стадии.
func filter(ctx context.Context, in <-chan int, pred func(int) bool) <-chan int {
    out := make(chan int)
    go func() {
        defer close(out)
        for v := range in {          // каскад: закрылся вход, вышли
            if !pred(v) {
                continue
            }
            select {
            case out <- v:
            case <-ctx.Done():
                return
            }
        }
    }()
    return out
}

// Стадия 3: трансформация.
func mapStage[T, R any](ctx context.Context, in <-chan T, f func(T) R) <-chan R {
    out := make(chan R)
    go func() {
        defer close(out)
        for v := range in {
            select {
            case out <- f(v):
            case <-ctx.Done():
                return
            }
        }
    }()
    return out
}

// Сборка: стадии просто вкладываются друг в друга.
func main() {
    ctx, cancel := context.WithCancel(context.Background())
    defer cancel()

    nums := gen(ctx, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    even := filter(ctx, nums, func(n int) bool { return n%2 == 0 })
    sq   := mapStage(ctx, even, func(n int) int { return n * n })

    for v := range sq {
        fmt.Println(v)               // 4, потом 16, потом 36; на 36 сработает break
        if v > 30 {
            cancel()                 // уходим раньше: отменяем все стадии
            break
        }
    }
    // После cancel() каждая стадия выйдет по ctx.Done() и закроет свой out.
}

// вывод, ровно три строки:
// 4
// 16
// 36
// Стадии умеют выдать 4 16 36 64 100, но потребитель уходит на первом же значении > 30.
// 64 и 100 не напечатаются никогда, и поэтому нужен ctx: без него
// три горутины навсегда зависли бы на записи в канал, который больше никто не читает.

Три свойства, которые делают это правильным pipeline

1. Каждая стадия владеет только своим выходным каналом. Она его создаёт, пишет в него и закрывает. Входной канал она только читает и никогда не закрывает. Поэтому завершение идёт само: закрылся вход — вышел range — сработал defer close(out) — закрылся выход следующей стадии, и так до конца.
2. Однородная сигнатура. func(ctx, <-chan In, ...) <-chan Out. Стадии свободно складываются друг с другом: их можно переставлять, добавлять, оборачивать в Merge, чтобы распараллелить одну стадию.
3. ctx в каждой стадии. Каскад закрытия работает слева направо, но останавливаться досрочно приходится справа налево — потребитель решил, что хватит. Канала данных для этого нет, нужен отдельный сигнал: ctx (раньше писали done chan struct{}: та же идея, только ctx удобнее).

Параллельная стадия: fan-out + fan-in внутри pipeline

Если одна стадия стала узким местом (например, ходит в сеть), её распараллеливают, не ломая сигнатуру: запускаем M копий стадии на одном входе и сливаем их выходы через Merge из предыдущего вопроса.

func parallel[T, R any](ctx context.Context, in <-chan T, m int, f func(T) R) <-chan R {
    outs := make([]<-chan R, m)
    for i := 0; i < m; i++ {
        outs[i] = mapStage(ctx, in, f)   // все M читают один in: это fan-out
    }
    return Merge(ctx, outs...)           // и сливаются обратно: это fan-in
}

Порядок элементов после такой стадии теряется. Если он важен, либо не распараллеливай стадию, либо тащи порядковый номер внутри элемента и пересобирай на выходе.

Где обычно ошибаются

• Стадия закрывает входной канал. Предыдущая стадия тут же паникует на записи. Правило: закрываю только то, что создал.
• close(out) не через defer, а в конце горутины. Любой ранний return (по ctx, по ошибке) оставит канал незакрытым, и следующая стадия зависнет в range навсегда.
• Общий буферизованный канал «на всякий случай». Буфер сдвигает момент блокировки, но утечку не убирает — она просто проявится на другом объёме данных.
• cancel() без дренажа. Технически стадии выйдут сами, но если стадия держит ресурс (открытый файл, соединение), освобождать его надо в defer той же горутины, а не надеяться на GC.
• Ошибки некуда девать. Стадия возвращает один канал значений, а error деть некуда. Решения два: канал struct{ Val T; Err error } (просто, работает) или отдельный errCh (сложнее в завершении). На собесе назови первый.

Добивки, которые задаст интервьюер

• «Как передать ошибку через pipeline?» Тип элемента становится Result[T]{Val T; Err error}. Стадии пропускают элементы с ошибкой дальше без обработки, и ошибка доезжает до потребителя, не ломая структуру.
• «Зачем done chan struct{}, если есть context?» Это исторический вариант из статьи «Go Concurrency Patterns: Pipelines» (2014), написанной до появления context в стандартной библиотеке. Механика идентична: закрытый канал делает <-done мгновенно готовым для всех читателей. context добавляет к этому дедлайны, значения и иерархию отмены.
• «Сколько буферизовать между стадиями?» По умолчанию ноль. Буфер имеет смысл, если стадии неравномерны по времени и есть всплески: он сглаживает jitter. Но буфер = задержка в очереди и память; размер подбирай замером, а не на глаз.
• «Что если стадия должна отдавать несколько элементов на один входной?» Ничего не меняется — просто for внутри for, каждая запись под select. Число элементов на входе и выходе стадии никак не связано.
• «Как это тестировать?» Стадия работает как чистая функция от канала к каналу: подаёшь на вход закрытый канал с известными значениями, читаешь выход в слайс, сравниваешь. Плюс тест на отмену: cancel() сразу, проверяешь, что выходной канал закрылся, и goleak в TestMain.

Шаг 1. Базовый вариант: map + Mutex

type Cache[K comparable, V any] struct {
    mu sync.Mutex
    m  map[K]V
}

func New[K comparable, V any]() *Cache[K, V] {
    return &Cache[K, V]{m: make(map[K]V)}
}

func (c *Cache[K, V]) Get(k K) (V, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()
    v, ok := c.m[k]
    return v, ok
}

func (c *Cache[K, V]) Set(k K, v V) {
    c.mu.Lock()
    defer c.mu.Unlock()
    c.m[k] = v
}

func (c *Cache[K, V]) Delete(k K) {
    c.mu.Lock()
    defer c.mu.Unlock()
    delete(c.m, k)
}

// GetOrSet: атомарно «прочитать, а если нет, записать».
// Без неё кэш неправильный: Get+Set снаружи не атомарны.
func (c *Cache[K, V]) GetOrSet(k K, v V) (V, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if old, ok := c.m[k]; ok {
        return old, true             // true = уже было
    }
    c.m[k] = v
    return v, false
}
// c := New[string, int]()
// c.Get("a")          → 0, false
// c.Set("a", 1)
// c.Get("a")          → 1, true
// c.GetOrSet("a", 99) → 1, true    ← 99 не записалось, вернулось старое
// c.GetOrSet("b", 2)  → 2, false   ← false = «положили новое»
// c.Delete("a"); c.Get("a") → 0, false

Шаг 2. RWMutex — и почему он не бесплатный

type RWCache[K comparable, V any] struct {
    mu sync.RWMutex
    m  map[K]V
}

func (c *RWCache[K, V]) Get(k K) (V, bool) {
    c.mu.RLock()                     // много читателей одновременно
    defer c.mu.RUnlock()
    v, ok := c.m[k]
    return v, ok
}

func (c *RWCache[K, V]) Set(k K, v V) {
    c.mu.Lock()                      // писатель один
    defer c.mu.Unlock()
    c.m[k] = v
}

Интуиция «читателей много, значит RWMutex быстрее» верна не всегда. RLock атомарно инкрементит общий счётчик читателей, то есть пишет в одну и ту же кэш-линию из всех ядер. Получается cache line contention: строка постоянно перегоняется между ядрами в состоянии Modified. Если критическая секция короткая (а m[k] укладывается в десятки наносекунд), накладные расходы на этот пинг-понг сопоставимы с самой работой, и RWMutex проигрывает обычному Mutex.

Отвечай на собесе не «RWMutex быстрее», а «надо померить бенчмарком с -cpu=1,2,4,8, потому что выигрыш зависит от длины критической секции и числа ядер; для однострочного чтения из мапы я бы по умолчанию оставил обычный Mutex». Это отличает человека, который читал про RWMutex, от человека, который его профилировал.

Шаг 3. sync.Map — ровно два сценария

var m sync.Map                       // нулевое значение готово к работе

m.Store("k", 42)
v, ok := m.Load("k")                 // v имеет тип any, нужен type assertion
actual, loaded := m.LoadOrStore("k", 100)  // атомарный GetOrSet
m.Delete("k")
m.Range(func(k, v any) bool {        // снимок, не консистентный срез
    return true                      // false прерывает обход
})
// Что напечатает такая последовательность:
// m.Load("k")            → 42, true
// m.LoadOrStore("k", 100) → 42, true   ← ключ уже есть, 100 не записалось
// после m.Delete("k"):
// m.Load("k")            → <nil>, false

До Go 1.24 внутри sync.Map лежали две мапы: read (атомарная, только на чтение) и dirty под мьютексом, а промахи по первой копили счётчик, после которого вторая «повышалась» в первую. С Go 1.24 внутри другое — HashTrieMap, дерево из атомарно подменяемых узлов, — но профиль применимости остался прежним:

• Выигрывает: ключ записали один раз и потом читают миллионы раз (реестры, метаданные, конфиг). Или так: разные горутины работают с непересекающимися наборами ключей — тогда contention неоткуда взяться.
• Проигрывает: частые записи новых ключей — каждая идёт в dirty под дерева, а не в общий кэш. В одну горутину sync.Map вдвое медленнее обычной мапы под мьютексом — там нет конкуренции, и платить за неё незачем.
• Минусы по эргономике: ключ и значение имеют тип any, то есть interface{}-боксинг, аллокации и приведение типов на каждом обращении; нет Len(); Range не даёт консистентного снимка.

Готовая формулировка: «sync.Map не "быстрая мапа", а структура под конкретный профиль. В документации так и написано: она оптимизирована под append-only и под disjoint key sets. Во всех остальных случаях я беру обычную мапу под мьютексом, а если упираюсь в блокировку — шардирую.»

Шаг 4. Шардирование — то, ради чего задавался весь вопрос

const shards = 256                   // степень двойки: маска вместо деления

type shard[K comparable, V any] struct {
    mu sync.RWMutex
    m  map[K]V
    _  [32]byte                      // padding до 64 байт: шарды не делят кэш-линию
}

type Sharded[K comparable, V any] struct {
    s    [shards]*shard[K, V]
    hash func(K) uint64
}

func NewSharded[K comparable, V any](hash func(K) uint64) *Sharded[K, V] {
    c := &Sharded[K, V]{hash: hash}
    for i := range c.s {
        c.s[i] = &shard[K, V]{m: make(map[K]V)}
    }
    return c
}

func (c *Sharded[K, V]) shardFor(k K) *shard[K, V] {
    return c.s[c.hash(k)&(shards-1)]  // & вместо %: маска дешевле деления
}

func (c *Sharded[K, V]) Get(k K) (V, bool) {
    sh := c.shardFor(k)
    sh.mu.RLock()
    defer sh.mu.RUnlock()
    v, ok := sh.m[k]
    return v, ok
}

func (c *Sharded[K, V]) Set(k K, v V) {
    sh := c.shardFor(k)
    sh.mu.Lock()
    defer sh.mu.Unlock()
    sh.m[k] = v
}

// Len приходится собирать по всем шардам, и срез не атомарный.
func (c *Sharded[K, V]) Len() int {
    n := 0
    for _, sh := range c.s {
        sh.mu.RLock()
        n += len(sh.m)
        sh.mu.RUnlock()
    }
    return n
}

Сводная таблица: когда что выигрывает

Где обычно ошибаются

• Нет атомарного GetOrSet. Самая частая содержательная ошибка: кэш безопасен, а пользоваться им небезопасно.
• defer забыт при раннем return. Мьютекс остаётся захваченным навсегда, и следующая же операция вешает всю программу.
• Возврат внутреннего значения по ссылке. Если под V прячется *User, []byte или мапа, вызывающий получит доступ к тем же данным и изменит их вне мьютекса. Либо возвращать копию, либо документировать «значение read-only».
• Мьютекс копируется вместе со структурой. Методы обязаны быть на указателе *Cache; при значении go vet ругнётся, а копия получит свой собственный мьютекс и всю защиту потеряет.
• RWMutex «на всякий случай». Без бенчмарка это карго-культ; часто медленнее обычного мьютекса.
• Шардирование по len(key) или первой букве. Неравномерный хеш даёт горячие шарды, и вся затея теряет смысл. Нужен нормальный хеш: maphash, xxhash, fnv. Короче всего maphash.Comparable(seed, key): дженерик-функция, хеширующая любой сравнимый ключ в uint64, без ручной сериализации в байты. В Go 1.27 в том же пакете появились maphash.Hasher и ComparableHasher — пара «хеш + равенство» для случаев, когда своей хеш-таблице нужно нестандартное сравнение ключей (например, строки без учёта регистра).
• Вытеснения нет. Кэш без TTL и без ограничения размера течёт, просто не сразу. Спроси у интервьюера про политику вытеснения сам, до того как спросят тебя.

Добивки, которые задаст интервьюер

• «Добавь TTL». Хранить struct{ val V; exp time.Time }, проверять срок на чтении (ленивое вытеснение) плюс фоновый time.Ticker, который раз в минуту чистит просроченное (активное). Без активной чистки память не освобождается для ключей, которые больше не запрашивают; без ленивой проверки читатель успеет увидеть протухшее.
• «Добавь ограничение размера». Это уже LRU: мапа + двусвязный список, Get двигает элемент в голову, при переполнении выкидываем хвост. Разбирали в главе 1.2, там же ловушка с обновлением при Get.
• «Как избежать cache stampede?» Когда популярный ключ протух, сотня горутин одновременно пойдёт его пересчитывать. Лечится singleflight (следующий вопрос) — все, кроме одной, ждут её результат.
• «Сколько шардов брать?» Порядка 4–8 × GOMAXPROCS, округлённое вверх до степени двойки; на практике берут 128 или 256. Возьмёшь меньше, останется конкуренция; возьмёшь больше, вырастет память под мапы и просядет локальность.
• «Зачем padding в структуре шарда?» False sharing: два мьютекса, попавшие в одну 64-байтную кэш-линию, заставляют ядра гонять эту линию друг у друга, даже когда шарды логически независимы. Padding до размера кэш-линии убирает эффект. Это ровно та деталь, после которой разговор о кэше обычно заканчивается в твою пользу.
• «Кэш с фоновой горутиной — как ловить утечку?» Кэш с TTL заводит горутину-уборщика, и если у структуры нет Close(), эта горутина переживёт сам кэш. С Go 1.27 для таких случаев есть штатный профиль goroutineleak (в 1.26 он был за GOEXPERIMENT=goroutineleakprofile): он показывает горутины, заблокированные на примитивах, до которых из живого кода уже не дотянуться, то есть разбудить их некому. Именно так выглядит уборщик, который ждёт <-c.stop у выброшенного кэша, или горутина, пишущая результат в канал, читателя у которого больше нет. Берётся он как обычный профиль: curl 'localhost:6060/debug/pprof/goroutineleak?debug=1'. Оговорка, которая покажет, что ты им пользовался: горутину, висящую на достижимом канале или на time.Ticker, профиль не покажет — формально её ещё можно разбудить; такие случаи по-прежнему ловятся глазами по /debug/pprof/goroutine?debug=2 и через go.uber.org/goleak в тестах.
• «А в Go 1.24 sync.Map же переписали?» Да, реализацию заменили на HashTrieMap — на многих профилях она заметно быстрее старой, особенно на записи. Но общий совет не поменялся: типизированная мапа под мьютексом (или шарды) остаётся дефолтом, а sync.Map берут под её заявленные сценарии.

Версия 1: на time.Ticker — то, что пишут на доске за две минуты

type TickerLimiter struct {
    tokens chan struct{}
    stop   chan struct{}
}

func NewTickerLimiter(rate int, burst int) *TickerLimiter {
    l := &TickerLimiter{
        tokens: make(chan struct{}, burst),  // ёмкость канала = burst
        stop:   make(chan struct{}),
    }
    for i := 0; i < burst; i++ {             // стартуем с полным ведром
        l.tokens <- struct{}{}
    }

    go func() {
        t := time.NewTicker(time.Second / time.Duration(rate))
        defer t.Stop()
        for {
            select {
            case <-t.C:
                select {
                case l.tokens <- struct{}{}: // капнули токен
                default:                     // ведро полно, токен теряется, и это правильно
                }
            case <-l.stop:
                return
            }
        }
    }()
    return l
}

func (l *TickerLimiter) Wait(ctx context.Context) error {
    select {
    case <-l.tokens:
        return nil
    case <-ctx.Done():
        return ctx.Err()
    }
}

func (l *TickerLimiter) Allow() bool {        // неблокирующий вариант
    select {
    case <-l.tokens:
        return true
    default:
        return false
    }
}

func (l *TickerLimiter) Close() { close(l.stop) }
// l := NewTickerLimiter(5, 3)   // 5 токенов в секунду, ведро на 3
// Allow() пять раз подряд:  true true true false false  ← burst израсходован
// затем Wait() три раза:    прошли на 200ms, 400ms, 600ms, ровно 1/rate между токенами

Всё держится на вложенном select с default. Без него горутина тикера заблокируется на полном ведре, перестанет читать t.C, и весь лимитер встанет. Именно тут валятся чаще всего.

Слабое место версии на тикере: она держит горутину на каждый лимитер и не умеет в дробный rate («1 запрос в 3 секунды» ещё можно, а «2.5 запроса в секунду» уже неудобно). Для сотни лимитеров (по одному на клиента) это сто горутин, которые тикают, даже когда трафика нет.

Версия 2: ленивое пополнение — без горутины и без тикера

type Limiter struct {
    mu       sync.Mutex
    tokens   float64        // дробные токены: держим любой rate
    max      float64        // burst
    rate     float64        // токенов в секунду
    last     time.Time      // когда последний раз пересчитывали
}

func NewLimiter(rate float64, burst int) *Limiter {
    return &Limiter{
        tokens: float64(burst),
        max:    float64(burst),
        rate:   rate,
        last:   time.Now(),
    }
}

// refill вызывается под мьютексом: докапывает токены за прошедшее время.
func (l *Limiter) refill(now time.Time) {
    if now.After(l.last) {
        l.tokens += now.Sub(l.last).Seconds() * l.rate
        if l.tokens > l.max {
            l.tokens = l.max                 // ведро не переполняется
        }
        l.last = now
    }
}

// Allow: неблокирующая проверка, есть токен или нет.
func (l *Limiter) Allow() bool {
    l.mu.Lock()
    defer l.mu.Unlock()
    l.refill(time.Now())
    if l.tokens >= 1 {
        l.tokens--
        return true
    }
    return false
}

// Wait ждёт токен или отмены контекста.
func (l *Limiter) Wait(ctx context.Context) error {
    for {
        l.mu.Lock()
        l.refill(time.Now())
        if l.tokens >= 1 {
            l.tokens--
            l.mu.Unlock()
            return nil
        }
        // сколько ждать, пока капнет токен
        need := (1 - l.tokens) / l.rate
        l.mu.Unlock()

        t := time.NewTimer(time.Duration(need * float64(time.Second)))
        select {
        case <-t.C:                          // проснулись, пробуем ещё раз
        case <-ctx.Done():
            t.Stop()
            return ctx.Err()
        }
    }
}
// l := NewLimiter(5, 3)   // 5 запросов в секунду, burst 3
// Allow() шесть раз подряд: true true true false false false
// затем Wait() три раза:    прошли на 200ms, 400ms, 600ms
// Числа устойчивы: в отличие от порядка горутин, тайминги здесь задаёт арифметика токенов.

Фокус в том, чтобы не хранить токены, а вычислять их по времени. Состояние укладывается в три числа, горутин нет вообще, лимитеров можно завести миллион (по одному на пользователя). Именно так устроен golang.org/x/time/rate, только там ещё резервирование (Reserve) и корректная работа с прошлым временем.

Цикл for в Wait стоит там не случайно: после сна нельзя просто выдать токен — за время сна его мог забрать кто-то другой. Проверять надо заново. Этот цикл забывают, и это вторая по частоте ошибка в задаче.

Token bucket vs leaky bucket vs sliding window

Разница token vs leaky в одной фразе: token bucket ограничивает вход и допускает всплеск, leaky bucket выравнивает выход и всплеск размазывает. Защищаешь чужой сервис с жёстким лимитом — бери token bucket с burst, равным его допуску. Свой медленный ресурс, которому вредны пики, прикрывай leaky.

Где обычно ошибаются

• Нет default при пополнении. Тикер блокируется на полном ведре, лимитер умирает.
• Нет ограничения burst. Ведро копит токены неограниченно; после часа простоя лимитер пропустит тысячи запросов залпом.
• Нет цикла в Wait. После сна токен выдают без повторной проверки, и при конкуренции лимит нарушается.
• time.Sleep вместо select с ctx. Запрос, который клиент уже отменил, продолжает занимать место в очереди.
• Утечка тикера. time.NewTicker без defer t.Stop() живёт вечно вместе с горутиной. Для time.Timer в цикле та же история.
• time.Now() вместо монотонного времени. В Go time.Now() содержит и монотонную часть, и Sub использует именно её, так что перевод системных часов ничего не сломает — но об этом стоит сказать вслух, знают немногие.
• Один глобальный лимитер там, где нужен per-key. За «100 rps на пользователя» стоит мапа лимитеров с вытеснением по неактивности, иначе она растёт бесконечно.

Добивки, которые задаст интервьюер

• «Сделай лимитер на каждого клиента». map[string]*Limiter под мьютексом (или шардированный кэш из прошлого вопроса) плюс фоновая чистка тех, кто не обращался N минут. Без чистки получишь утечку памяти на все IP интернета.
• «А распределённо, на несколько инстансов?» Redis: INCR с EXPIRE для fixed window или Lua-скрипт для token bucket (нужна атомарность чтения и записи). Из готового есть redis-cell. Обязательно упомяни, что появляется сетевой round-trip на каждый запрос и вопрос «что делать, если Redis недоступен» (fail-open или fail-closed — решает продукт).
• «Что вернуть клиенту при отказе?» HTTP 429 Too Many Requests плюс заголовок Retry-After, и по-хорошему X-RateLimit-Limit / -Remaining / -Reset. Ответ про заголовки сразу показывает практический опыт.
• «Как это протестировать без реального ожидания?» Вынести источник времени в интерфейс (now func() time.Time) и подменить в тесте. Тесты, зависящие от time.Sleep, всегда флакают на CI.
• «Чем твой лимитер отличается от x/time/rate?» Тем, что там есть Reserve() — резервирование токена из будущего с возможностью отмены, AllowN/WaitN для «тяжёлых» запросов и аккуратная обработка изменения rate на лету. В проде я бы взял его.

(а) Первый успешный — паттерн «or»

type res struct {
    val string
    err error
}

// First возвращает результат первого успешного вызова.
// Если все упали, возвращает объединение ошибок.
func First(ctx context.Context, urls []string,
    do func(context.Context, string) (string, error)) (string, error) {

    ctx, cancel := context.WithCancel(ctx)
    defer cancel()                       // отменяет всех отставших при любом выходе

    ch := make(chan res, len(urls))      // буфер на всех: никто не зависнет на записи

    for _, u := range urls {
        go func(u string) {
            v, err := do(ctx, u)
            ch <- res{v, err}            // запись не блокируется: буфер вмещает всё
        }(u)
    }

    var errs []error
    for i := 0; i < len(urls); i++ {
        select {
        case r := <-ch:
            if r.err == nil {
                return r.val, nil        // defer cancel() отменит остальных
            }
            errs = append(errs, r.err)
        case <-ctx.Done():
            return "", ctx.Err()
        }
    }
    return "", errors.Join(errs...)      // все N упали
}
// do: "a" падает через 30 мс, "b" отвечает через 10 мс, "c" через 50 мс.
// First(ctx, []string{"a","b","c"}, do) → "ответ от b", <nil>
//   Побеждает не первый в списке, а первый успевший, так что результат зависит
//   от таймингов, а не от порядка urls.
// Если падают все трое, errors.Join печатает их по одной на строку:
//   упал b
//   упал a
//   упал c
//   Это порядок прихода в канал: здесь он задан таймингами, но полагаться на него нельзя.

(б) Все результаты, с сохранением порядка

func All(ctx context.Context, urls []string,
    do func(context.Context, string) (string, error)) ([]string, error) {

    out := make([]string, len(urls))     // длина фиксирована, реаллокаций нет
    errs := make([]error, len(urls))     // каждая горутина пишет в свой индекс

    var wg sync.WaitGroup
    wg.Add(len(urls))
    for i, u := range urls {
        go func(i int, u string) {
            defer wg.Done()
            out[i], errs[i] = do(ctx, u) // разные слоты, гонки нет, мьютекс не нужен
        }(i, u)
    }
    wg.Wait()                            // здесь happens-before: всё записанное видно

    return out, errors.Join(errs...)     // nil, если в errs одни nil
}
// do: "b" возвращает ошибку 503, остальные «ответ от ...»
// All(ctx, []string{"a","b","c"}, do) → ["ответ от a" "" "ответ от c"], 503
//   Слот упавшего остался нулевым, но соседи на месте: в этом и смысл «всех».
// Если ошибок нет:                   → ["ответ от a" "ответ от b" "ответ от c"], <nil>
// Порядок out всегда совпадает с порядком urls: каждый пишет в свой индекс.

wg.Wait() закрывает вопрос с видимостью: всё, что горутина записала до wg.Done(), гарантированно видно после wg.Wait() по модели памяти Go. Читать out после Wait безопасно, и мьютекс тут не нужен. Проговори это вслух: вопрос «а точно ли тут нет гонки?» прилетает почти всегда.

(в) Таймаут на всю операцию

func AllWithTimeout(parent context.Context, urls []string, d time.Duration,
    do func(context.Context, string) (string, error)) ([]string, error) {

    ctx, cancel := context.WithTimeout(parent, d)
    defer cancel()

    type indexed struct {
        i   int
        val string
        err error
    }
    ch := make(chan indexed, len(urls))  // снова буфер на всех

    for i, u := range urls {
        go func(i int, u string) {
            v, err := do(ctx, u)         // ctx уезжает внутрь: HTTP-клиент оборвёт запрос сам
            ch <- indexed{i, v, err}
        }(i, u)
    }

    out := make([]string, len(urls))
    var errs []error
    for got := 0; got < len(urls); got++ {
        select {
        case r := <-ch:
            if r.err != nil {
                errs = append(errs, fmt.Errorf("%s: %w", urls[r.i], r.err))
                continue
            }
            out[r.i] = r.val
        case <-ctx.Done():
            // Вышли по дедлайну. Горутины допишут в буфер и завершатся сами.
            return out, fmt.Errorf("получено %d из %d: %w", got, len(urls), ctx.Err())
        }
    }
    return out, errors.Join(errs...)
}

В комментарии не зря сказано: при выходе по таймауту мы не дренируем канал, и это корректно ровно потому, что он буферизован. Горутины допишут результаты в буфер, завершатся, а сам канал и буфер соберёт GC, когда на них не останется ссылок. Будь канал небуферизован, такой return означал бы N зависших горутин.

Всё то же самое на errgroup — как выглядит прод-версия

// (б) + (в) одной конструкцией: первая ошибка отменяет остальных, есть таймаут и лимит.
func AllEG(ctx context.Context, urls []string, d time.Duration,
    do func(context.Context, string) (string, error)) ([]string, error) {

    ctx, cancel := context.WithTimeout(ctx, d)
    defer cancel()

    g, ctx := errgroup.WithContext(ctx)  // ctx отменится при первой ошибке
    g.SetLimit(8)                        // не более 8 одновременно

    out := make([]string, len(urls))
    for i, u := range urls {
        i, u := i, u                     // до Go 1.22 обязательно
        g.Go(func() error {
            v, err := do(ctx, u)
            if err != nil {
                return fmt.Errorf("%s: %w", u, err)
            }
            out[i] = v
            return nil
        })
    }
    return out, g.Wait()                 // g.Wait() вернёт первую ошибку
}

Где обычно ошибаются

• Небуферизованный канал в варианте «первый успешный». Главная ловушка задачи: N−1 горутин зависают навсегда.
• return сразу после первого элемента без проверки err. Задача про первый успешный, а не первый пришедший. Если первым придёт мгновенная ошибка «connection refused», наивная версия вернёт её и не дождётся успеха.
• Забыт cancel(). После возврата первого успеха остальные запросы продолжают жечь соединения и трафик. defer cancel() обязателен.
• append в общий слайс из горутин. Гонка. Либо канал, либо запись по индексу.
• Таймаут через time.After вместо context. Функция вернётся, а сами HTTP-запросы продолжат выполняться: никто их не оборвал. ctx прерывает работу, time.After лишь прекращает ожидание, и это совсем не одно и то же.
• Возврат nil результатов при частичном успехе. Часто правильнее вернуть и то, что успели, и ошибку, а вызывающий решит сам. Спроси у интервьюера, какая семантика нужна: этот вопрос сам по себе засчитывается в плюс.

Добивки, которые задаст интервьюер

• «А если нужен не первый успешный, а кворум — 2 из 3?» Тот же цикл, но считаем успехи и выходим при ok == quorum. Это quorum read из распределённых систем.
• «Сделай hedged request». Отправляем первый запрос, ждём p95; если не ответил, шлём дубль в другую реплику и берём то, что придёт раньше. Приём из статьи «The Tail at Scale», и сам термин на собеседовании работает хорошо.
• «Что если N — миллион?» Нельзя запускать миллион горутин: нужен SetLimit/семафор, иначе память и число открытых сокетов кончатся раньше результата.
• «Как отличить таймаут от отмены клиентом?» errors.Is(err, context.DeadlineExceeded) против context.Canceled. Для HTTP-сервера это разные коды ответа: 504 и, как правило, 499/ничего.
• «Гарантирует ли wg.Wait() видимость записей?» Да, это прописано в модели памяти Go: Done happens-before возврата из Wait. То же верно для отправки/приёма по каналу и для Unlock/Lock.

Решение на двух каналах

func printAlternate(n int) {
    odd := make(chan struct{})       // разрешение печатать нечётное
    even := make(chan struct{})      // разрешение печатать чётное
    done := make(chan struct{})      // сигнал «всё, закончили»

    var wg sync.WaitGroup
    wg.Add(2)

    go func() {                      // нечётные
        defer wg.Done()
        for i := 1; i <= n; i += 2 {
            <-odd                    // жду свой ход
            fmt.Println(i)
            if i+1 > n {             // следующего чётного не будет
                close(done)          // будим соседа на выход
                return
            }
            even <- struct{}{}       // передаю ход
        }
    }()

    go func() {                      // чётные
        defer wg.Done()
        for i := 2; i <= n; i += 2 {
            select {
            case <-even:
            case <-done:             // сосед закончил: выходим, а не виснем
                return
            }
            fmt.Println(i)
            if i+1 > n {
                close(done)
                return
            }
            odd <- struct{}{}
        }
    }()

    odd <- struct{}{}                // даём старт: первый ход у нечётных
    wg.Wait()
}
// printAlternate(5) → 1 2 3 4 5 (каждое с новой строки)
// printAlternate(6) → 1 2 3 4 5 6
// Порядок здесь детерминирован, и в этом весь смысл: право хода передаётся явно,
// планировщику выбирать не из чего.

Тот же ответ короче: один канал с самим значением

Если разрешено передавать по каналу не «палочку», а само число, решение становится короче, а завершение через close выглядит естественно.

func printAlternate2(n int) {
    odd, even := make(chan int), make(chan int)
    var wg sync.WaitGroup
    wg.Add(2)

    worker := func(mine, next chan int, wantOdd bool) {
        defer wg.Done()
        for v := range mine {        // выходим по close: одна точка завершения
            fmt.Println(v)
            if v == n {
                close(next)          // закрываем свой выход: сосед выйдет из range
                return
            }
            next <- v + 1
        }
    }

    go worker(odd, even, true)
    go worker(even, odd, false)

    odd <- 1
    wg.Wait()
}
// printAlternate2(5) → 1 2 3 4 5;  printAlternate2(6) → 1 2 3 4 5 6
// Тот же строгий порядок, что и в варианте на «палочках».

Здесь close(next) формально нарушает правило «закрывает писатель», но тут это осознанный протокол между двумя строго чередующимися сторонами: в момент close сосед гарантированно стоит в range и в канал не пишет. Такой нюанс полезно проговорить: он показывает, что ты понимаешь, почему существует правило, а не просто его помнишь.

Вариант на sync.Cond — если спросят «а без каналов?»

func printCond(n int) {
    var mu sync.Mutex
    cond := sync.NewCond(&mu)
    turn := 1                        // чей ход: 1 — нечётные, 0 — чётные
    var wg sync.WaitGroup
    wg.Add(2)

    run := func(parity int) {
        defer wg.Done()
        for i := parity; i <= n; i += 2 {
            if i == 0 {
                continue
            }
            mu.Lock()
            for turn != parity%2 {   // всегда for, не if: возможны ложные пробуждения
                cond.Wait()
            }
            fmt.Println(i)
            turn = 1 - turn
            cond.Broadcast()         // будим соседа
            mu.Unlock()
        }
        mu.Lock()                    // финальный Broadcast, чтобы сосед не остался в Wait
        cond.Broadcast()
        mu.Unlock()
    }

    go run(1)
    go run(2)
    wg.Wait()
}
// printCond(5) → 1 2 3 4 5;  printCond(6) → 1 2 3 4 5 6
// Порядок снова строгий: его держит переменная turn, а не планировщик.

for вместо if вокруг cond.Wait() требуется в любом языке с условными переменными. Wait может вернуться без изменения условия, поэтому условие перепроверяют в цикле.

Где обычно ошибаются

• Забыт «стартовый толчок». Обе горутины ждут своего канала, никто не пишет, дедлок с первой же секунды: fatal error: all goroutines are asleep.
• Нет корректного завершения. Самая частая ошибка: числа печатаются правильно, а потом программа падает с deadlock, потому что вторая горутина осталась висеть на <-even. Проверяют здесь именно завершение, остальное тривиально.
• Буферизованные каналы. С буфером чередование ломается: горутина может уйти вперёд на несколько шагов. Здесь буфер обязан быть нулевым: он и есть механизм синхронизации, а не оптимизация.
• Общий счётчик под мьютексом вместо очереди ходов. Мьютекс гарантирует взаимоисключение, но не порядок: одна и та же горутина может захватить его два раза подряд, и получится «1 3 5 … 2 4 6».
• if вместо for вокруг cond.Wait(). Работает «почти всегда», ломается редко и невоспроизводимо.

Добивки, которые задаст интервьюер

• «Сделай для K горутин: печатают 1..N по кругу». Кольцо из K каналов: горутина i читает ch[i], пишет в ch[(i+1)%K]. Красивое обобщение: покажи его сразу, и половина добивок отпадёт.
• «Сколько раз произойдёт переключение контекста?» Порядка N: каждая передача хода через небуферизованный канал паркует одну горутину и будит другую. Это дорого, но задача учебная: в проде такой код не нужен.
• «А через atomic и busy-wait?» Технически да: for atomic.LoadInt32(&turn) != mine { runtime.Gosched() }. Но это спин, который жжёт CPU. Назови такой вариант и сразу объясни, почему так не делают.
• «Что произойдёт, если убрать wg.Wait()?» main завершится и убьёт процесс вместе с горутинами; вывод оборвётся на случайном числе. Наглядно видно: горутины не удерживают программу от выхода.

Mutex на канале

type Mutex chan struct{}

func NewMutex() Mutex { return make(Mutex, 1) }   // ёмкость 1 = одно разрешение

func (m Mutex) Lock()   { m <- struct{}{} }       // занял слот, вошёл
func (m Mutex) Unlock() { <-m }                   // освободил слот

// Бонус, которого нет у sync.Mutex: неблокирующий захват и захват с таймаутом.
func (m Mutex) TryLock() bool {
    select {
    case m <- struct{}{}:
        return true
    default:
        return false
    }
}

func (m Mutex) LockCtx(ctx context.Context) error {
    select {
    case m <- struct{}{}:
        return nil
    case <-ctx.Done():
        return ctx.Err()
    }
}

Канальный мьютекс умеет больше (таймаут, отмена, TryLock до Go 1.18), но заметно медленнее. sync.Mutex в неконкурентном случае обходится одной атомарной CAS-операцией без системных вызовов; канал тащит за собой мьютекс рантайма и очередь ожидающих. Разница обычно в разы. Отсюда правило: канальный мьютекс берут ради семантики (отмена), а не ради скорости.

Once на каналах

type Once struct {
    token chan struct{}   // ровно один токен: достанется одному вызывающему
    done  chan struct{}   // закрывается после выполнения f
}

func NewOnce() *Once {
    o := &Once{
        token: make(chan struct{}, 1),
        done:  make(chan struct{}),
    }
    o.token <- struct{}{}         // единственный токен кладём заранее
    return o
}

func (o *Once) Do(f func()) {
    select {
    case <-o.token:               // выиграл гонку, выполняю
        defer close(o.done)       // defer: даже при панике в f ожидающие проснутся
        f()
    case <-o.done:                // уже выполнено, выходим сразу
    }
}

WaitGroup на каналах

type WaitGroup struct {
    mu   chan struct{}   // мьютекс-канал вокруг счётчика
    n    int
    done chan struct{}   // закрывается, когда n достигает нуля
}

func NewWaitGroup() *WaitGroup {
    wg := &WaitGroup{
        mu:   make(chan struct{}, 1),
        done: make(chan struct{}),
    }
    return wg
}

func (wg *WaitGroup) Add(delta int) {
    wg.mu <- struct{}{}
    defer func() { <-wg.mu }()

    wg.n += delta
    if wg.n < 0 {
        panic("negative WaitGroup counter")   // как в оригинале
    }
    if wg.n == 0 {
        close(wg.done)                        // broadcast: будим всех ожидающих сразу
    }
}

func (wg *WaitGroup) Done() { wg.Add(-1) }

func (wg *WaitGroup) Wait() { <-wg.done }     // на закрытом канале приём мгновенный

func (wg *WaitGroup) WaitCtx(ctx context.Context) error {
    select {
    case <-wg.done:
        return nil
    case <-ctx.Done():
        return ctx.Err()                      // чего sync.WaitGroup не умеет
    }
}

Закрытие канала как broadcast стоит запомнить отдельно от этой задачи. Отправка в канал будит одного ожидающего, закрытие — всех. Именно поэтому done chan struct{} и ctx.Done() устроены через закрытие, а не через отправку значений. Спросят на собесе «как разбудить N горутин одним действием», отвечай: «закрыть канал».

У этой реализации есть ограничение: она одноразовая. Настоящий sync.WaitGroup можно переиспользовать после Wait (при аккуратном Add), а наш done закрыт навсегда: повторный Add до 1 и снова до 0 даст «close of closed channel». Назови ограничение сам, и станет видно, что ты сравнил свою реализацию с контрактом оригинала, а не просто написал что-то работающее.

Где обычно ошибаются

• Once без ожидания. Проигравший гонку уходит до того, как отработает f. Самая содержательная ошибка в задаче.
• close(done) без defer в Once. Паника внутри f оставит все остальные вызовы Do заблокированными навсегда. Кстати, реальный sync.Once ведёт себя так же в части «второй раз f не запустится»: паника считается выполнением.
• Счётчик WaitGroup без защиты. wg.n += delta из нескольких горутин даёт гонку. Нужен либо канал-мьютекс, либо atomic.
• Отправка в done вместо закрытия. Разбудит ровно одного ожидающего, остальные повиснут.
• Мьютекс на структуре-значении. type Mutex chan struct{} работает и по значению, потому что канал это указатель на внутреннюю структуру рантайма. А вот struct { mu chan struct{}; n int } копировать уже нельзя: счётчик продублируется. Отсюда *WaitGroup в методах.

Добивки, которые задаст интервьюер

• «Что быстрее — твой мьютекс или sync.Mutex?» sync.Mutex, почти на порядок на неконкурентном пути: там fast path сводится к одной атомарной операции без обращения к рантайму каналов.
• «Сделай RWMutex на каналах». Заметно сложнее: нужен счётчик читателей, отдельный канал для писателя и правило, которое не даёт писателю голодать. Так и отвечай: «сделаю, но это уже 40 строк, и я бы взял sync.RWMutex».
• «Почему sync.Mutex нельзя копировать?» Внутри лежит состояние (state, sema). Копия получает своё состояние, и два «мьютекса» перестают защищать общее. go vet ловит это правилом copylocks. И ещё: заблокированный мьютекс не привязан к горутине, Unlock может звать другая горутина, в отличие от, скажем, Java-синхронизации.
• «Зачем тогда вообще каналы, если sync быстрее?» Каналы дают композицию: их можно положить в select с таймаутом и отменой. Формула «share memory by communicating» про передачу владения данными, а sync про защиту общего состояния. Это два разных инструмента, а не конкуренты.
• «Что вернёт len() и cap() от твоего мьютекса?» cap всегда 1, len равен 1, если захвачен, и 0, если свободен. Забавный побочный эффект, полезный для метрик и бесполезный для логики (гонка).

Наивная версия — та, которую пишут первой и которая медленнее последовательной

func mergeSortNaive(a []int) []int {
    if len(a) <= 1 {
        return a
    }
    mid := len(a) / 2

    var left, right []int
    var wg sync.WaitGroup
    wg.Add(2)
    go func() { defer wg.Done(); left = mergeSortNaive(a[:mid]) }()   // горутина
    go func() { defer wg.Done(); right = mergeSortNaive(a[mid:]) }()  // и ещё одна
    wg.Wait()

    return merge(left, right)
}

Для слайса на 1 000 000 элементов это около двух миллионов горутин. Каждая берёт минимум 2 КБ стека (растущего), её надо зарегистрировать в планировщике, запарковать на wg.Wait() и разбудить. На нижних уровнях рекурсии горутина создаётся ради сортировки двух элементов: полезной работы наносекунды, накладных расходов сотни. Результат стабильно хуже обычного sort.Ints, иногда в разы.

Правильная версия: порог + ограничение глубины

const seqThreshold = 1 << 12    // ниже 4096 элементов только последовательно

func MergeSort(a []int) []int {
    // Глубина, до которой имеет смысл ветвиться: log2 от числа ядер, +1 про запас.
    maxDepth := bits.Len(uint(runtime.GOMAXPROCS(0)))
    buf := make([]int, len(a))   // один общий буфер на всю сортировку
    copy(buf, a)
    sortInto(buf, a, 0, maxDepth)
    return a
}

// sortInto сортирует src в dst; buf и dst меняются ролями на каждом уровне.
func sortInto(src, dst []int, depth, maxDepth int) {
    n := len(src)
    if n <= 1 {
        return
    }
    if n < seqThreshold || depth >= maxDepth {
        insertionOrStdSort(dst)   // мелкий кусок: без горутин и без рекурсии
        return
    }

    mid := n / 2
    if depth < maxDepth {
        var wg sync.WaitGroup
        wg.Add(1)
        go func() {                                   // одна новая горутина
            defer wg.Done()
            sortInto(dst[:mid], src[:mid], depth+1, maxDepth)
        }()
        sortInto(dst[mid:], src[mid:], depth+1, maxDepth)  // вторую половину в текущей
        wg.Wait()
    } else {
        sortInto(dst[:mid], src[:mid], depth+1, maxDepth)
        sortInto(dst[mid:], src[mid:], depth+1, maxDepth)
    }

    mergeInto(src[:mid], src[mid:], dst)
}

func mergeInto(l, r, dst []int) {
    i, j, k := 0, 0, 0
    for i < len(l) && j < len(r) {
        if l[i] <= r[j] {         // <= сохраняет стабильность сортировки
            dst[k] = l[i]
            i++
        } else {
            dst[k] = r[j]
            j++
        }
        k++
    }
    k += copy(dst[k:], l[i:])
    copy(dst[k:], r[j:])
}

Три отличия от наивной версии, каждое даёт заметный вклад:

1. Одна горутина вместо двух на уровень: вторую половину сортирует текущая горутина. Это вдвое меньше горутин и, что важнее, работа остаётся на «горячем» ядре.
2. Порог seqThreshold. Ниже него не ветвимся вообще. Тот же приём, что в pdqsort из стандартной библиотеки: там порог 12 элементов для insertion sort.
3. Один общий буфер. Наивная версия аллоцирует новый слайс на каждом merge. Слияний ровно n−1, значит и аллокаций n−1: линейно, а не O(n log n), замер на n = 65 536 даёт 65 536 вызовов аллокатора. O(n log n) здесь про суммарный объём: 8,9 МБ на том же входе, и вот он и грузит GC. Версия с двумя буферами, которые меняются ролями, делает ровно одну аллокацию на всю сортировку.

Где обычно ошибаются

• Горутина на каждый рекурсивный вызов. Главная ошибка задачи; ответ «нужен порог» и есть то, что проверяют.
• Аллокация на каждом слиянии. result := make([]int, 0, len(l)+len(r)) внутри merge выглядит невинно, но даёт n−1 аллокацию и O(n log n) выделенных байт: профиль превращается в сплошной GC.
• Гонка на общем слайсе. Две горутины пишут в a[:mid] и a[mid:], и это безопасно (диапазоны не пересекаются). А вот запись в общий result без разделения диапазонов даёт гонку. -race её поймает.
• Захват переменной цикла при попытке распараллелить итеративный вариант (bottom-up merge sort): до Go 1.22 все горутины получат последний диапазон.
• Нестабильность. l[i] < r[j] вместо <= ломает стабильность сортировки. Мелочь, но интервьюер, который просил стабильную, это заметит.
• Замер на маленьком массиве. На 1000 элементах параллельная версия проиграет всегда. Порог окупаемости обычно десятки-сотни тысяч элементов, и его надо назвать вслух.

Добивки, которые задаст интервьюер

• «С какого размера параллельная версия начинает выигрывать?» Отвечай так: «замерил бы go test -bench с -cpu=1,2,4,8; по опыту порядка 10⁵ элементов, но зависит от типа элемента и от того, дорого ли сравнение».
• «Как то же самое сделать для quicksort?» Так же: рекурсивно параллелим, но quicksort хуже балансируется (разбиение может быть неравным), поэтому там особенно важен порог. Зато quicksort работает in-place, ему не нужен буфер, и на практике он быстрее.
• «Что в стандартной библиотеке?» sort.Slice и slices.Sort последовательны и используют pdqsort (с Go 1.19). Параллельной сортировки в stdlib нет: если нужна, берут внешние библиотеки или пишут сами.
• «А если данные не влезают в память?» Внешняя сортировка: режем на куски по объёму RAM, сортируем каждый и пишем на диск, затем k-way merge через кучу. Тот же merge, только источниками служат файлы.
• «Как распараллелить сам merge?» Есть параллельный merge через бинарный поиск медианы: делим оба отсортированных массива на пары кусков, которые можно сливать независимо. Сложно, но это правильный ответ на «а как обойти закон Амдала здесь».

Полная реализация

// call — один «полёт»: сколько бы горутин ни попросило ключ, вызов будет один.
type call struct {
    done chan struct{}    // закрывается, когда результат готов
    val  any
    err  error
    dups int              // сколько вызывающих присоединилось (для метрик)
}

type Group struct {
    mu sync.Mutex
    m  map[string]*call   // ленивая инициализация
}

// Do гарантирует: для одного key в один момент времени fn выполняется ровно один раз.
// Возвращает результат этого выполнения всем ожидающим.
func (g *Group) Do(key string, fn func() (any, error)) (v any, err error, shared bool) {
    g.mu.Lock()
    if g.m == nil {
        g.m = make(map[string]*call)
    }
    if c, ok := g.m[key]; ok {          // полёт уже идёт — присоединяемся
        c.dups++
        g.mu.Unlock()
        <-c.done                        // ждём закрытия канала
        return c.val, c.err, true       // читаем результат ПОСЛЕ закрытия — гонки нет
    }

    c := &call{done: make(chan struct{})}
    g.m[key] = c                        // публикуем полёт под тем же мьютексом
    g.mu.Unlock()

    g.doCall(c, key, fn)
    return c.val, c.err, c.dups > 0
}

func (g *Group) doCall(c *call, key string, fn func() (any, error)) {
    defer func() {
        if r := recover(); r != nil {   // паника не должна оставить ожидающих висеть
            c.err = fmt.Errorf("singleflight: panic: %v", r)
        }
        g.mu.Lock()
        if g.m[key] == c {              // после Forget тут может лежать уже чужой полёт
            delete(g.m, key)            // снимаем свой полёт до закрытия канала
        }
        g.mu.Unlock()
        close(c.done)                   // broadcast: будим всех ожидающих разом
    }()
    c.val, c.err = fn()
}

// Forget убирает ключ из мапы, не дожидаясь завершения:
// следующий вызывающий начнёт новый полёт, а текущий доработает для уже ждущих.
func (g *Group) Forget(key string) {
    g.mu.Lock()
    delete(g.m, key)
    g.mu.Unlock()
}
// 10 горутин одновременно зовут g.Do("top", load), где load спит 50 мс:
//   горутина 10: из БД err=<nil> shared=true
//   горутина  8: из БД err=<nil> shared=true
//   ... (все десять, порядок строк каждый раз разный)
//   реальных вызовов load: 1
// Вот это «1» и есть весь смысл singleflight. Обрати внимание: shared=true даже
// у той горутины, которая реально выполняла вызов — к моменту возврата dups уже 9.

Версия с context и DoChan

У базового Do есть неприятное свойство: ожидающий не может отменить ожидание. Если fn зависла на 30 секунд, все присоединившиеся зависли вместе с ней, даже если их собственные ctx уже отменены. Настоящий golang.org/x/sync/singleflight решает это через DoChan, который возвращает канал вместо значения.

type Result struct {
    Val    any
    Err    error
    Shared bool
}

func (g *Group) DoChan(key string, fn func() (any, error)) <-chan Result {
    ch := make(chan Result, 1)          // буфер 1: отправитель никогда не блокируется
    go func() {
        v, err, shared := g.Do(key, fn)
        ch <- Result{v, err, shared}
    }()
    return ch
}

// Теперь вызывающий может ждать с отменой:
func fetch(ctx context.Context, g *Group, key string) (any, error) {
    select {
    case r := <-g.DoChan(key, func() (any, error) { return loadFromDB(key) }):
        return r.Val, r.Err
    case <-ctx.Done():
        return nil, ctx.Err()           // мы ушли, но полёт продолжается для остальных
    }
}

Буфер 1 в ch — обязателен. Без него горутина-обёртка зависнет навсегда, если вызывающий ушёл по ctx.Done(). Та же логика, что в задаче «первый успешный»: буфер снимает зависимость от того, читает ли кто-нибудь результат.

Зачем это нужно на самом деле: cache stampede

Ключ "top_products" лежит в Redis с TTL 60 секунд и запрашивается 5000 раз в секунду. В момент истечения TTL все 5000 запросов одновременно промахиваются и идут в PostgreSQL за одним и тем же тяжёлым агрегатом. База ложится, ответы замедляются, промахов становится ещё больше — классический каскад. Singleflight превращает эти 5000 обращений в одно: 4999 горутин просто ждут результата первой и получают его копию.

func (s *Service) TopProducts(ctx context.Context) ([]Product, error) {
    if v, ok := s.cache.Get("top_products"); ok {
        return v.([]Product), nil
    }
    v, err, _ := s.sf.Do("top_products", func() (any, error) {
        ps, err := s.db.QueryTopProducts(ctx)   // в БД идёт ровно один запрос
        if err != nil {
            return nil, err
        }
        s.cache.Set("top_products", ps, time.Minute)
        return ps, nil
    })
    if err != nil {
        return nil, err
    }
    return v.([]Product), nil
}

Второй классический приём против stampede — вероятностное раннее обновление: обновлять значение не в момент истечения TTL, а чуть раньше, с вероятностью, растущей по мере приближения к сроку. Тогда лавина не собирается в одну точку времени. Упомянуть оба подхода (singleflight + jitter/early recompute) — сильный ответ.

Где обычно ошибаются

• Мьютекс удерживается на время fn(). Полная сериализация всех ключей — именно то, чего мы избегали.
• Нет defer вокруг delete+close. Паника или ранний return в fn оставляют ключ в мапе навсегда: все последующие запросы этого ключа виснут вечно. Отладить такое в проде крайне неприятно.
• Чтение c.val до <-c.done. Гонка.
• Ключ не удаляется после завершения. Тогда singleflight превращается в кэш без TTL — и первый результат, включая ошибку, навсегда прилипает к ключу.
• Забыт буфер в DoChan. Утечка горутины на каждый отменённый вызов.
• Одна ошибка отдаётся всем. Это осознанный компромисс: если fn упала, все 5000 ожидающих получат один и тот же err. Обычно это желаемое поведение (не добивать упавшую базу), но сказать об этом вслух надо — иначе прозвучит вопрос «а справедливо ли это?».

Добивки, которые задаст интервьюер

• «Чем это отличается от мьютекса на ключ?» Мьютекс на ключ сериализует N вызовов: они выполнятся по очереди, N раз. Singleflight выполняет один вызов и раздаёт результат — это принципиально другая семантика.
• «Что если fn зависла?» Все присоединившиеся зависли с ней. Отсюда DoChan + ctx у вызывающего и обязательный таймаут внутри самой fn.
• «Зачем нужен Forget?» Для случаев, когда полёт «залип» или когда нужно принудительно обновить данные, не дожидаясь текущего вызова. В x/sync он тоже есть.
• «А работает ли это между инстансами сервиса?» Нет, singleflight — процессная дедупликация. Для распределённого варианта нужен распределённый лок (Redis SET NX с TTL) — и вместе с ним весь набор проблем: истёкший лок, split-brain, необходимость fencing token.
• «Есть ли тут утечка памяти?» Мапа растёт только на время активных полётов и сама очищается через delete. Если ключей много, но полёты короткие — мапа остаётся маленькой. Утечка возможна только при незакрытом полёте, что мы закрыли через defer.

Код

func f1() (result int) {          // именованный результат
    defer func() { result *= 2 }()
    return 5
}

func f2() int {                   // анонимный результат
    result := 5
    defer func() { result *= 2 }()
    return result
}

func f3() (result int, err error) {
    defer func() {
        if r := recover(); r != nil {
            err = fmt.Errorf("recovered: %v", r)
            result = -1
        }
    }()
    panic("boom")
}

func f4() (n int) {
    defer func() { n++ }()
    defer func() { n *= 10 }()
    return 1
}

func main() {
    fmt.Println(f1())
    fmt.Println(f2())
    fmt.Println(f3())
    fmt.Println(f4())
}

Почему: что на самом деле делает return

return X в Go распадается на три операции, строго в этом порядке:

1. присвоить X переменной-результату;
2. выполнить отложенные вызовы в порядке LIFO (last in, first out: последний объявленный defer срабатывает первым);
3. фактически вернуть управление, отдав то, что лежит в переменной-результате сейчас.

Вся разница между f1 и f2 сводится к одному: существует ли эта переменная как именованная. В f1 результат назван result, и defer модифицирует ровно ту ячейку, из которой на шаге 3 будет взято значение: result = 5 → result *= 2 → вернули 10.

В f2 результат анонимен. return result копирует значение локальной переменной result в невидимый слот результата, и defer, изменяя локальную result, к этому слоту уже никак не относится. Функция возвращает 5, а result становится 10 в никуда.

f3 применяет ту же механику на практике и остаётся единственным способом вернуть ошибку из recover. Без именованных результатов перехваченная паника не превращается в error: писать некуда.

f4 проверяет порядок: отложенные вызовы выполняются LIFO, поэтому сначала n *= 10 (1 → 10), затем n++ (10 → 11). Порядок объявления обратен порядку выполнения.

Как звучит правильное объяснение на собесе

«return сначала присваивает результату, потом идёт defer, потом собственно возврат. Если результат именованный, defer видит ту же переменную и может её поменять, поэтому f1 вернёт 10. Если анонимный, значение уже скопировано, и defer меняет локальную переменную впустую, так что f2 вернёт 5. На этом же механизме держится превращение паники в ошибку через recover, и на нём же стоит правильный defer Close(), который не теряет ошибку закрытия.»

Код

type T struct {
    n int
}

func (t T) Show()   { fmt.Println("Show (значение):", t.n) }
func (t *T) ShowP() { fmt.Println("ShowP (указатель):", t.n) }

func main() {
    i := 0
    defer fmt.Println("A defer со значением:", i)
    defer func() { fmt.Println("B defer с замыканием:", i) }()

    t := T{n: 1}
    defer t.Show()      // получатель-значение
    defer t.ShowP()     // получатель-указатель

    i = 3
    t.n = 2
    fmt.Println("конец main:", i, t.n)
}

Почему

Правило одно, но у него четыре следствия: defer вычисляет функцию и все её аргументы немедленно, а вызывает при выходе.

• A. i стоит аргументом fmt.Println, поэтому вычислен и скопирован в момент defer, когда i был равен 0. Последующее i = 3 ни на что не влияет.
• B. Аргументов у func(){...}() нет вообще. Тело работает как замыкание, захватывает переменную i, а не её значение, и читает её при выполнении: 3.
• t.Show(). Получатель тоже считается аргументом, просто неявным. Метод объявлен на значении, поэтому t копируется в момент defer: копия помнит n = 1.
• t.ShowP(). Метод на указателе, значит вычисляется и копируется &t, то есть сам указатель, а не то, на что он смотрит. Через него виден актуальный n = 2.

Порядок вывода подчиняется LIFO: последний объявленный defer выполняется первым.

Как звучит правильное объяснение на собесе

«defer значит "запомнить вызов и его аргументы сейчас, выполнить потом". Аргументы, включая получателя метода, копируются в момент объявления. Поэтому defer f(x) замораживает x, а defer func(){ f(x) }() не замораживает: замыкание держит саму переменную. Если метод на значении, заморозится копия структуры; если на указателе, заморозится указатель, и изменения будут видны. Выполняются в порядке LIFO.»

Код

func main() {
    for i := 0; i < 3; i++ {
        defer fmt.Println("defer", i)
    }
    fmt.Println("конец цикла")

    for i := 0; i < 3; i++ {
        func() {
            defer fmt.Println("вложенный defer", i)
        }()
    }
    fmt.Println("конец main")
}

Почему

defer привязан к функции, а не к блоку. Ни фигурные скобки цикла, ни if, ни switch не создают точку выполнения отложенных вызовов; её создаёт только возврат из функции (или паника). Поэтому три defer из первого цикла копятся в списке текущей функции и разряжаются в самом конце main, в порядке LIFO.

Второй цикл показывает стандартное лекарство: обернуть тело итерации в немедленно вызываемую анонимную функцию. Теперь у каждой итерации своя функция, и defer срабатывает на её выходе сразу, в прямом порядке.

// Открывает 10 000 файлов и НИ ОДНОГО не закрывает до конца функции.
for _, name := range names {
    f, err := os.Open(name)
    if err != nil {
        return err
    }
    defer f.Close()          // ← накопится 10 000 отложенных Close
    process(f)
}

Отдельно про производительность: с Go 1.14 defer в большинстве случаев инлайнится и стоит порядка одной-двух наносекунд. Это уже не тот дорогой defer, о котором писали в 2017-м. Но defer в цикле остаётся дорогим по другой причине: он не выполняется, а накапливается в списке, то есть расходует память пропорционально числу итераций.

Как звучит правильное объяснение на собесе

«defer относится к функции, а не к блоку, поэтому в цикле он не выполняется на каждой итерации, а копится и разряжается в конце функции в порядке LIFO. Для ресурсов внутри цикла это утечка дескрипторов, поэтому тело итерации заворачивают в анонимную функцию, чтобы у каждой итерации была своя точка выхода. В main из примера сначала отработают все вложенные defer по ходу второго цикла, а три "цикловых" сработают только после конец main, в обратном порядке.»

Код

func main() {
    var wg sync.WaitGroup
    for i := 0; i < 3; i++ {
        wg.Add(1)
        go func() { defer wg.Done(); fmt.Print(i, " ") }()
    }
    wg.Wait()
    fmt.Println()

    var fns []func()
    for _, s := range []string{"a", "b", "c"} {
        fns = append(fns, func() { fmt.Print(s, " ") })
    }
    for _, f := range fns {
        f()
    }
    fmt.Println()

    ptrs := []*int{}
    for i := 0; i < 3; i++ {
        ptrs = append(ptrs, &i)
    }
    for _, p := range ptrs {
        fmt.Print(*p, " ")
    }
    fmt.Println()
}

Почему: что именно изменили в Go 1.22

До Go 1.22 переменная цикла объявлялась один раз на весь цикл и переиспользовалась на каждой итерации. Замыкание захватывает переменную, а не её значение, поэтому все три горутины ссылались на одну и ту же ячейку памяти. К моменту их запуска цикл обычно уже завершался, и в ячейке лежало финальное значение, 3 для счётчика и "c" для range. Отсюда и &i: три указателя на одну ячейку.

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

Деталь про версию. Поведение определяется не версией установленного компилятора, а строкой go 1.xx в go.mod модуля. Собранный Go 1.27 модуль с go 1.21 получит старую семантику. Именно поэтому вопрос всё ещё живой: легаси-модулей с go 1.19 вокруг очень много, а миграция сводится к правке одной строки, которую боятся трогать ровно из-за этого изменения.

Как писали до 1.22 — и почему это до сих пор встречается

// Способ 1: параметр функции, значение копируется при вызове go.
for i := 0; i < 3; i++ {
    go func(i int) { fmt.Print(i, " ") }(i)
}

// Способ 2: затенение, новая переменная на итерацию вручную.
for i := 0; i < 3; i++ {
    i := i                    // да, это легально и было идиомой
    go func() { fmt.Print(i, " ") }()
}
// Оба способа под go 1.21 в go.mod печатают 0, 1 и 2, но в произвольном порядке.
// Шесть прогонов подряд дали: 2 0 1 / 2 1 0 / 2 1 0 / 2 1 0 / 2 1 0 / 2 0 1.
// (В самом фрагменте нет wg.Wait, так что для проверки его надо дописать,
//  иначе main завершится раньше, чем горутины успеют напечатать хоть что-то.)

Оба приёма продолжают работать и на 1.22+, просто перестали быть обязательными. В новом коде строка i := i теперь избыточна, и линтеры (copyloopvar) на неё ругаются.

Как звучит правильное объяснение на собесе

«Замыкание захватывает переменную, а не значение. До Go 1.22 переменная цикла была одна на весь цикл, поэтому все горутины видели её финальное значение, отсюда 3 3 3. С Go 1.22 на каждой итерации создаётся своя переменная, и выведется 0, 1, 2, но в произвольном порядке, потому что порядок выполнения горутин не гарантирован. Семантику задаёт строка go в go.mod, а не версия компилятора, так что в старом модуле, собранном новым Go, поведение останется старым.»

Код

func main() {
    a := []int{1, 2, 3, 4, 5}
    b := a[1:3]
    fmt.Println(len(b), cap(b))

    b = append(b, 99)
    fmt.Println(a)
    fmt.Println(b)
}

Почему

Слайс устроен как заголовок из трёх полей: {ptr, len, cap}. Операция a[1:3] не копирует данные, она делает новый заголовок на тот же массив: указатель сдвигается на элемент 1, длина становится 2, а ёмкость считается до конца массива: cap(b) = cap(a) - 1 = 4. Именно эта «лишняя» ёмкость и есть корень проблемы.

append(b, 99) видит len(b) < cap(b) и понимает, что место есть, а новый массив выделять не нужно. Он записывает 99 в следующую свободную ячейку того же массива, а это физически a[3]. Значение 4 уничтожено. Возвращается заголовок с len = 3, указывающий туда же.

Где это встречается в реальном коде

// Популярный приём «отфильтровать без аллокации» легко превращается в баг,
// если вызывающий продолжает пользоваться исходным слайсом.
func filterInPlace(s []int, keep func(int) bool) []int {
    out := s[:0]                 // тот же массив, len 0, cap полный
    for _, v := range s {
        if keep(v) {
            out = append(out, v) // пишем поверх s
        }
    }
    return out
}

a := []int{1, 2, 3, 4, 5}
b := filterInPlace(a, func(v int) bool { return v%2 == 0 })
// b = [2 4], но a = [2 4 3 4 5] — исходный слайс изуродован

Как звучит правильное объяснение на собесе

«Срез не копирует данные, он делает новый заголовок на тот же массив, и cap считается до конца массива, а не до конца среза. У b получилось len 2, cap 4, поэтому append нашёл свободное место в том же массиве и записал 99 в ячейку, которая для a служит четвёртым элементом. Если нужно гарантировать независимость, надо либо явно копировать через slices.Clone, либо ограничить ёмкость трёхиндексным срезом a[1:3:3].»

Код

func main() {
    x := make([]int, 3, 4)        // len 3, cap 4, есть одна свободная ячейка
    copy(x, []int{1, 2, 3})

    y := append(x, 4)
    z := append(x, 5)
    fmt.Println(x, y, z)

    p := []int{1, 2, 3}           // len 3, cap 3, свободных ячеек нет
    q := append(p, 4)
    q[0] = 99
    fmt.Println(p, q)
}

Почему

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

Первый случай. При cap(x) = 4 и len(x) = 3 свободная ячейка есть. append(x, 4) записывает 4 в array[3] и возвращает заголовок {ptr, 4, 4}. Затем append(x, 5) смотрит на тот же x, у которого по-прежнему len 3, и записывает 5 в ту же array[3], затирая четвёрку. Теперь y и z держат два заголовка на один массив, и оба показывают [1 2 3 5]. Сам x остаётся [1 2 3], потому что его len никто не менял: append не модифицирует исходный заголовок, он возвращает новый.

Второй случай. cap(p) = 3, места нет. append выделяет новый массив (обычно вдвое больше), копирует туда три элемента, дописывает четвёртый. Слайс q смотрит на новую память, поэтому q[0] = 99 никак не задевает p.

Как растёт ёмкость

Точные коэффициенты остаются деталью реализации и менялись между версиями, но модель такая: для маленьких слайсов ёмкость примерно удваивается, а после порога (около 256 элементов с Go 1.18) рост становится плавнее и с ростом длины сходится к ×1.25, чтобы не тратить память на больших объёмах: сразу за порогом коэффициент ещё около полутора. Поэтому append работает амортизированно за O(1): отдельная операция может стоить O(n) на копировании, но суммарно за n добавлений копирований будет O(n). Заранее известный размер стоит задавать: make([]T, 0, n) убирает все реаллокации.

var s []int
prev := cap(s)
for i := 0; i < 2000; i++ {
    s = append(s, i)
    if cap(s) != prev {
        fmt.Printf("len=%d cap=%d\n", len(s), cap(s))
        prev = cap(s)
    }
}
// len=1 cap=4, len=5 cap=8, len=9 cap=16, len=17 cap=32, ... len=257 cap=512,
// а дальше шаг роста уменьшается: 512 -> 848 -> 1280 -> 1792 -> 2560

Как звучит правильное объяснение на собесе

«append смотрит на len и cap. Если места хватает, он пишет в существующий массив и возвращает заголовок с увеличенной длиной; исходный слайс при этом не меняется, но данные общие. Если места нет, выделяется новый массив, и слайсы становятся независимыми. В первом примере ёмкости хватило, поэтому оба append писали в одну и ту же ячейку, и второй затёр первый. Во втором не хватило, поэтому q уехал на новую память. Из этого следует правило: не полагаться на то, скопировал append данные или нет, а копировать явно, когда независимость нужна.»

Код

func main() {
    m := []int{1, 2, 3, 4, 5}
    n := m[1:3:3]                 // low : high : max
    fmt.Println(len(n), cap(n))

    n = append(n, 99)
    fmt.Println(m)
    fmt.Println(n)
}

Почему

Full slice expression a[low:high:max] задаёт все три поля заголовка явно: ptr = &a[low], len = high - low, cap = max - low. Действует ограничение low ≤ high ≤ max ≤ cap(a).

В примере cap(n) == len(n) == 2, свободного места нет вообще. Поэтому append обязан выделить новый массив и скопировать туда данные, а исходный m остаётся физически недосягаем. Ровно этого мы и добивались.

Приём применяют, когда отдают наружу кусок своего буфера и не хотят, чтобы вызывающий его случайно испортил:

type Buffer struct {
    data []byte
}

// Плохо: вызывающий может append'нуть и затереть наши данные за границей len.
func (b *Buffer) Head(n int) []byte { return b.data[:n] }

// Хорошо: cap обрезан, любой append у вызывающего сделает копию.
func (b *Buffer) HeadSafe(n int) []byte { return b.data[:n:n] }

Идиома s[:n:n] (или s[:len(s):len(s)]) читается как «отдать read-append-safe вид на слайс». Ровно в таком виде она встречается в стандартной библиотеке и в хорошем чужом коде.

Как звучит правильное объяснение на собесе

«Третий индекс задаёт cap: a[low:high:max] даёт cap = max - low. Когда я пишу a[1:3:3], ёмкость становится равной длине, свободного места нет, и любой append вынужден скопировать данные в новый массив. Это стандартный приём, когда отдаёшь наружу часть своего буфера: сосед не сможет незаметно записать поверх твоих данных через append. От прямой записи по индексу это не защищает, там нужна копия.»

Код

func mod(s []int) {
    s[0] = 100                    // запись по индексу
    s = append(s, 4)              // может переаллоцировать
    s[1] = 200                    // запись, но куда?
}

func main() {
    a := []int{1, 2, 3}           // len 3, cap 3
    mod(a)
    fmt.Println(a, len(a), cap(a))

    b := make([]int, 3, 4)        // len 3, cap 4
    copy(b, []int{1, 2, 3})
    mod(b)
    fmt.Println(b, len(b), cap(b))
}

Почему

В Go всё передаётся по значению, включая слайс. Функция получает копию заголовка {ptr, len, cap}. Отсюда два разных эффекта, которые часто путают в один:

• Запись по индексу проходит через указатель, который в копии заголовка тот же. Поэтому s[0] = 100 меняет данные, видимые снаружи. Работает всегда.
• append меняет поля len/cap копии заголовка, а копия локальна. Даже если данные записались в общий массив, снаружи len остался старым, и новый элемент не виден. Именно поэтому обязательно писать s = append(s, v) и возвращать результат.

Первый случай: cap(a) = 3, места нет, append выделил новый массив. Локальный s теперь смотрит туда, и s[1] = 200 пишет в новую память, которую снаружи никто не видит. На выходе [100 2 3].

Второй случай: cap(b) = 4, место есть, append дописал в тот же массив. Локальный s всё ещё указывает на массив b, поэтому s[1] = 200 меняет b[1]. Получается [100 200 3], а четвёрка лежит в b[3], за границей длины, и снаружи не видна.

Как надо было написать

// Вариант 1: вернуть результат, так идиоматичнее.
func mod(s []int) []int {
    s[0] = 100
    s = append(s, 4)
    s[1] = 200
    return s
}
a = mod(a)

// Вариант 2: указатель на слайс, когда возврат неудобен (редко).
func modP(s *[]int) {
    (*s)[0] = 100
    *s = append(*s, 4)
}

Как звучит правильное объяснение на собесе

«Слайс передаётся по значению, функция получает копию заголовка, но указатель внутри тот же. Поэтому запись по индексу видна снаружи всегда, а append снаружи не виден: он меняет len локальной копии. Дальше всё зависит от ёмкости: если append переаллоцировал, локальный слайс уехал на новую память и последующие записи наружу не видны; если места хватило, они по-прежнему идут в исходный массив. Поэтому в Go и пишут s = append(s, v), а функции, которые дописывают в слайс, возвращают его.»

Код

type P struct {
    Name string
    Age  int
}

func main() {
    ps := []P{{"Аня", 30}, {"Боря", 40}}
    for _, p := range ps {
        p.Age++                       // меняем копию
    }
    fmt.Println(ps)

    for i := range ps {
        ps[i].Age++                   // меняем оригинал
    }
    fmt.Println(ps)

    arr := [3]int{1, 2, 3}            // МАССИВ
    fmt.Print("массив: ")
    for i, v := range arr {
        if i == 0 {
            arr[1] = 100
        }
        fmt.Print(v, " ")
    }
    fmt.Println(arr)

    sl := []int{1, 2, 3}              // СЛАЙС
    fmt.Print("слайс:  ")
    for i, v := range sl {
        if i == 0 {
            sl[1] = 100
        }
        fmt.Print(v, " ")
    }
    fmt.Println(sl)
}

Почему часть первая: переменная цикла — копия

for _, p := range ps на каждой итерации копирует элемент в переменную p. Копия структуры полностью независима, p.Age++ инкрементирует её и выбрасывает при следующей итерации. Чтобы изменить оригинал, нужно обращаться по индексу: ps[i].Age++ (или брать &ps[i]).

Побочный эффект, о котором стоит знать: копирование не бесплатно. Если структура большая — скажем, 200 байт, — цикл for _, v := range bigStructs копирует по 200 байт на итерацию. Для горячего кода это заметно, и там пишут for i := range s с обращением &s[i].

Почему часть вторая: range вычисляет выражение один раз

Перед началом цикла Go один раз вычисляет выражение справа от range и работает с этой копией значения. И вот тут массив и слайс расходятся радикально:

• Массив — это значение целиком, все элементы. Копируется весь массив. Цикл идёт по копии, поэтому arr[1] = 100 внутри тела на итерации не влияет: копия сделана до цикла. Печатается 1 2 3, хотя сам arr уже [1 100 3].
• Слайс — это заголовок {ptr, len, cap}. Копируется заголовок, но данные общие. Поэтому sl[1] = 100 видно на следующей итерации: печатается 1 100 3.

Отсюда же следует ещё одно свойство: число итераций фиксируется до цикла. Если внутри range sl делать sl = append(sl, x), цикл всё равно пройдёт исходное число раз — бесконечного цикла не будет, потому что len взят один раз. Это отличает Go от языков, где такой код зацикливается.

Как звучит правильное объяснение на собесе

«range делает две вещи, о которых надо помнить. Первое: он один раз вычисляет выражение справа. Для массива это копия всех элементов, поэтому изменения внутри цикла не видны; для слайса — копия заголовка, а данные общие, поэтому видны. Второе: переменная значения — это копия элемента, менять её бессмысленно, надо идти через индекс. Оба факта сводятся к одному: в Go всё копируется по значению, а разница между массивом и слайсом — в том, что именно лежит в этом значении.»

Код

func main() {
    m := map[string]int{"a": 1, "b": 2, "c": 3, "d": 4, "e": 5, "f": 6}
    for r := 0; r < 3; r++ {
        fmt.Print("проход ", r, ": ")
        for k := range m {
            fmt.Print(k, " ")
        }
        fmt.Println()
    }

    m2 := map[int]int{1: 1, 2: 2, 3: 3, 4: 4}
    seen := 0
    for k := range m2 {
        seen++
        if k == 1 {
            m2[100] = 100          // добавляем во время обхода
            delete(m2, 4)          // и удаляем
        }
    }
    fmt.Println("итераций:", seen, "итог:", len(m2))
}

Почему порядок случаен — и почему это сделано специально

Рантайм Go намеренно рандомизирует стартовую позицию обхода мапы. Это не побочный эффект хеширования, а сознательное решение: чтобы никто не начал полагаться на порядок, который остаётся деталью устройства мапы. Иначе любая переделка внутренностей (а их переписывали: в Go 1.24 мапу перевели на SwissTable) ломала бы код по всей экосистеме. Плюс защита от HashDoS: в этой атаке злоумышленник подбирает ключи с одинаковым хешем, все они ложатся в одну корзину, и поиск в мапе вырождается из O(1) в O(n). Подобрать такие ключи не выйдет: сид (seed, случайное число, которое подмешивается в хеш) у каждого процесса свой и берётся при старте.

Практическое следствие: если порядок нужен, его надо создать явно.

keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
sort.Strings(keys)               // или slices.Sort(keys)
for _, k := range keys {
    fmt.Println(k, m[k])
}
// Для m := map[string]int{"b": 2, "a": 1, "c": 3} выведет всегда одно и то же:
// a 1
// b 2
// c 3

Почему модификация во время обхода даёт разное число итераций

Спецификация Go описывает это буквально в двух правилах:

• Удаление безопасно и предсказуемо. Если ключ удалён во время обхода, а цикл до него ещё не дошёл, он не будет выдан. Поэтому for k := range m { delete(m, k) } законно очищает мапу (хотя clear(m) с Go 1.21 лучше).
• Добавление недетерминированно. Новый ключ может быть выдан в этом же обходе, а может и нет. Зависит от того, попал он в уже пройденную область таблицы или в ещё не пройденную и вызвала ли вставка рост таблицы.

В примере: 4 ключа, а на итерации с ключом 1 один удаляется (4) и один добавляется (100). Если удалённый ключ ещё не был выдан, а это редкий случай — ключ 1 должен выпасть первым, — получается минус одна итерация. Новый попал в непройденную часть, значит плюс одна. Комбинации дают 3 или 4. Итоговый len при этом всегда 4: было 4, минус один, плюс один.

Как звучит правильное объяснение на собесе

«Порядок обхода мапы в Go рандомизирован намеренно: чтобы на него не полагались и чтобы защититься от HashDoS. Для стабильного порядка надо собрать ключи в слайс и отсортировать. Модификация во время обхода из одной горутины легальна, но с оговорками: удалённый ключ гарантированно не будет выдан, а добавленный может быть выдан, а может нет. Поэтому число итераций тут не определено, 3 или 4. А конкурентная модификация из другой горутины даёт fatal error от рантайма, который не ловится через recover.»

Код

func main() {
    var m map[string]int           // объявлена, но НЕ создана — это nil

    fmt.Println(m == nil, len(m), m["x"])
    v, ok := m["x"]
    fmt.Println("чтение:", v, ok)

    delete(m, "x")                 // без паники
    for range m {                  // 0 итераций, без паники
        fmt.Println("не будет")
    }
    fmt.Println("до записи всё ок")

    defer func() { fmt.Println("recover:", recover()) }()
    m["x"] = 1                     // ← вот тут
}

Почему

Nil-мапа хранит нулевой указатель на хеш-таблицу. Всё, что не требует самой таблицы, работает корректно и без специальных проверок в твоём коде:

Асимметрию сделали осознанно: nil-мапа ведёт себя как пустая мапа только для чтения. Поэтому функция спокойно возвращает nil вместо пустой мапы, а вызывающий её читает и обходит, не проверяя на nil. Так же устроен nil-слайс: len, range и append на нём работают.

type Config struct {
    Name string
    Tags map[string]string          // забыли инициализировать
}

c := Config{Name: "svc"}
fmt.Println(c.Tags["env"])          // "" — работает, никаких подозрений
c.Tags["env"] = "prod"              // panic: assignment to entry in nil map

Как звучит правильное объяснение на собесе

«Nil-мапа ведёт себя как пустая мапа, доступная только для чтения. Чтение, len, range и delete на ней работают и возвращают нулевые значения: так сделано, чтобы функции могли возвращать nil вместо пустой мапы. Паникует только запись, потому что писать физически некуда. Чаще всего на это напарываются с мапой-полем структуры: нулевое значение структуры содержит nil-мапу, и падение приходит на первой же записи. Отсюда правило: мапы и каналы инициализируются в конструкторе.»

Код

type MyErr struct {
    Code int
}

func (e *MyErr) Error() string { return fmt.Sprintf("my error %d", e.Code) }

func doWork(fail bool) *MyErr {      // ← конкретный тип, не error
    if fail {
        return &MyErr{Code: 500}
    }
    return nil                       // честный nil типа *MyErr
}

func wrap(fail bool) error {         // ← а тут уже интерфейс
    return doWork(fail)
}

func main() {
    err := wrap(false)
    fmt.Println("err == nil:", err == nil)
    fmt.Println("err печатается как:", err)
    fmt.Printf("%v | %T\n", err, err)

    var p *MyErr
    var i any = p
    fmt.Println("any(nil-указатель) == nil:", i == nil)
}

Почему

Внутри значения интерфейса лежит пара (тип, значение). Интерфейс равен nil тогда и только тогда, когда обе части пусты.

На return doWork(fail) срабатывает неявное преобразование *MyErr → error. Компилятор упаковывает пару: тип *MyErr есть, значение указателя равно nil. Интерфейс получился «непустым», хотя внутри пусто.

Больнее всего делает баг строка err печатается как: <nil>. fmt видит nil-указатель внутри и печатает <nil>, так что в логах всё выглядит нормально, а if err != nil при этом срабатывает. Классический сценарий: сервис отвечает «ошибка», в логе стоит <nil>, и несколько часов уходит на поиск.

Как чинить

// Вариант 1 (лучший): функция сразу возвращает интерфейс error.
func doWork(fail bool) error {
    if fail {
        return &MyErr{Code: 500}
    }
    return nil                       // теперь это настоящий nil-интерфейс
}

// Вариант 2: если сигнатуру менять нельзя — явная проверка при конвертации.
func wrap(fail bool) error {
    if e := doWork(fail); e != nil {  // сравниваем УКАЗАТЕЛЬ с nil, до упаковки
        return e
    }
    return nil
}

Правило, которое стоит произнести: «функции всегда возвращают error, а не конкретный тип ошибки». Это официальная рекомендация из Go FAQ, а вот линтера, который ловил бы этот случай, нет: nilnil проверяет другое — возврат nil, nil, — а nilness из x/tools в go vet не входит и ищет разыменование заведомо нулевого указателя.

Как звучит правильное объяснение на собесе

«Интерфейс хранит пару тип-значение и равен nil только когда обе части пусты. Здесь функция вернула nil типа *MyErr; при упаковке в error тип сохранился, поэтому интерфейс не nil, хотя указатель внутри nil. Печатается он при этом как <nil>, что делает баг особенно неприятным. Правило простое: возвращать из функций error, а не конкретный тип ошибки; если сигнатуру не поменять, сравнить конкретный указатель с nil до того, как он попадёт в интерфейс.»

Код

func main() {
    defer func() {
        if r := recover(); r != nil {
            fmt.Println("main recover:", r)
        }
        fmt.Println("defer в main")
    }()

    go func() {
        defer fmt.Println("defer в горутине")
        panic("boom")
    }()

    time.Sleep(100 * time.Millisecond)
    fmt.Println("сюда не дойдём")
}

Почему

recover работает только внутри той же горутины, где случилась паника, и только в отложенной функции, вызванной непосредственно паникующей цепочкой. У каждой горутины свой стек и свой список defer; main о панике в другой горутине ничего не знает: для неё эта паника не «происходит».

Механика раскрутки такая: паника поднимается по стеку своей горутины, выполняя её отложенные вызовы, поэтому defer в горутине и печатается. Если ни один из них не сделал recover, паника доходит до вершины стека горутины, и рантайм печатает сообщение с трассировкой и завершает весь процесс. Отложенные вызовы остальных горутин, включая main, при этом не выполняются вовсе.

// Обёртка, которую стоит завести в любом сервисе с фоновыми горутинами.
func Go(fn func()) {
    go func() {
        defer func() {
            if r := recover(); r != nil {
                log.Printf("паника в горутине: %v\n%s", r, debug.Stack())
                metrics.PanicTotal.Inc()
            }
        }()
        fn()
    }()
}

goroutine 1 [running] {request_id: "abc-123", route: "/users/{id}"}:
main.main()

Что recover не ловит вообще

• Панику из другой горутины: разобрано выше.
• fatal error от рантайма. «concurrent map writes», «all goroutines are asleep - deadlock», «out of memory», переполнение стека. Это не паники, а фатальные состояния рантайма: их не перехватить в принципе.
• os.Exit(). Он не разматывает стек и не выполняет defer.
• recover не в defer. Вызов recover() прямо в коде функции всегда вернёт nil: он работает только из отложенной функции. И только из непосредственно отложенной: defer func(){ helper() }(), где helper вызывает recover, тоже не сработает.

Как звучит правильное объяснение на собесе

«recover действует только в своей горутине: у каждой горутины свой стек и свой список defer. Паника раскручивает стек только этой горутины, поэтому её собственный defer отработает, а потом рантайм печатает трассировку и убивает процесс целиком. defer в main и в других горутинах при этом не выполняется. Отсюда практическое правило: каждая горутина, которую ты запускаешь, обязана иметь свой recover, иначе любая ошибка в фоновой задаче роняет весь сервис.»

Код

func main() {
    a := make(chan int, 1)
    b := make(chan int, 1)
    counts := map[string]int{}
    for i := 0; i < 10000; i++ {
        a <- 1
        b <- 2
        select {                       // ОБА готовы
        case <-a:
            counts["a"]++
            <-b
        case <-b:
            counts["b"]++
            <-a
        }
    }
    fmt.Println("случайный выбор:", counts)

    c := make(chan int)
    close(c)
    for i := 0; i < 3; i++ {
        select {
        case v, ok := <-c:
            fmt.Println("из закрытого:", v, ok)
        }
    }

    var nilCh chan int
    select {
    case <-nilCh:
        fmt.Println("никогда")
    default:
        fmt.Println("nil-канал не готов никогда — сработал default")
    }
}

Почему

Правил у select четыре, и все четыре стоит назвать:

1. Если готова ровно одна ветка, выполняется она.
2. Если готовы несколько, выбирается равновероятно случайная. Не первая, не последняя, не по порядку в коде. Это гарантия языка, и держится она на перестановке порядка опроса. Сделано, чтобы select не голодал ни по одной ветке: иначе быстрый канал навсегда заглушил бы медленный.
3. Если не готова ни одна и есть default, выполняется default, и select становится неблокирующим.
4. Если не готова ни одна и default нет, горутина блокируется, пока какая-нибудь не станет готова. select{} без веток блокируется навсегда.

Закрытый канал всегда готов на чтение и мгновенно отдаёт нулевое значение с ok == false. Отсюда две вещи. Хорошая: на этом построены done-каналы и ctx.Done(): закрытие будит всех ожидающих сразу. Плохая: если забыть про ok, select в цикле по закрытому каналу начнёт крутиться на 100% CPU, бесконечно получая нули. Лечит обнуление канала:

for a != nil || b != nil {
    select {
    case v, ok := <-a:
        if !ok {
            a = nil                    // выключаем ветку навсегда
            continue
        }
        use(v)
    case v, ok := <-b:
        if !ok {
            b = nil
            continue
        }
        use(v)
    }
}

Nil-канал в select не готов никогда, ни на чтение, ни на запись, и просто «выключает» свою ветку. Это не костыль, а официальная идиома: приём с ch = nil живёт в стандартной библиотеке и в любом нетривиальном pipeline. Вне select операция с nil-каналом блокирует навсегда, и отсюда же берётся её роль «выключателя».

for {
    select {
    case v := <-ch:
        handle(v)
    case <-time.After(time.Second):    // НОВЫЙ таймер на каждой итерации
        return
    }
}

Как звучит правильное объяснение на собесе

«Если в select готовы несколько веток, выбирается случайная. Это гарантия языка, а не деталь реализации, и сделана она против голодания. Закрытый канал всегда готов и отдаёт нулевое значение с ok = false, поэтому в цикле такой select закрутится, если не проверять ok и не обнулять канал. Nil-канал, наоборот, не готов никогда, и присваивание ch = nil служит стандартным способом выключить ветку select. default делает select неблокирующим.»

Код

type S struct {
    mu sync.Mutex
    n  int
    sl []int
    m  map[string]int
    p  *int
}

func main() {
    one := 1
    a := S{n: 1, sl: []int{1, 2, 3}, m: map[string]int{"x": 1}, p: &one}
    b := a                             // копирование структуры

    b.n = 100
    b.sl[0] = 100
    b.m["x"] = 100
    *b.p = 100
    b.sl = append(b.sl, 4)

    fmt.Println("a:", a.n, a.sl, a.m, *a.p)
    fmt.Println("b:", b.n, b.sl, b.m, *b.p)
}

Почему

Структура копируется поверхностно (shallow copy): побайтово копируются все поля. Дальше всё решает тип поля.

Тонкий момент со слайсом: b.sl[0] = 100 видно в a, потому что массив общий. А b.sl = append(b.sl, 4) уже не видно: append при cap 3 переаллоцировал, и b.sl уехал на новый массив. Даже если бы ёмкости хватило, a.sl всё равно остался бы длиной 3, заголовки-то разные. Одна строка кода показывает обе половины природы слайса.

Как сделать настоящую независимую копию

func (s *S) Clone() *S {
    s.mu.Lock()
    defer s.mu.Unlock()

    c := &S{n: s.n}                    // новый мьютекс в нулевом состоянии
    c.sl = slices.Clone(s.sl)          // копия слайса
    c.m = maps.Clone(s.m)              // копия мапы (тоже поверхностная!)
    if s.p != nil {
        v := *s.p
        c.p = &v                       // копия значения по указателю
    }
    return c
}

Оговорка: slices.Clone и maps.Clone тоже поверхностные. Если внутри слайса лежат структуры со слайсами, их придётся копировать рекурсивно. Настоящего глубокого копирования в стандартной библиотеке нет, и на добивку правильно ответить: «сделал бы явный Clone, потому что автоматического deep copy в Go нет».

Как звучит правильное объяснение на собесе

«Копирование структуры в Go поверхностное: копируются поля как есть. int скопировался по-настоящему. Слайс скопировал заголовок, массив остался общий, но длина у каждого своя, поэтому запись по индексу видна, а append уже нет. Мапа и указатель сами по себе указатели, данные полностью общие. А мьютекс скопировался вместе со своим состоянием, и это баг: у копии свой мьютекс, взаимоисключение сломано. go vet ловит это правилом copylocks, поэтому типы с мьютексом всегда используются через указатель.»

Код

package main

import "fmt"

var a = b + 1                     // объявлены в «неправильном» порядке
var b = c + 1
var c = f()

func f() int { fmt.Println("1. f() — вычисляется c"); return 1 }

func init() { fmt.Println("2. init A:", a, b, c) }
func init() { fmt.Println("3. init B") }

const (
    A = iota                      // 0
    B                             // 1
    _                             // 2 — пропущен
    D                             // 3
)

const (
    _  = iota
    KB = 1 << (10 * iota)          // 1 << 10
    MB                            // повтор выражения с iota = 2
    GB
)

type Weekday int

const (
    Mon Weekday = iota + 1
    Tue
    Wed
)

func main() {
    fmt.Println("4. main:", a, b, c)
    fmt.Println("iota:", A, B, D)
    fmt.Println("размеры:", KB, MB, GB)
    fmt.Println("дни:", Mon, Tue, Wed)
}

Почему: переменные пакета инициализируются по зависимостям, а не по порядку

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

Здесь a зависит от b, b зависит от c, а c не зависит ни от чего. Поэтому реальный порядок: c = f() = 1, затем b = 2, затем a = 3. Текстовый порядок объявления полностью игнорируется. Циклическая зависимость (var x = y; var y = x) даёт ошибку компиляции, а не бесконечный цикл.

Полный порядок запуска программы: константы пакета → переменные пакета в порядке зависимостей → все функции init() в порядке объявления (их может быть сколько угодно, в том числе несколько в одном файле) → main(). Пакеты при этом обрабатываются снизу вверх по дереву импортов: импортируемый пакет полностью инициализируется раньше импортирующего, и каждый проходит это ровно один раз, даже если импортирован многократно.

Почему iota ведёт себя именно так

• iota хранит порядковый номер ConstSpec в блоке const, считая с нуля. Не «счётчик констант», а именно номер строки спецификации. Поэтому пустая строка _ тоже увеличивает iota: A=0, B=1, _=2, D=3.
• Пропущенное выражение повторяет предыдущее. MB и GB не «наследуют значение», а повторяют формулу 1 << (10 * iota) со своим iota: 2 и 3. Отсюда 1<<20 и 1<<30. Тут спотыкаются чаще всего.
• iota обнуляется в каждом новом блоке const, а внутри блока считает строки, а не константы: строка X, Y = iota, iota*2 даёт одну спецификацию и один iota.
• Тип наследуется вместе с выражением. Tue и Wed получают тип Weekday, потому что повторяется вся спецификация целиком, включая тип.

Как звучит правильное объяснение на собесе

«Переменные пакета инициализируются не сверху вниз, а по графу зависимостей: сначала то, у чего нет неготовых зависимостей. Здесь это c, потом b, потом a, получится 3, 2, 1. Дальше выполняются все init() в порядке объявления, потом main. Пакеты инициализируются снизу вверх по импортам и по одному разу. iota означает номер строки внутри блока const, поэтому пропуск через _ его увеличивает, а пустая строка повторяет предыдущее выражение целиком, включая тип, но уже с новым значением iota.»

Код

func main() {
    var x any = 1
    var y any = 1.0
    fmt.Println("1)", x == y)

    var s1 any = "go"
    var s2 any = "go"
    fmt.Println("2)", s1 == s2)

    type Pt struct {
        X, Y int
    }
    var p1 any = Pt{1, 2}
    var p2 any = Pt{1, 2}
    fmt.Println("3)", p1 == p2)

    defer func() { fmt.Println("recover:", recover()) }()
    var b1 any = []int{1, 2}
    var b2 any = []int{1, 2}
    fmt.Println("4)", b1 == b2)       // ← компилируется, но падает
}

Почему

Два значения интерфейса равны, если совпадают их динамические типы И равны их динамические значения. Отсюда первый результат: 1 и 1.0 — числа одинаковые, но типы int и float64 разные, значит false. Никакого неявного приведения при сравнении интерфейсов не происходит.

Второй шаг — сравнимость самого динамического типа. Go делит типы на две категории:

Если несравнимый тип написан явно — []int{1} == []int{2}, — это ошибка компиляции: компилятор видит типы и запрещает. Но когда значение спрятано в интерфейсе, статически тип неизвестен: any == any компилируется всегда. Проверка переезжает в рантайм, и там она превращается в панику comparing uncomparable type []int. Именно этот переход «из compile-time в runtime» и есть содержание вопроса.

m := map[any]int{}
m["строка"] = 1                    // ок
m[42] = 2                          // ок
m[[2]int{1, 2}] = 3                // ок: массив сравним
m[[]int{1, 2}] = 4                 // panic: runtime error: hash of unhashable type []int

Чем сравнивать несравнимое

slices.Equal(a, b)                 // слайсы, поэлементно, быстро — Go 1.21+
maps.Equal(m1, m2)                 // мапы
reflect.DeepEqual(x, y)            // что угодно, но медленно и с сюрпризами

reflect.DeepEqual стоит упомянуть вместе с его подвохом: он считает []int(nil) и []int{} разными, хотя обе длины нулевые. В тестах это регулярно приводит к ложным падениям — поэтому в новом коде предпочитают slices.Equal (который их как раз уравнивает) или google/go-cmp.

Как звучит правильное объяснение на собесе

«Интерфейсы равны, когда совпадают и динамический тип, и значение. Поэтому any(1) и any(1.0) не равны — типы разные. А если динамический тип несравним — слайс, мапа или функция, — то сравнение компилируется (статически тип неизвестен), но падает в рантайме с comparing uncomparable type. Та же паника прилетает при использовании такого значения как ключа мапы. Для слайсов и мап есть slices.Equal и maps.Equal; reflect.DeepEqual тоже работает, но медленный и по-разному трактует nil и пустой слайс.»

Код

func main() {
    s := "Привет, Go!"
    fmt.Println("len:", len(s))
    fmt.Println("рун:", utf8.RuneCountInString(s))
    fmt.Printf("s[0] = %v, %c, %q\n", s[0], s[0], s[0])
    fmt.Printf("s[:3] = %q\n", s[:3])

    fmt.Print("range: ")
    for i, r := range s[:12] {
        fmt.Printf("(%d:%c) ", i, r)
    }
    fmt.Println()

    fmt.Print("byte-loop: ")
    for i := 0; i < 6; i++ {
        fmt.Printf("%d ", s[i])
    }
    fmt.Println()

    r := []rune(s)
    fmt.Println("[]rune len:", len(r), "первый:", string(r[0]))
}

Почему

Строка в Go — это неизменяемая последовательность байт, а не символов. Литералы в исходнике хранятся в UTF-8, где кириллическая буква занимает 2 байта, латиница и цифры — 1, а эмодзи — 4. «Привет, Go!» — это 6 кириллических букв (12 байт) + запятая, пробел, G, o, ! (5 байт) = 17 байт при 11 рунах.

• s[i] возвращает byte (uint8), а не символ. s[0] = 208 — это первый из двух байт буквы «П» (0xD0 0x9F). %c честно печатает символ с кодом 208 — Ð.
• Срез строки режет байты. s[:3] захватывает «П» целиком и первый байт от «р» — получается невалидный UTF-8, который %q показывает как "П\xd1".
• range по строке декодирует UTF-8 на лету и выдаёт пары (байтовое смещение, руна). Именно поэтому индексы идут 0, 2, 4, 6… — это не порядковые номера символов, а смещения в байтах. Ловушка: если использовать этот i как «номер символа», всё сломается на первой же кириллице.
• []rune(s) декодирует всю строку в слайс int32 — по 4 байта на руну. Даёт случайный доступ и корректный len, но стоит O(n) времени и O(n) памяти.

Как делать правильно

Когда индексный цикл по байтам уместен: если ты осознанно работаешь с байтами — парсишь ASCII-протокол, ищешь разделитель, считаешь размер для буфера. Тогда это не ошибка, а оптимизация, и об этом стоит сказать вслух: «здесь я иду по байтам намеренно, потому что разделитель — ASCII, а ASCII-байт не может встретиться внутри многобайтовой руны в UTF-8». Последнее — самосинхронизирующееся свойство UTF-8, и знание про него ценится отдельно.

Как звучит правильное объяснение на собесе

«Строка в Go — это байты в UTF-8, поэтому len даёт длину в байтах, а s[i] — байт, а не символ: для кириллицы это половина буквы. range по строке декодирует UTF-8 и выдаёт руну и её байтовое смещение — поэтому индексы идут через один, и использовать их как номер символа нельзя. Если нужен случайный доступ к символам — конвертирую в []rune один раз, помня, что это O(n) памяти. Резать строку можно только по границам рун, иначе получится невалидный UTF-8.»