Senior Go Interview Prep

- Core Go: https://go.vbloher.org/docs/01-core-go/
- Механика defer в Go: https://go.vbloher.org/docs/01-core-go/defer/
- Встраивание структур и интерфейсов (Embedding): https://go.vbloher.org/docs/01-core-go/embedding/
- Ошибки в Go: error, wrapping, errors.Is/As/Join: https://go.vbloher.org/docs/01-core-go/errors/
- Дженерики в Go (1.18+): https://go.vbloher.org/docs/01-core-go/generics/
- Интерфейсы в Go: https://go.vbloher.org/docs/01-core-go/interfaces/
- Устройство map в Go: https://go.vbloher.org/docs/01-core-go/maps/
- panic / recover: механика, раскрутка стека и runtime-паники: https://go.vbloher.org/docs/01-core-go/panic-recover/
- Указатели в Go: https://go.vbloher.org/docs/01-core-go/pointers/
- Рефлексия в Go (reflect): https://go.vbloher.org/docs/01-core-go/reflection/
- Внутреннее устройство слайсов в Go: https://go.vbloher.org/docs/01-core-go/slices/
- Строки, руны и байты в Go: https://go.vbloher.org/docs/01-core-go/strings-runes-bytes/
- Система типов Go: defined types, alignment, memory layout: https://go.vbloher.org/docs/01-core-go/type-system/
- Concurrency: https://go.vbloher.org/docs/02-concurrency/
- sync/atomic: https://go.vbloher.org/docs/02-concurrency/atomic/
- Буферизованные vs небуферизованные каналы: https://go.vbloher.org/docs/02-concurrency/buffered-unbuffered/
- Канал vs Mutex: когда что выбрать: https://go.vbloher.org/docs/02-concurrency/channel-vs-mutex/
- Каналы: устройство hchan: https://go.vbloher.org/docs/02-concurrency/channels/
- Утечки горутин, дедлоки, livelock, starvation: https://go.vbloher.org/docs/02-concurrency/common-leaks-deadlocks/
- sync.Cond: https://go.vbloher.org/docs/02-concurrency/cond/
- context: https://go.vbloher.org/docs/02-concurrency/context/
- Горутины: жизненный цикл, стоимость, стек: https://go.vbloher.org/docs/02-concurrency/goroutines-lifecycle/
- sync.Mutex и sync.RWMutex: https://go.vbloher.org/docs/02-concurrency/mutex-rwmutex/
- sync.Once: https://go.vbloher.org/docs/02-concurrency/once/
- Паттерны конкурентности: https://go.vbloher.org/docs/02-concurrency/patterns/
- Race Detector (гонки данных и -race): https://go.vbloher.org/docs/02-concurrency/race-detector/
- Планировщик GMP: https://go.vbloher.org/docs/02-concurrency/scheduler-gmp/
- select: https://go.vbloher.org/docs/02-concurrency/select/
- sync.WaitGroup: https://go.vbloher.org/docs/02-concurrency/waitgroup/
- Runtime и память: https://go.vbloher.org/docs/03-runtime-memory/
- Паттерны аллокаций и снижение давления на GC: https://go.vbloher.org/docs/03-runtime-memory/allocation-patterns/
- Escape Analysis: когда переменная убегает в кучу: https://go.vbloher.org/docs/03-runtime-memory/escape-analysis/
- Сборщик мусора Go: concurrent tri-color mark-sweep: https://go.vbloher.org/docs/03-runtime-memory/gc/
- Тюнинг GC: GOGC и GOMEMLIMIT: https://go.vbloher.org/docs/03-runtime-memory/gogc-gomemlimit/
- GOMAXPROCS: параллелизм планировщика и проблема контейнеров: https://go.vbloher.org/docs/03-runtime-memory/gomaxprocs/
- Утечки горутин (goroutine leaks): https://go.vbloher.org/docs/03-runtime-memory/goroutine-leaks/
- Утечки памяти в Go (несмотря на GC): https://go.vbloher.org/docs/03-runtime-memory/memory-leaks/
- Модель памяти Go (Go Memory Model): happens-before и синхронизация: https://go.vbloher.org/docs/03-runtime-memory/memory-model/
- pprof: профилирование CPU, памяти и блокировок в Go: https://go.vbloher.org/docs/03-runtime-memory/pprof/
- Execution Tracer и runtime/trace: тайминги вместо агрегатов: https://go.vbloher.org/docs/03-runtime-memory/runtime-tracing/
- Стек vs Куча: где живут данные в Go: https://go.vbloher.org/docs/03-runtime-memory/stack-vs-heap/
- Тестирование: https://go.vbloher.org/docs/04-testing/
- testify, assert/require и golden files: https://go.vbloher.org/docs/04-testing/assertions-testify/
- Бенчмарки в Go: https://go.vbloher.org/docs/04-testing/benchmarks/
- Покрытие, -race и флаки-тесты: https://go.vbloher.org/docs/04-testing/coverage-race/
- Нативный fuzzing в Go (1.18+): https://go.vbloher.org/docs/04-testing/fuzzing/
- Интеграционные тесты, testcontainers-go, TestMain: https://go.vbloher.org/docs/04-testing/integration-testcontainers/
- Моки, стабы и тестируемость: https://go.vbloher.org/docs/04-testing/mocks/
- Table-driven тесты, subtests и параллельность: https://go.vbloher.org/docs/04-testing/table-driven/
- Backend: https://go.vbloher.org/docs/05-backend/
- Аутентификация и авторизация: AuthN/AuthZ, сессии vs токены, RBAC/ABAC, API keys, mTLS, секреты: https://go.vbloher.org/docs/05-backend/auth-authz/
- Graceful Shutdown HTTP/gRPC сервера в Go: https://go.vbloher.org/docs/05-backend/graceful-shutdown/
- gRPC: типы RPC, интерсепторы, контекст, метаданные, error model: https://go.vbloher.org/docs/05-backend/grpc/
- JWT (JSON Web Token): https://go.vbloher.org/docs/05-backend/jwt/
- Middleware-паттерн в Go: https://go.vbloher.org/docs/05-backend/middleware/
- net/http: Server, Handler, ServeMux, таймауты, Client и контекст: https://go.vbloher.org/docs/05-backend/net-http/
- OAuth2: роли, grant types, OIDC, токены и типовые ошибки: https://go.vbloher.org/docs/05-backend/oauth2/
- OpenAPI/Swagger, code generation, contract-first vs code-first, валидация: https://go.vbloher.org/docs/05-backend/openapi/
- Protocol Buffers: схемы, wire format, эволюция и совместимость: https://go.vbloher.org/docs/05-backend/protobuf/
- REST: принципы, версионирование, идемпотентность, статусы, пагинация, ошибки: https://go.vbloher.org/docs/05-backend/rest/
- Сети и протоколы: https://go.vbloher.org/docs/06-networking/
- Пулы соединений: http.Transport, БД, утечки: https://go.vbloher.org/docs/06-networking/connection-pooling/
- DNS: записи, резолвинг, кэширование, DNS в Go: https://go.vbloher.org/docs/06-networking/dns/
- Версии HTTP: 1.1, 2, 3: https://go.vbloher.org/docs/06-networking/http-versions/
- TCP/IP: модель, транспорт и что важно бэкендеру: https://go.vbloher.org/docs/06-networking/tcp-ip/
- TLS: handshake, сертификаты, mTLS, производительность: https://go.vbloher.org/docs/06-networking/tls/
- UDP и надёжность поверх UDP: https://go.vbloher.org/docs/06-networking/udp/
- WebSocket: upgrade, фреймы, масштабирование: https://go.vbloher.org/docs/06-networking/websocket/
- Базы данных: https://go.vbloher.org/docs/07-databases/
- Пул соединений к PostgreSQL в Go: database/sql, pgx, pgxpool, PgBouncer: https://go.vbloher.org/docs/07-databases/connection-pooling-pgx/
- Взаимоблокировки (Deadlocks) в PostgreSQL: https://go.vbloher.org/docs/07-databases/deadlocks/
- Индексы в PostgreSQL: https://go.vbloher.org/docs/07-databases/indexes/
- Уровни изоляции транзакций в PostgreSQL: https://go.vbloher.org/docs/07-databases/isolation-levels/
- MVCC в PostgreSQL: версии строк, видимость, VACUUM и bloat: https://go.vbloher.org/docs/07-databases/mvcc/
- Обзор NoSQL и Redis: https://go.vbloher.org/docs/07-databases/nosql-redis/
- Партиционирование таблиц в PostgreSQL: https://go.vbloher.org/docs/07-databases/partitioning/
- Архитектура PostgreSQL: https://go.vbloher.org/docs/07-databases/postgresql-architecture/
- Планирование и оптимизация запросов в PostgreSQL: https://go.vbloher.org/docs/07-databases/query-planning/
- Репликация в PostgreSQL: https://go.vbloher.org/docs/07-databases/replication/
- Шардирование (горизонтальное масштабирование): https://go.vbloher.org/docs/07-databases/sharding/
- Транзакции в PostgreSQL и Go (database/sql, pgx): https://go.vbloher.org/docs/07-databases/transactions/
- Распределённые системы: https://go.vbloher.org/docs/08-distributed-systems/
- CAP теорема: https://go.vbloher.org/docs/08-distributed-systems/cap-theorem/
- Circuit Breaker: https://go.vbloher.org/docs/08-distributed-systems/circuit-breaker/
- Консенсус и Raft: репликация состояния в присутствии отказов: https://go.vbloher.org/docs/08-distributed-systems/consensus-raft/
- Модели согласованности: https://go.vbloher.org/docs/08-distributed-systems/consistency/
- Гарантии доставки сообщений: at-most-once / at-least-once / exactly-once: https://go.vbloher.org/docs/08-distributed-systems/delivery-guarantees/
- Eventual Consistency: https://go.vbloher.org/docs/08-distributed-systems/eventual-consistency/
- Идемпотентность в распределённых системах: https://go.vbloher.org/docs/08-distributed-systems/idempotency/
- Apache Kafka: https://go.vbloher.org/docs/08-distributed-systems/kafka/
- Transactional Outbox: https://go.vbloher.org/docs/08-distributed-systems/outbox/
- RabbitMQ: AMQP 0-9-1, маршрутизация, надёжность доставки и сравнение с Kafka: https://go.vbloher.org/docs/08-distributed-systems/rabbitmq/
- Ретраи: backoff, jitter, budgets и идемпотентность: https://go.vbloher.org/docs/08-distributed-systems/retries/
- Saga Pattern: https://go.vbloher.org/docs/08-distributed-systems/saga/
- Observability: https://go.vbloher.org/docs/09-observability/
- Grafana: https://go.vbloher.org/docs/09-observability/grafana/
- Метрики: RED, USE, Golden Signals: https://go.vbloher.org/docs/09-observability/metrics/
- OpenTelemetry: https://go.vbloher.org/docs/09-observability/opentelemetry/
- Prometheus: https://go.vbloher.org/docs/09-observability/prometheus/
- SLI / SLO / SLA: https://go.vbloher.org/docs/09-observability/slo-sli/
- Структурированное логирование (slog): https://go.vbloher.org/docs/09-observability/structured-logging/
- Distributed Tracing: https://go.vbloher.org/docs/09-observability/tracing/
- System Design: https://go.vbloher.org/docs/10-system-design/
- Analytics Pipeline: https://go.vbloher.org/docs/10-system-design/analytics-pipeline/
- Chat System: https://go.vbloher.org/docs/10-system-design/chat/
- Фреймворк System Design интервью: https://go.vbloher.org/docs/10-system-design/framework/
- Notification Service: https://go.vbloher.org/docs/10-system-design/notification-service/
- Order Service: https://go.vbloher.org/docs/10-system-design/order-service/
- Payment Service: https://go.vbloher.org/docs/10-system-design/payment-service/
- Rate Limiter: https://go.vbloher.org/docs/10-system-design/rate-limiter/
- URL Shortener: https://go.vbloher.org/docs/10-system-design/url-shortener/
- DevOps: https://go.vbloher.org/docs/11-devops/
- CI/CD: пайплайны, стадии, стратегии деплоя: https://go.vbloher.org/docs/11-devops/cicd/
- Облака (AWS / GCP) для бэкендера: https://go.vbloher.org/docs/11-devops/cloud-aws-gcp/
- Docker для Go-разработчика: https://go.vbloher.org/docs/11-devops/docker/
- GitHub Actions и GitLab CI: https://go.vbloher.org/docs/11-devops/github-gitlab-ci/
- Kubernetes для Go-разработчика: https://go.vbloher.org/docs/11-devops/kubernetes/
- Terraform / Infrastructure as Code: https://go.vbloher.org/docs/11-devops/terraform/
- Алгоритмы: https://go.vbloher.org/docs/12-algorithms/
- Типовые алгоритмические задачи и паттерны: https://go.vbloher.org/docs/12-algorithms/common-problems/
- Асимптотическая сложность (Big-O): https://go.vbloher.org/docs/12-algorithms/complexity/
- Структуры данных в Go: https://go.vbloher.org/docs/12-algorithms/data-structures/
- Специфика live-coding на Go: https://go.vbloher.org/docs/12-algorithms/go-specifics/
- Behavioral: https://go.vbloher.org/docs/13-behavioral/
- Конфликты, разногласия и работа со стейкхолдерами: https://go.vbloher.org/docs/13-behavioral/conflicts/
- Как проходит senior-интервью: этапы, оценка, оффер: https://go.vbloher.org/docs/13-behavioral/interview-flow/
- Лидерство и менторство: https://go.vbloher.org/docs/13-behavioral/leadership-mentoring/
- Типовые поведенческие вопросы для Senior: https://go.vbloher.org/docs/13-behavioral/senior-questions/


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

