Модуль: Алгоритмы · Уровень: Middle+/Senior

TL;DR#

  • На Go-интервью ценят идиоматичность: slices/maps/sort, map[T]struct{} как set, multiple return + comma-ok, ранние возвраты.
  • Главные ловушки: range копирует значение, shared backing array при slicing, байты vs руны в строках, nil map panic, захват переменной цикла в горутине/замыкании.
  • Знать stdlib: sort, slices (1.21+), maps, strings, strconv, container/heap. Не изобретать велосипед.
  • Senior отличают: чистый код, обработка edge cases, понимание аллокаций/escape, написанные тесты (table-driven), проговаривание сложности.

Теория#

Идиоматичные приёмы для алгоритмов#

// comma-ok для map и type assertion:
if v, ok := m[key]; ok { _ = v }

// multiple return — норма, не "костыль":
func minmax(a []int) (mn, mx int) { /* ... */ return }

// set через map[T]struct{} (0 байт на значение):
seen := map[int]struct{}{}
seen[x] = struct{}{}
_, ok := seen[x]

// swap без temp:
a[i], a[j] = a[j], a[i]

// ранний возврат вместо вложенности:
if len(a) == 0 { return nil }

Слайсы: то, что спросят#

s := make([]int, 0, n)          // pre-alloc cap — меньше реаллокаций
s = append(s, vals...)          // распаковка слайса
b := slices.Clone(s)            // независимая копия (Go 1.21+)
s = slices.Delete(s, i, i+1)    // удаление с сохранением порядка
idx := slices.Index(s, x)       // поиск, -1 если нет
ok := slices.Contains(s, x)
slices.Reverse(s)
mx := slices.Max(s)

// 2D-слайс — правильная инициализация (каждый ряд отдельно!):
grid := make([][]int, rows)
for i := range grid {
    grid[i] = make([]int, cols)
}

Map: то, что спросят#

m := make(map[string]int, hint) // hint = ожидаемый размер
m[k]++                          // работает даже если k нет (zero value 0)
delete(m, k)
v := m[absent]                  // zero value, без panic (для ЧТЕНИЯ)

// детерминированный обход (map рандомизирован!):
keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
slices.Sort(keys)
for _, k := range keys { _ = m[k] }

// maps пакет (1.21+):
import "maps"
clone := maps.Clone(m)
for k := range maps.Keys(m) { _ = k } // iterator (1.23+)

Строки и руны (UTF-8!)#

Строка в Go — неизменяемая последовательность байтов (UTF-8). Индексация s[i] даёт байт, range даёт руны.

s := "héllo"
len(s)                  // байты (может быть > числа символов!)
s[0]                    // byte
for i, r := range s {   // i — байтовый индекс, r — rune
    _ = i; _ = r
}
runes := []rune(s)      // конвертация в руны: теперь len = число символов
n := utf8.RuneCountInString(s) // число рун без аллокации

// Разворот строки с учётом Unicode:
func reverseStr(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)
}

// Эффективная конкатенация (вместо += в цикле — O(n²)!):
var b strings.Builder
b.Grow(estimatedSize)   // pre-alloc
for _, p := range parts {
    b.WriteString(p)
}
result := b.String()

Пакет sort и slices (сортировка)#

// Go 1.21+ — предпочтительно:
slices.Sort(nums)                              // Ordered
slices.SortFunc(xs, func(a, b T) int {         // -1 / 0 / +1
    return cmp.Compare(a.Key, b.Key)
})
slices.SortStableFunc(xs, cmpFn)               // стабильная

// До 1.21 / для совместимости:
sort.Ints(nums)
sort.Strings(strs)
sort.Slice(xs, func(i, j int) bool { return xs[i].Key < xs[j].Key }) // less
sort.SliceStable(xs, less)
sort.Sort(myInterface)                         // полный sort.Interface

// Сортировка по нескольким полям:
slices.SortFunc(people, func(a, b Person) int {
    if c := cmp.Compare(a.Age, b.Age); c != 0 {
        return c
    }
    return cmp.Compare(a.Name, b.Name) // tie-breaker
})

sort.Slice использует pdqsort (introsort), O(n log n), нестабильна. Компаратор less(i,j) возвращает bool, а SortFunc — int (это путают).

Числа и конвертации#

import "strconv"
n, err := strconv.Atoi("42")
s := strconv.Itoa(42)
f, _ := strconv.ParseFloat("3.14", 64)

import "math"
math.MaxInt, math.MinInt        // границы (Go 1.17+)
math.Abs(x)                      // только float64

// целочисленный max/min (Go 1.21+ встроенные!):
m := max(a, b)
n := min(x, y, z)

