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

TL;DR#

  • Go аскетичен: из коробок — слайсы и map. Остальное (container/list, container/ring, container/heap) — в container/*, причём heap это интерфейс над вашим слайсом, а не готовый тип.
  • На live-coding 90% задач решаются слайсом + map. Stack/queue делаются на слайсе руками. Heap — через container/heap.
  • linked list, tree, trie, graph пишут вручную через структуры с указателями. Знать обходы и инварианты.
  • В Go 1.21+ есть slices и maps пакеты (generics) — slices.Sort, slices.Contains, maps.Keys и т.д.
  • Senior должен знать сложности всех операций, когда какая структура нужна, и подводные камни Go (shared backing array, nil map, random iteration).

Теория#

Массивы и слайсы#

Массив [N]T — фиксированный размер, value-тип (копируется при передаче). Редко используется напрямую. Слайс []T — header {ptr, len, cap} поверх массива; основная рабочая структура.

a := [3]int{1, 2, 3}      // массив, размер часть типа
s := []int{1, 2, 3}       // слайс
s = append(s, 4)          // O(1) аморт.
m := make([]int, 0, 100)  // len=0, cap=100 — pre-allocation

// Удаление элемента i (порядок не важен) — O(1):
s[i] = s[len(s)-1]
s = s[:len(s)-1]

// Удаление с сохранением порядка — O(n):
s = append(s[:i], s[i+1:]...)
// или Go 1.21+:
s = slices.Delete(s, i, i+1)
СтруктураКогдаМинусы
[N]T массивфикс. размер, value-семантикакопирование, негибкость
[]T слайспочти всегдаshared backing, реаллокации

Hash map#

map[K]V — встроенная хеш-таблица. Ключ — любой comparable тип (нельзя слайс, map, функцию; можно struct из comparable полей, массив).

m := make(map[string]int)
m["a"] = 1
v, ok := m["a"]      // idiomatic check
delete(m, "a")
for k, v := range m { // ВНИМАНИЕ: порядок случайный
    _ = k; _ = v
}

// map как множество (set):
set := make(map[string]struct{})
set["x"] = struct{}{}      // struct{} занимает 0 байт
_, exists := set["x"]
  • Lookup/insert/delete — O(1) среднее.
  • nil map читать можно (вернёт zero value), писать — panic. var m map[K]V нужно инициализировать через make.
  • Итерация в случайном порядке (намеренно рандомизирована). Нужен порядок — собрать ключи в слайс и отсортировать.

Linked list#

Однонаправленный/двунаправленный список. Вставка/удаление O(1) при наличии указателя; доступ по индексу O(n). Плохая cache locality.

type Node struct {
    Val  int
    Next *Node
}

// Разворот списка — классика live-coding, O(n) время, O(1) память:
func reverse(head *Node) *Node {
    var prev *Node
    for head != nil {
        head.Next, prev, head = prev, head, head.Next
    }
    return prev
}

container/list — готовый двусвязный список (*list.List, *list.Element):

import "container/list"

l := list.New()
e := l.PushBack(10)   // *list.Element
l.PushFront(5)
l.Remove(e)           // O(1)
for el := l.Front(); el != nil; el = el.Next() {
    _ = el.Value      // interface{} / any — нет дженериков!
}

Минус: Value any → накладные расходы и приведения типов. На практике редко нужен; чаще пишут свой типизированный список.

Stack и Queue#

В Go нет отдельных типов — делают на слайсе.

// Stack (LIFO) на слайсе:
var st []int
st = append(st, 1)            // push
top := st[len(st)-1]          // peek
st = st[:len(st)-1]           // pop

// Queue (FIFO) на слайсе — простой вариант (O(1) аморт. amortized, но память течёт):
var q []int
q = append(q, 1)              // enqueue
front := q[0]                 // peek
q = q[1:]                     // dequeue — backing array не освобождается!

Для долгоживущей очереди лучше ring buffer или container/list, чтобы не накапливать «голову» backing array. Для интервью слайс-вариант обычно ОК, но проговорите нюанс.

Heap (container/heap)#

В stdlib нет готовой кучи — есть интерфейс, который вы реализуете над своим слайсом. Реализуете heap.Interface (= sort.Interface + Push/Pop).

import "container/heap"

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] } // min-heap
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    v := old[n-1]
    *h = old[:n-1]
    return v
}

func main() {
    h := &IntHeap{5, 2, 8}
    heap.Init(h)                 // O(n)
    heap.Push(h, 1)              // O(log n)
    min := heap.Pop(h).(int)     // O(log n), вернёт 1
    _ = min
}
  • Push/Pop — O(log n), Init — O(n).
  • Для max-heap инвертируйте Less (h[i] > h[j]).
  • Применение: Dijkstra, top-K, merge K sorted lists, медиана потока.

Tree#

Бинарное дерево / BST / сбалансированные (AVL, red-black). В stdlib готового дерева нет (внутри runtime/map есть, но не экспортирован). Пишут руками.

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

// In-order обход BST даёт отсортированную последовательность:
func inorder(root *TreeNode, out *[]int) {
    if root == nil {
        return
    }
    inorder(root.Left, out)
    *out = append(*out, root.Val)
    inorder(root.Right, out)
}

BST: search/insert/delete — O(h), где h высота; O(log n) для сбалансированного, O(n) для вырожденного. Обходы: pre/in/post-order (DFS) и level-order (BFS через очередь).

Trie (префиксное дерево)#

Для префиксного поиска по строкам. Узел = карта/массив детей.

type Trie struct {
    children map[rune]*Trie
    end      bool
}

func NewTrie() *Trie { return &Trie{children: map[rune]*Trie{}} }

func (t *Trie) Insert(word string) {
    cur := t
    for _, r := range word {       // range по строке даёт руны — важно!
        nxt, ok := cur.children[r]
        if !ok {
            nxt = NewTrie()
            cur.children[r] = nxt
        }
        cur = nxt
    }
    cur.end = true
}

func (t *Trie) Search(word string) bool {
    cur := t
    for _, r := range word {
        nxt, ok := cur.children[r]
        if !ok {
            return false
        }
        cur = nxt
    }
    return cur.end
}

Search/Insert — O(len слова). Применение: автодополнение, словари, IP-роутинг.

Graph#

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

  • Список смежности map[int][]int или [][]int — для разреженных графов, O(V+E) памяти.
  • Матрица смежности [][]bool — для плотных, O(V²) памяти, O(1) проверка ребра.
type Graph struct {
    adj map[int][]int
}

func (g *Graph) AddEdge(u, v int) {
    g.adj[u] = append(g.adj[u], v)
    g.adj[v] = append(g.adj[v], u) // для неориентированного
}

// BFS — кратчайший путь по числу рёбер, O(V+E):
func bfs(g *Graph, start int) []int {
    visited := map[int]bool{start: true}
    queue := []int{start}
    var order []int
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)
        for _, n := range g.adj[node] {
            if !visited[n] {
                visited[n] = true
                queue = append(queue, n)
            }
        }
    }
    return order
}

Что есть в стандартной библиотеке (сводка)#

СтруктураВ stdlib?Пакет
Slice, Mapда, встроеныbuiltin
Двусвязный списокдаcontainer/list
Кольцевой буфердаcontainer/ring
Heap (интерфейс)даcontainer/heap
Stack / Queueнетделать на слайсе
Tree / BSTнетвручную
Trieнетвручную
Graphнетвручную (map/slice)
Setнетmap[T]struct{}
Утилиты для slice/mapда (1.21+)slices, maps

container/ring — кольцевой список фиксированного размера, для циклических буферов:

import "container/ring"
r := ring.New(3)          // 3 элемента в кольце
for i := 0; i < 3; i++ {
    r.Value = i
    r = r.Next()
}
r.Do(func(v any) { _ = v }) // обход всех

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

  • Slice shared backing array — s[a:b] разделяет память; append может затереть «соседей». Используйте slices.Clone для независимой копии.
  • Queue через q = q[1:] не освобождает голову backing array — память растёт в долгоживущей очереди. Для прод-кода — ring buffer или периодический re-slice с копированием.
  • container/heap — это не тип, а интерфейс. Частая ошибка кандидата: искать heap.New(). Нужно реализовать 5 методов, причём Push/Pop на указателе.
  • Push/Pop у heap не вызывают напрямую — это методы интерфейса; пользователь зовёт heap.Push(h, x) / heap.Pop(h), которые поддерживают инвариант кучи.
  • nil map panic при записи — var m map[K]V; m[k]=v падает. Всегда make.
  • container/list и ring хранят any — нет дженериков, накладные расходы и runtime-приведения. В новом коде чаще свой типизированный вариант.
  • range по строке даёт руны (rune), не байты — важно для trie/строковых задач с UTF-8. for i := range s даёт байтовые индексы.
  • map итерация рандомизирована — нельзя полагаться на порядок; для детерминизма сортируйте ключи.

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

В: Как реализовать stack и queue в Go? О: Оба на слайсе. Stack: append для push, s[:len-1] для pop, s[len-1] для peek. Queue: append для enqueue, q[0] peek, q[1:] dequeue. Нюанс очереди — q[1:] не освобождает backing array, для долгоживущей очереди лучше ring buffer или container/list.

В: Почему в Go нет готового Set? О: Идиома — map[T]struct{}. struct{} занимает 0 байт, так что это эффективно. map[T]bool тоже работает, но тратит память на значения и допускает неоднозначность (false vs отсутствие).

В: Как использовать container/heap? Что нужно реализовать? О: Это интерфейс, не тип. Реализуете heap.Interface: Len, Less (определяет min/max), Swap (это sort.Interface) плюс Push(any) и Pop() any на указателе. Затем heap.Init, heap.Push(h,x), heap.Pop(h). Push/Pop — O(log n).

В: Список смежности vs матрица смежности — когда что? О: Список (map[int][]int / [][]int) — для разреженных графов, память O(V+E), обход соседей эффективен. Матрица ([][]bool) — для плотных, O(V²) памяти, но O(1) проверка наличия ребра. На практике чаще список.

В: В чём опасность slicing’а в Go? О: b := a[i:j] разделяет backing array с a. Мутации b видны в a; append(b, x) при наличии cap затрёт элементы a; маленький под-слайс удерживает весь большой массив в памяти. Решение — slices.Clone(b) или append([]T(nil), b...).

В: Как обойти дерево в ширину и в глубину? О: DFS — рекурсией (pre/in/post-order) или явным стеком; память O(h). BFS — очередью (level-order); память O(ширины уровня), даёт кратчайший путь по рёбрам в невзвешенном графе.

В: Зачем нужен trie, если есть map? О: Trie даёт O(len) поиск по префиксу и перечисление всех слов с данным префиксом (автодополнение), чего map не умеет эффективно. Map даёт только точный lookup. Trie разделяет общие префиксы — экономит память на больших словарях с общими началами.

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

  • Знание точных сложностей всех операций и умение выбрать структуру под задачу (top-K → heap, префиксы → trie, кратчайший путь → BFS/Dijkstra).
  • Понимание memory layout: cache locality слайса vs указательный связный список; почему слайс почти всегда быстрее на практике.
  • Реализация container/heap с нуля без подсказок, понимание sift-up/sift-down.
  • Подводные камни Go: shared backing array, nil map, random iteration, рост памяти у naive queue.
  • Когда брать stdlib (container/list, heap), а когда писать своё (типобезопасность, отсутствие boxing в any).
  • Альтернативные представления и trade-offs (graph: list vs matrix; set: map vs bitset для плотных целочисленных множеств).