## TL;DR
- **Big-O** описывает асимптотический рост ресурсов (время/память) при росте входа `n`, отбрасывая константы и младшие члены.
- Оцениваем **отдельно время и память** — оптимизация одного часто ухудшает другое (trade-off).
- **Амортизированная сложность** — средняя стоимость операции на длинной серии (классика: `append` к слайсу = O(1) амортизированно).
- В Go важно знать: `append` может реаллоцировать и копировать (амортизированно O(1)), доступ к map — O(1) в среднем, сортировка `sort.Slice` — O(n log n).
- На senior ждут не «знаю определение», а умения **вывести сложность по коду**, заметить скрытые копирования и аллокации, обсудить worst/average/best case.

## Теория

### Что такое Big-O формально
O(f(n)) — множество функций, ограниченных сверху `c·f(n)` начиная с некоторого `n₀`. На практике: «как растёт ресурс при стремлении n к бесконечности».

Семейство нотаций:
- **O (Big-O)** — верхняя граница (worst case или просто «не хуже чем»).
- **Ω (Omega)** — нижняя граница (не лучше чем).
- **Θ (Theta)** — точная граница (и сверху, и снизу).

На интервью обычно говорят «O», подразумевая Θ для worst case. Будьте готовы уточнить, о каком случае идёт речь.