Подводные камни / gotchas#

  • range копирует элемент. for _, v := range s { v.X = 1 } меняет копию, не оригинал. Чтобы мутировать — s[i].X = 1 по индексу.
  • Захват переменной цикла. До Go 1.22 for _, v := range s { go func(){ use(v) }() } захватывал одну общую v. В 1.22+ переменная цикла новая на каждой итерации — но на старых версиях / в собеседовании проговорите явно.
  • Shared backing array. b := a[1:3]; b = append(b, x) может затереть a. slices.Clone для изоляции.
  • nil map panic. var m map[K]V; m[k]=v → panic. Чтение из nil map безопасно. Всегда make.
  • Байты vs руны. len("привет") = 12, не 6. s[i] — байт, не символ. Для строковых алгоритмов часто нужен []rune.
  • append к чужому слайсу как параметру — может либо повлиять на вызывающего (если был cap), либо нет (если реаллокация). Не полагайтесь — возвращайте результат append.
  • Сравнение через == — структуры из comparable полей сравнимы; слайсы/map/функции — нет (только с nil). Для слайсов — slices.Equal.
  • Integer overflow молчаливый — int переполняется без паники. В задачах с произведениями/суммами больших чисел держите в уме.
  • defer в цикле копит до выхода из функции — в горячем цикле это утечка/тормоза.
  • Деление на ноль для int — panic; для float — Inf/NaN.

Вопросы / задачи на собеседовании#

В: В чём разница s[i] и range по строке? О: s[i] возвращает байт (byte/uint8); строка — это UTF-8 байты. range декодирует UTF-8 и выдаёт руны (rune/int32) вместе с байтовым индексом начала символа. Для алгоритмов с многобайтовыми символами работайте через []rune.

В: Почему for _, v := range items { go process(v) } могло работать неправильно? О: До Go 1.22 переменная цикла v переиспользовалась — все горутины видели одно (последнее) значение. Фикс: передать параметром go func(v T){...}(v) или v := v. В Go 1.22+ это исправлено на уровне языка, но знание истории — признак опыта.

В: Как сделать множество (set) в Go? О: map[T]struct{} — struct{} занимает 0 байт. seen[x]=struct{}{}, проверка _, ok := seen[x]. map[T]bool проще читается, но тратит память и допускает двусмысленность false vs отсутствие.

В: Разница sort.Slice и slices.SortFunc? О: sort.Slice(less func(i,j) bool) — индексы и предикат «меньше», рефлексия внутри, есть с Go 1.8. slices.SortFunc(cmp func(a,b) int) — дженерик, компаратор возвращает -1/0/1, типобезопасен и быстрее, с Go 1.21. Обе O(n log n), нестабильны (есть *Stable варианты).

В: Как избежать O(n²) при сборке большой строки? О: strings.Builder с Grow для пред-аллокации и WriteString. Конкатенация += в цикле каждый раз создаёт новую строку (строки иммутабельны) → O(n²). Для []byte — bytes.Buffer или append к слайсу.

В: Что вернёт чтение из nil map? А запись? О: Чтение — zero value соответствующего типа, без паники (удобно для счётчиков и т.п.). Запись в nil map — panic. Поэтому map всегда инициализируют через make перед записью.

В: Как написать table-driven тест для алгоритма? О: Слайс структур {name, input, want}, цикл с t.Run(tc.name, ...), сравнение reflect.DeepEqual или slices.Equal. Покрыть edge cases: пустой вход, один элемент, дубликаты, граничные значения.

func TestTwoSum(t *testing.T) {
    tests := []struct {
        name        string
        in          []int
        target      int
        wantI, wantJ int
    }{
        {"basic", []int{2, 7, 11}, 9, 0, 1},
        {"empty", nil, 5, -1, -1},
        {"no pair", []int{1, 2}, 100, -1, -1},
    }
    for _, tc := range tests {
        t.Run(tc.name, func(t *testing.T) {
            i, j := twoSum(tc.in, tc.target)
            if i != tc.wantI || j != tc.wantJ {
                t.Errorf("got (%d,%d), want (%d,%d)", i, j, tc.wantI, tc.wantJ)
            }
        })
    }
}

В: Как вернуть детерминированный обход map? О: Map итерируется в случайном порядке намеренно. Собрать ключи в слайс, отсортировать (slices.Sort), обойти слайс. Полагаться на порядок итерации map нельзя никогда.

На что копают на senior+#

  • Идиоматичность, а не «Go как Java/Python»: использование stdlib (slices, maps, sort, strings.Builder), comma-ok, multiple return, ранние возвраты.
  • Понимание value vs reference семантики: что копируется (range, передача структур, массивы), что разделяется (слайсы, map).
  • Аллокации и производительность: pre-sizing, escape analysis, избегание O(n²) на строках, осознанные heap/stack решения; умение подкрепить бенчмарком.
  • Edge cases и устойчивость: nil, пустой вход, переполнение, Unicode — обрабатываются до того, как спросят.
  • Тестируемость: table-driven тесты, чистые функции, продумывание граничных случаев как часть решения.
  • Чистый код под давлением: понятные имена, маленькие функции, отсутствие дублирования даже в live-coding; проговаривание решения вслух и сложности.
  • Знание тонкостей версий (loop var в 1.22, generics-утилиты в 1.21) — показывает, что человек следит за языком.
Backward Структуры данных в Go Behavioral Forward