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

TL;DR#

  • На senior live-coding дают задачи средней сложности: two pointers, sliding window, binary search, BFS/DFS, базовый DP, сортировки.
  • Ценят не «знание трюка», а распознавание паттерна по условию, корректные edge cases, чистый код и проговаривание сложности.
  • Большинство паттернов сводят O(n²) перебор к O(n) / O(n log n) за счёт инварианта (указатели, окно, отсортированность).
  • Всегда: уточнить вход (пустой? отсортирован? дубликаты? отрицательные?), назвать сложность, проверить границы.

Теория#

Паттерн 1: Two Pointers (два указателя)#

Два индекса, движущихся навстречу или в одном направлении. Часто требует отсортированного входа. Заменяет O(n²) на O(n).

Признак: «пара с суммой», «палиндром», «удалить дубликаты на месте», «слить отсортированные».

// Two Sum в ОТСОРТИРОВАННОМ массиве, O(n) время, O(1) память:
func twoSumSorted(a []int, target int) (int, int) {
    l, r := 0, len(a)-1
    for l < r {
        sum := a[l] + a[r]
        switch {
        case sum == target:
            return l, r
        case sum < target:
            l++          // нужно больше — двигаем левый
        default:
            r--          // нужно меньше — двигаем правый
        }
    }
    return -1, -1
}
// Удаление дубликатов из отсортированного слайса на месте, O(n):
func dedup(a []int) []int {
    if len(a) == 0 {
        return a
    }
    slow := 0
    for fast := 1; fast < len(a); fast++ {
        if a[fast] != a[slow] {
            slow++
            a[slow] = a[fast]
        }
    }
    return a[:slow+1]
}

Паттерн 2: Sliding Window (скользящее окно)#

Подмассив/подстрока переменной или фиксированной длины. Расширяем правую границу, сужаем левую при нарушении условия. O(n) вместо O(n²).

Признак: «самая длинная/короткая подстрока с условием», «макс. сумма окна k».

// Длиннейшая подстрока без повторов, O(n):
func longestUnique(s string) int {
    last := make(map[byte]int) // символ -> последний индекс
    best, left := 0, 0
    for right := 0; right < len(s); right++ {
        c := s[right]
        if idx, ok := last[c]; ok && idx >= left {
            left = idx + 1 // сдвигаем окно за дубликат
        }
        last[c] = right
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best
}

Паттерн 3: Binary Search (бинарный поиск)#

Поиск в отсортированном пространстве за O(log n). Не только по массиву — по «пространству ответов» (binary search on answer).

// Ручной бинарный поиск, аккуратно с границами:
func search(a []int, target int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2  // защита от переполнения (важно в C-подобных; в Go тоже хорошая привычка)
        switch {
        case a[mid] == target:
            return mid
        case a[mid] < target:
            lo = mid + 1
        default:
            hi = mid - 1
        }
    }
    return -1
}

// Идиоматично через stdlib:
import "sort"
idx := sort.SearchInts(a, target) // позиция вставки; проверить a[idx]==target
// Go 1.21+:
import "slices"
i, found := slices.BinarySearch(a, target)
_ = i; _ = found

Binary search on answer — когда монотонна функция «подходит ли ответ X»:

// Минимальная скорость, чтобы успеть (псевдо-пример lower bound):
func minFeasible(lo, hi int, ok func(int) bool) int {
    for lo < hi {
        mid := lo + (hi-lo)/2
        if ok(mid) {
            hi = mid       // mid подходит — ищем меньше
        } else {
            lo = mid + 1   // не подходит — больше
        }
    }
    return lo
}

Паттерн 4: BFS / DFS (обходы графов и деревьев)#

BFS — очередь, кратчайший путь по рёбрам в невзвешенном графе, послойный обход. DFS — рекурсия/стек, поиск компонент, циклов, топосортировка, backtracking.