### Иерархия сложностей (от лучшей к худшей)

| Нотация | Название | Пример |
|---|---|---|
| O(1) | константа | доступ по индексу, map lookup (avg) |
| O(log n) | логарифм | бинарный поиск, высота сбалансированного дерева |
| O(n) | линейная | один проход по слайсу |
| O(n log n) | линейно-логарифм. | эффективные сортировки, divide&conquer |
| O(n²) | квадрат | вложенные циклы, наивная сортировка |
| O(n³) | куб | тройные циклы, наивное умножение матриц |
| O(2ⁿ) | экспонента | перебор подмножеств, наивный fib |
| O(n!) | факториал | перебор перестановок (TSP brute force) |

Ориентир по `n` для лимита ~1 сек (~10⁸ операций):
- n ≤ 10–12 → допустим O(n!), O(2ⁿ)
- n ≤ 20–25 → O(2ⁿ)
- n ≤ 500 → O(n³)
- n ≤ 10⁴ → O(n²)
- n ≤ 10⁶ → O(n log n)
- n ≤ 10⁸ → O(n)

### Как оценивать сложность по коду
1. Последовательные блоки складываются → берём максимум: `O(n) + O(n log n) = O(n log n)`.
2. Вложенные циклы перемножаются: цикл по n внутри цикла по n → O(n²).
3. Рекурсия — через **рекуррентное соотношение** и Master Theorem.

