Идея

В лоб получаются два вложенных цикла, 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 секции или разделяются другими строками. Аллокаций при этом до двух: для строки до 32 рун компилятор отдаёт под []rune буфер на стеке, и в куче выделяется только результат. Попытка []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 при положительных числах берётся окном переменной длины: расширяем правым, сжимаем левым, пока сумма достаточна.
• Среднее по окну / скользящий максимум. Для максимума нужна монотонная дека на слайсе, тоже 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+1), это тот же порядок, что и сам fib(n), а он растёт как φⁿ/√5, где φ ≈ 1.618. Отсюда и O(1.618ⁿ): fib(50) наивно это порядка 4·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) вниз.
• «Найди наименьшего общего предка». В 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] не копирует байты, а делает новый заголовок на тот же массив, отсюда, кстати, и эффект «маленькая подстрока удерживает в памяти большой буфер».
• «Почему строки неизменяемы?» Это позволяет свободно копировать заголовок, класть строки в ключи мапы и не бояться гонок при передаче между горутинами.