// DFS подсчёт компонент связности, O(V+E):
func countComponents(n int, adj map[int][]int) int {
    visited := make([]bool, n)
    var dfs func(int)
    dfs = func(u int) {
        visited[u] = true
        for _, v := range adj[u] {
            if !visited[v] {
                dfs(v)
            }
        }
    }
    count := 0
    for i := 0; i < n; i++ {
        if !visited[i] {
            count++
            dfs(i)
        }
    }
    return count
}
// BFS кратчайший путь в невзвешенном графе, O(V+E):
func shortestPath(adj map[int][]int, src, dst int) int {
    dist := map[int]int{src: 0}
    queue := []int{src}
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        if u == dst {
            return dist[u]
        }
        for _, v := range adj[u] {
            if _, seen := dist[v]; !seen {
                dist[v] = dist[u] + 1
                queue = append(queue, v)
            }
        }
    }
    return -1
}

Для взвешенного графа — Dijkstra (BFS + min-heap, O((V+E)log V)).

Паттерн 5: Backtracking (перебор с возвратом)#

Систематический перебор с отсечением. Перестановки, подмножества, судоку, N-queens. Сложность экспоненциальная, но с отсечениями приемлема на малых n.

// Все подмножества, O(2ⁿ):
func subsets(nums []int) [][]int {
    var res [][]int
    var cur []int
    var bt func(start int)
    bt = func(start int) {
        res = append(res, append([]int(nil), cur...)) // ВАЖНО: копия!
        for i := start; i < len(nums); i++ {
            cur = append(cur, nums[i])
            bt(i + 1)
            cur = cur[:len(cur)-1] // откат
        }
    }
    bt(0)
    return res
}

Паттерн 6: Динамическое программирование (DP)#

Разбиение на перекрывающиеся подзадачи + мемоизация (top-down) или табуляция (bottom-up). Признак: «сколько способов», «максимум/минимум при выборе», оптимальная подструктура.

// Top-down с мемоизацией, fib O(n):
func fib(n int, memo map[int]int) int {
    if n < 2 {
        return n
    }
    if v, ok := memo[n]; ok {
        return v
    }
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
}

// Bottom-up с оптимизацией памяти до O(1):
func fibBottomUp(n int) int {
    if n < 2 {
        return n
    }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}
// 0/1 Knapsack, O(n·W) время, O(W) память:
func knapsack(weights, values []int, W int) int {
    dp := make([]int, W+1)
    for i := range weights {
        for w := W; w >= weights[i]; w-- { // ОБРАТНЫЙ порядок для 0/1!
            if v := dp[w-weights[i]] + values[i]; v > dp[w] {
                dp[w] = v
            }
        }
    }
    return dp[W]
}

Шаги решения DP: 1) определить состояние, 2) рекуррентное соотношение, 3) базовые случаи, 4) порядок вычисления, 5) (опц.) оптимизация памяти.

Паттерн 7: Сортировки#

На интервью редко просят писать сортировку с нуля, но надо знать классы и уметь применить sort.

АлгоритмВремя (avg/worst)ПамятьСтабильна
Quick sortO(n log n) / O(n²)O(log n)нет
Merge sortO(n log n) / O(n log n)O(n)да
Heap sortO(n log n) / O(n log n)O(1)нет
InsertionO(n²) / O(n²)O(1)да
Counting/RadixO(n+k)O(n+k)да
// Идиоматичная сортировка в Go:
import "slices"
slices.Sort(s)                                   // []int / любой Ordered, Go 1.21+
slices.SortFunc(people, func(a, b Person) int {  // компаратор возвращает -1/0/1
    return cmp.Compare(a.Age, b.Age)
})