**Master Theorem** для `T(n) = a·T(n/b) + f(n)`:
- merge sort: `T(n) = 2T(n/2) + O(n)` → O(n log n)
- бинарный поиск: `T(n) = T(n/2) + O(1)` → O(log n)

```go
// O(n²): для каждого элемента — проход по остатку
func hasDuplicateNaive(a []int) bool {
    for i := 0; i < len(a); i++ {
        for j := i + 1; j < len(a); j++ {
            if a[i] == a[j] {
                return true
            }
        }
    }
    return false
}

// O(n) время, O(n) память: размен памяти на скорость
func hasDuplicate(a []int) bool {
    seen := make(map[int]struct{}, len(a)) // pre-size — меньше реаллокаций
    for _, v := range a {
        if _, ok := seen[v]; ok {
            return true
        }
        seen[v] = struct{}{}
    }
    return false
}
```

### Время vs Память (trade-off)
Часто можно ускорить алгоритм ценой памяти (мемоизация, хеш-таблицы) или сэкономить память ценой времени (in-place, пересчёт). На интервью **проговаривайте обе оси** — это признак зрелости.

Пример: подсчёт сложности по памяти учитывает **только дополнительную** память (auxiliary space), не вход. In-place сортировка слайса — O(1) доп. памяти (хотя `sort.Slice` использует стек рекурсии O(log n)).

