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 - На 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). Признак: «пара с суммой», «палиндром», «удалить дубликаты на месте», «слить отсортированные». ```go // 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 } ``` ```go // Удаление дубликатов из отсортированного слайса на месте, 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». ```go // Длиннейшая подстрока без повторов, 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). ```go // Ручной бинарный поиск, аккуратно с границами: 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»: ```go // Минимальная скорость, чтобы успеть (псевдо-пример 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. ```go // 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 } ``` ```go // 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. ```go // Все подмножества, 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). Признак: «сколько способов», «максимум/минимум при выборе», оптимальная подструктура. ```go // 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 } ``` ```go // 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 sort | O(n log n) / O(n²) | O(log n) | нет | | Merge sort | O(n log n) / O(n log n) | O(n) | да | | Heap sort | O(n log n) / O(n log n) | O(1) | нет | | Insertion | O(n²) / O(n²) | O(1) | да | | Counting/Radix | O(n+k) | O(n+k) | да | ```go // Идиоматичная сортировка в 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