import "sort"
sort.Slice(s, func(i, j int) bool { return s[i] < s[j] }) // до 1.21
sort.SliceStable(s, less)                                  // стабильная

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

  • Backtracking без копии — res = append(res, cur) сохранит ссылку на изменяемый слайс; нужна копия append([]T(nil), cur...). Очень частая ошибка.
  • Бинарный поиск, off-by-one — lo<=hi vs lo<hi, mid+1/mid-1/mid. Определитесь с инвариантом (closed [lo,hi] или half-open [lo,hi)) и держитесь его.
  • Sliding window: when to shrink — путают условие сужения окна и обновление ответа. Чётко: расширяем right, восстанавливаем инвариант сужением left, обновляем ответ.
  • DP 0/1 knapsack — обратный порядок внутреннего цикла по весу; прямой даёт unbounded knapsack (предмет берётся многократно).
  • Two pointers требует сортировки — если в условии «можно сортировать» и порядок не важен, это часто намёк на two pointers.
  • DFS глубокая рекурсия — переполнение стека на больших графах; для очень глубоких — итеративный DFS со стеком.
  • sort.Slice не стабильна — для стабильности sort.SliceStable / slices.SortStableFunc.
  • Деление целых — (lo+hi)/2 может переполниться (в Go int 64-битный, но привычка lo+(hi-lo)/2 правильная и переносимая).

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

Задача: Two Sum — вернуть индексы двух чисел с заданной суммой (массив НЕ отсортирован). Разбор: Наивно O(n²). Оптимально — hash map «значение→индекс» за один проход: для каждого x ищем target-x в map. O(n) время, O(n) память.

func twoSum(a []int, t int) (int, int) {
    seen := make(map[int]int, len(a))
    for i, x := range a {
        if j, ok := seen[t-x]; ok {
            return j, i
        }
        seen[x] = i
    }
    return -1, -1
}

Задача: Развернуть односвязный список. Разбор: Итеративно с тремя указателями (prev, cur, next), O(n) время, O(1) память. Рекурсия даёт O(n) стека. Edge: пустой список, один узел. (Код — см. data-structures.md reverse.)

Задача: Проверить валидность скобок ()[]{}. Разбор: Stack. Открывающую кладём, закрывающую сверяем с вершиной. В конце стек должен быть пуст. O(n).

func validParens(s string) bool {
    pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
    var st []byte
    for i := 0; i < len(s); i++ {
        c := s[i]
        if open, isClose := pairs[c]; isClose {
            if len(st) == 0 || st[len(st)-1] != open {
                return false
            }
            st = st[:len(st)-1]
        } else {
            st = append(st, c)
        }
    }
    return len(st) == 0
}

Задача: Найти k-й по величине элемент. Разбор: Min-heap размера k (O(n log k)) или Quickselect (O(n) средн., O(n²) worst). Heap проще и устойчивее на интервью. Обсудить trade-off: full sort O(n log n) проще, но медленнее при k≪n.

Задача: Самая длинная подстрока без повторяющихся символов. Разбор: Sliding window + map последних позиций. O(n). (Код — longestUnique выше.) Edge: пустая строка, все одинаковые, все разные.

Задача: Слить K отсортированных списков. Разбор: Min-heap из голов K списков: извлекаем минимум, добавляем следующий из того же списка. O(N log K), N — всего элементов. Альтернатива — попарное слияние O(N log K).

Задача: Number of Islands (число компонент в сетке). Разбор: Обход сетки, при встрече суши запускаем DFS/BFS, «топим» посещённое. O(rows·cols). Edge: пустая сетка, вся вода/суша.

Задача: Лестница / climbing stairs — сколько способов подняться на n ступеней по 1–2 шага. Разбор: DP, по сути fib: dp[i]=dp[i-1]+dp[i-2]. Оптимизация памяти до O(1). Распознать, что это fib — половина успеха.

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

  • Распознавание паттерна по формулировке без подсказки и обоснование выбора структуры данных.
  • Корректная работа с edge cases до запуска: пустой вход, один элемент, дубликаты, переполнение, отрицательные.
  • Проговаривание сложности по времени и памяти для своего решения и для альтернатив; умение улучшить наивное решение.
  • Чистота кода: понятные имена, отсутствие дублирования, ранние возвраты, инварианты в комментариях там, где неочевидно.
  • Умение написать тесты к решению (table-driven) и обсудить, как бы тестировал.
  • Обсуждение trade-offs между решениями (heap vs quickselect, sort vs hash, рекурсия vs итерация) и масштабируемости (что если данные не влезают в память — внешняя сортировка, стриминг).