### Амортизированная сложность
Усреднённая стоимость операции по длинной последовательности, даже если отдельные операции дорогие. Не то же самое, что average-case (там усредняем по входам, тут — по времени серии).

**Классика — `append`:** слайс при переполнении capacity реаллоцирует новый массив (обычно ×2 для малых, ×1.25 для больших) и копирует элементы. Один append иногда O(n), но суммарно n аппендов = O(n), то есть O(1) амортизированно. Метод анализа — банковский (накапливаем «кредит» на дешёвых операциях).

```go
s := make([]int, 0)        // cap=0
for i := 0; i < 1000; i++ {
    s = append(s, i)       // изредка реаллокация+копирование, в среднем O(1)
}
// Если знаем размер заранее — убираем реаллокации:
s2 := make([]int, 0, 1000) // cap=1000, ни одной реаллокации
```

### Типичные сложности операций в Go

**Slice `[]T`:**

| Операция | Сложность | Заметки |
|---|---|---|
| доступ/запись по индексу | O(1) | |
| `len`, `cap` | O(1) | |
| `append` (в конец) | O(1) аморт. | реаллокация при росте cap |
| `append` с реаллокацией | O(n) | разовое копирование |
| вставка/удаление в середине | O(n) | сдвиг `copy` |
| `s[a:b]` (slicing) | O(1) | разделяет backing array! |
| поиск элемента | O(n) | линейный |
| `slices.Contains` | O(n) | |
| копирование `copy` | O(n) | |

**Map `map[K]V`:**

| Операция | Сложность | Заметки |
|---|---|---|
| lookup `m[k]` | O(1) среднее, O(n) worst | worst при коллизиях |
| insert / update | O(1) аморт. среднее | рост таблицы — рехеш |
| delete | O(1) среднее | память не возвращается ОС сразу |
| итерация `range` | O(n) | порядок случайный! |

Map не даёт гарантий worst-case O(1) (в отличие от сбалансированного дерева O(log n)), но на практике коллизии редки.

**Прочее stdlib:**

| Операция | Сложность |
|---|---|
| `sort.Slice` / `slices.Sort` | O(n log n) время, O(log n) стек (pdqsort) |
| `sort.Search` (бинарный) | O(log n) |
| `container/heap` Push/Pop | O(log n) |
| `container/list` insert/remove | O(1) (есть указатель на элемент) |
| `strings.Builder` запись | O(1) аморт. |
| конкатенация строк `+` в цикле | O(n²) — антипаттерн |

## Подводные камни / gotchas
- **Slicing разделяет backing array.** `b := a[1:3]` не копирует — изменение `b[0]` меняет `a[1]`, а `append(b, x)` может затереть данные `a`. Память исходного массива не освобождается, пока жив хоть один под-слайс (утечка). Лекарство: `slices.Clone` или `append([]T(nil), src...)`.
- **Скрытое O(n²):** конкатенация строк через `+=` в цикле, `append` в начало через пересоздание, удаление элементов сдвигом в цикле.
- **Pre-sizing** `make(map, n)` / `make([]T, 0, n)` — не меняет Big-O, но убирает реаллокации/рехеши; на интервью это плюс к «понимаю аллокации».
- **Map worst case O(n)** — теоретически возможна деградация; для гарантий нужен сбалансированный поиск. Редко спрашивают, но senior должен знать.
- **Константы важны на практике:** O(n) с тяжёлой константой может быть медленнее O(n log n) на реальных n. Big-O — про асимптотику, не про конкретный бенч.
- **Память рекурсии** — глубина стека входит в space complexity. Глубокая рекурсия = O(глубины) памяти + риск переполнения стека.
- **`delete` из map не уменьшает память** — занятые бакеты остаются. Для освобождения — пересоздать map.

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

**В:** Какова сложность `append` к слайсу и почему?
**О:** O(1) амортизированно. Отдельный append может вызвать реаллокацию (новый массив + копирование = O(n)), но рост capacity геометрический (×2 / ×1.25), поэтому суммарная стоимость n аппендов — O(n), то есть O(1) на операцию. Если cap известен заранее, можно избежать реаллокаций через `make([]T, 0, n)`.

**В:** Чем амортизированная сложность отличается от average-case?
**О:** Average-case усредняет по распределению входов (одна операция, разные данные). Амортизированная — усредняет стоимость по длинной серии операций на одной структуре, гарантируя среднюю стоимость даже при детерминированном worst-case входе. Append — амортизированно O(1) независимо от данных.

**В:** Сложность map lookup в Go?
**О:** O(1) в среднем, O(n) в худшем случае (все ключи в один бакет / много коллизий). Go использует хеш-таблицу с бакетами; на практике коллизии редки, но формальной гарантии O(1) worst-case нет.

**В:** Дан код с двумя последовательными циклами по n и одним вложенным двойным. Итоговая сложность?
**О:** O(n) + O(n) + O(n²) = O(n²). Последовательные блоки складываются, берём максимум; младшие члены отбрасываются.

**В:** Почему `b := a[i:j]` это O(1), и в чём опасность?
**О:** Слайсинг создаёт новый header (ptr, len, cap), указывающий в тот же backing array — копирования нет. Опасность: разделяемая память (мутации видны обоим), удержание всего большого массива из-за маленького под-слайса (утечка), и затирание данных при `append`, если есть свободный cap. Решение — `slices.Clone`.

**В:** Как оценить сложность рекурсивной функции?
**О:** Составить рекуррентное соотношение `T(n)` и решить — подстановкой, деревом рекурсии или Master Theorem для вида `a·T(n/b)+f(n)`. Пример: merge sort `2T(n/2)+O(n)` = O(n log n); наивный fib `T(n-1)+T(n-2)` = O(2ⁿ).

**В:** Алгоритм A — O(n log n), B — O(n). Какой выбрать?
**О:** Асимптотически B лучше, но надо смотреть константы, паттерн доступа к памяти (cache locality), доп. память B (часто O(n) hash vs in-place sort), стабильность и реальный диапазон n. На малых/средних n O(n log n) sort может выиграть у hash-подхода из-за константы и локальности. Ответ «зависит» с обоснованием ценнее, чем «B».

## На что копают на senior+
- Умение **вывести сложность из кода**, а не процитировать таблицу; заметить скрытое квадратичное поведение (строки, вставки).
- Различение **time vs space** и обсуждение trade-off осознанно.
- Понимание **аллокаций в Go**: реаллокации слайсов, рехеши map, escape analysis (попадает ли переменная в heap), влияние GC.
- **Worst/average/amortized** — чёткое разграничение, особенно для map и append.
- Practical vs theoretical: знание, что константы и cache locality решают на реальных данных, и умение это измерить (`testing.B`, `pprof`).
- Анализ сложности параллельных решений (work/depth), если зашла речь о горутинах.