Профессия:
Задачи с собеседований на Go-разработчика: горутины и каналы, worker pool, rate limiter, graceful shutdown HTTP-сервера, предсказание вывода кода на slice, defer и nil-каналах, поиск багов вроде goroutine leak и data race в map. Каждая задача идёт с разбором и рабочим кодом.
Решение
Анализ задачи
Требования:
Стратегия:
Решение
package main
import (
"context"
"fmt"
"net/http"
"os"
"os/signal"
"syscall"
"time"
)
Mutex и WaitGroup на каналах - полное решение
Описание задачи
В Go каналы являются примитивом синхронизации между горутинами. Да, можно реализовать и Mutex, и WaitGroup только на каналах, используя их свойства:
Часть 1: Mutex на каналах
package main
import (
"fmt"
"sync"
)
// ChannelMutex реализует взаимное исключение на каналах
type ChannelMutex struct {
ch chan struct{}
}
func NewChannelMutex() *ChannelMutex {
m := &ChannelMutex{
ch: make(chan struct{}, 1), // буферизированный канал емкостью 1
}
m.ch <- struct{}{} // инициализируем токеном
return m
}
// Lock получает взаимное исключение (блокирует, если занято)
func (m *ChannelMutex) Lock() {
<-m.ch // читаем из канала, блокируемся если пусто
}
nil канал в select - полное решение
Ответы на вопросы
default
Объяснение:
var ch chan int - объявляем переменную типа канал, но не инициализируем еёnilselect из nil канала - операция не блокируется, вместо этого пропускаетсяdefault веткаvar ch chan int
select {
case val := <-ch:
fmt.Println(val)
}
Результат: Программа зависнет (deadlock).
Почему?
fatal error: all goroutines are asleep - deadlock!
Подробный анализ поведения nil каналов
var ch chan int // ch == nil
Решение
Эта задача про буферизованные каналы и их поведение при отправке и получении данных. Ответ демонстрирует важное понимание concurrency в Go.
Ответ на вопросы
1
2
3
4
5
Программа выведет все 5 чисел без ошибок и deadlock-а.
НЕТ, deadlock-а НЕ будет, хотя могло бы быть в других сценариях.
Анализ работы буферизованного канала
Ключевое различие — буферизованный канал (make(chan int, 4)):
Безбуферный канал: make(chan int) — buffer size = 0
Буферизованный: make(chan int, 4) — buffer size = 4
Как это работает:
ch := make(chan int, 4) // буфер на 4 элемента
Решение
Это задача про pointer vs value receivers и interface в Go. Классический подвох, который показывает важность понимания, как методы привязываются к типам.
Ответ на вопросы
НЕТ, код НЕ скомпилируется.
compilation error:
Foo does not implement Bar (Get method has pointer receiver)
Ошибка компилятора говорит, что Foo не реализует интерфейс Bar, потому что метод Get() определён с pointer receiver *Foo, а не value receiver Foo.
Есть три варианта, каждый с разными implications:
Вариант 1: Передать указатель (рекомендуется)
func main() {
foo := Foo{"hello"}
print(&foo) // передаём указатель вместо значения
}
Плюсы:
Минусы:
Вариант 2: Изменить receiver на value receiver
Решение
Это классический паттерн Fan-In в Go — объединение нескольких каналов в один. Задача требует корректного управления жизненным циклом каналов и синхронизации горутин.
Подход
Реализация
package main
import "sync"
Решение
Thread-safe Map — это обёртка над стандартной map с синхронизацией доступа через RWMutex. RWMutex позволяет нескольким читателям работать одновременно, но исключает писателей.
Подход
Реализация
package main
import (
"fmt"
"sync"
)
type SafeMap struct {
mu sync.RWMutex
items map[string]interface{}
}
func NewSafeMap() *SafeMap {
return &SafeMap{
items: make(map[string]interface{}),
}
}
func (m *SafeMap) Set(key string, value interface{}) {
m.mu.Lock() // эксклюзивная блокировка для записи
defer m.mu.Unlock()
m.items[key] = value
}
func (m *SafeMap) Get(key string) (interface{}, bool) {
m.mu.RLock() // разделяемая блокировка для чтения
defer m.mu.RUnlock()
val, ok := m.items[key]
return val, ok
}
Решение
Token Bucket Rate Limiter — это алгоритм для ограничения частоты запросов. Используется в системах ограничения API, защиты от DDoS, и контроля нагрузки. Ключевая идея: токены пополняются с фиксированной скоростью, каждый запрос расходует токены.
Принцип работы
capacity токеновrate токенов (но не более capacity)Реализация
import (
"sync"
"time"
)
type RateLimiter struct {
mu sync.Mutex
rate float64
capacity float64
tokens float64
lastTime time.Time
}
func NewRateLimiter(rate float64, capacity int) *RateLimiter {
return &RateLimiter{
rate: rate,
capacity: float64(capacity),
tokens: float64(capacity),
lastTime: time.Now(),
}
}
Синхронизация кэша с TTL - полное решение
Описание задачи
Нужно реализовать потокобезопасный кэш, который:
Архитектурное решение
Компоненты:
Реализация
package main
import (
"fmt"
"sync"
"time"
)
// Entry хранит значение и время его истечения
type Entry struct {
Value interface{}
ExpiresAt time.Time
}
Решение
Анализ задачи
Требования:
Математика: 1² + 2² + 3² + 4² + 5² = 1 + 4 + 9 + 16 + 25 = 55
Решение
func SumOfSquares(c int) int {
// Канал для получения результатов
resultChan := make(chan int)
// Запускаем горутину для вычисления каждого квадрата
for i := 1; i <= c; i++ {
go func(num int) {
square := num * num
resultChan <- square
}(i)
}
// Собираем результаты
sum := 0
for j := 0; j < c; j++ {
// Используем select для получения результата из канала
select {
case result := <-resultChan:
sum += result
}
}
return sum
}
Пояснения реализации
Решение
Это задача на глубокое понимание того, как слайсы работают в Go, особенно взаимодействие append и shared backing array.
Ответ на вопросы
[10 2 3] [1 10 3]
Отправка:
b = [10 2 3]a = [1 10 3] (значение изменилось!)a изменилось?Потому что a[:1] и a делят один и тот же backing array (буферный массив).
Анализ кода
a := []int{1, 2, 3}
Внутреннее представление a:
slice a:
┌──────┬─────┬─────┐
│ ptr │ 3 │ 3 │ ptr → [1, 2, 3] (буферный массив)
│ │ len │ cap │ len = 3, cap = 3
└──────┴─────┴─────┘
b := append(a[:1], 10)
Шаг 1: a[:1] создаёт новый слайс
slice a[:1]:
┌──────┬─────┬─────┐
│ ptr │ 1 │ 3 │ ptr → [1, 2, 3] (ТОТЖЕ буферный массив!)
│ │ len │ cap │ len = 1, cap = 3
└──────┴─────┴─────┘
Решение
Это классическая задача на goroutine leak — утечку горутин. Горутина остаётся запущенной даже после того, как её результаты больше не нужны.
1. Какая проблема?
Проблема: Goroutine Leak (утечка горутин)
Горотина запущенная в process() никогда не завершается:
for i := 0; ; i++ { // ← бесконечный цикл
ch <- i
time.Sleep(100 * time.Millisecond)
}
В main читаются только 5 значений, затем программа выводит "done" и завершается, но горутина остаётся в памяти до выхода программы.
Последствия:
2. Как исправить?
Вариант 1: Закрыть канал
Решение
Это классическая задача, которая показывает критическое различие между слайсами в Go. Ответ требует глубокого понимания того, как слайсы передаются в функции и как работает append.
Ответ на вопросы
[]
Отправка: пустой слайс.
Проблема заключается в том, как Go передаёт слайсы в функции:
Что происходит в коде:
1. main: s = make([]int, 0, 2)
→ создаётся слайс {ptr→[_,_], len=0, cap=2}
2. main: doSomething(s)
→ копируется структура слайса в параметр a
→ a = {ptr→[_,_], len=0, cap=2} (копия, но указатель на те же данные)
Решение: Что выведет код с defer и panic
Ответ на вопрос 1
Программа выведет:
C
B
A
Почему F не выводится?
Panic прерывает выполнение кода в текущей функции. Строка fmt.Println("F") и defer fmt.Println("E") никогда не выполнятся, потому что они находятся после вызова анонимной функции, которая паникует.
Пошаговое выполнение
Шаг 1: Регистрация defer в main
defer fmt.Println("A") // defer stack: [A]
defer fmt.Println("B") // defer stack: [B, A]
Deferы добавляются в стек LIFO (Last In, First Out).
Шаг 2: Вызов анонимной функции
func() {
defer fmt.Println("C") // defer stack (локальный): [C]
panic("panic!") // ПАНИКА!
defer fmt.Println("D") // Эта строка НЕ выполнится
}()
Шаг 3: Обработка паники
Паника вызывает раскрутку стека (unwinding):
Решение
Это задача с множественными проблемами: race condition, closure-захват переменной и race condition при доступе к переменной. Демонстрирует типичные ошибки с concurrency в Go.
1. Какие проблемы в коде?
Проблема 1: Closure захватывает переменную цикла
for i := 1000; i > 0; i-- {
go func() {
if i%2 == 0 ... // захватывает переменную i
}()
}
Все горутины захватывают одну переменную i, которая меняется.
Проблема 2: Data Race на переменной maxNum
var maxNum int
// Несколько горутин одновременно читают и пишут в maxNum БЕЗ синхронизации
if i > maxNum { // race: чтение
maxNum = i // race: запись
}
Проблема 3: Отсутствует WaitGroup
for i := 1000; i > 0; i-- {
go func() { ... }()
}
fmt.Printf("Maximum is %d", maxNum) // главная горутина не ждёт!
Главная горутина выводит результат, прежде чем все background горутины завершатся.
2. Почему результат неожиданный?
Решение
Это классическая задача на обнаружение data race. Go имеет встроенный инструмент для обнаружения именно таких проблем.
Ответ на вопросы
Проблема: Data Race (race condition)
Мапа в Go НЕ потокобезопасна. Несколько горутин одновременно пишут в одну и ту же map без синхронизации.
Горотина 1: m[10] = 100
Горотина 2: m[20] = 400 ← одновременно!
Горотина 3: m[30] = 900
Горотина 4: m[40] = 1600
Внутри Go это вызывает проблемы:
Как обнаружить data race?
Запустить с флагом -race:
go run -race main.go
# ИЛИ
go test -race ./...
Вывод:
==================
WARNING: DATA RACE
Write at 0x00c0001da000 by goroutine 8:
main.main.func1()
/path/to/main.go:15 +0x44
Решение
Используем стек для отслеживания открывающих скобок. Алгоритм простой: открывающие скобки добавляем в стек, закрывающие - проверяем совпадение с вершиной.
Код
func isValid(s string) bool {
stack := make([]rune, 0)
pairs := map[rune]rune{')': '(', '}': '{', ']': '['}
open := map[rune]bool{'(': true, '{': true, '[': true}
for _, ch := range s {
if open[ch] {
stack = append(stack, ch)
} else if len(stack) == 0 || stack[len(stack)-1] != pairs[ch] {
return false
} else {
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}
Как работает
Сложность
Примеры
HTTP клиент с батчами - реальное решение KazanExpress
Описание задачи
Нужно реализовать батч-клиент, который:
Это реальная задача для работы с rate-limited API (Telegram, Yandex, 1C, etc.)
Архитектурное решение
Основные компоненты:
Реализация
package main
import (
"context"
"fmt"
"log"
"net/http"
"sync"
"time"
)
Простой HTTP сервер
Описание задачи
Реализовать HTTP сервер с:
Архитектура
Используем стандартную net/http с несколькими подходами:
Компоненты
GET /health
Просто возвращаем status 200 и JSON: {"status": "ok"}
GET /users/:id
Парсим ID из URL Ищем пользователя в хранилище Возвращаем 200 с JSON или 404
POST /users
Парсим JSON из body Валидируем Name и Email Создаем новый User с ID = max_id + 1 Возвращаем 201 с созданным пользователем
Логирование
Мидлвэр который:
Ограниченное хранилище (FIFO Map)
Описание задачи
Мап с максимальным размером где при превышении лимита удаляется самый старый элемент (FIFO - First In First Out).
Отличие от LRU:
Архитектура
Используем две структуры:
Это дешевле чем двусвязный список как в LRU.
Реализация FIFO
Непосредственно используем:
Алгоритм Set:
Алгоритм Get:
FizzBuzz - полное решение
Описание задачи
FizzBuzz - классическая задача на интервью, которая проверяет базовые навыки:
Несмотря на простоту, задача часто обнаруживает недостатки в кодировании.
Решение 1: Базовое (если-то-иначе)
package main
import (
"fmt"
"strconv"
)
func fizzBuzz(n int) []string {
result := make([]string, n)
for i := 1; i <= n; i++ {
if i%3 == 0 && i%5 == 0 {
// Делится и на 3, и на 5
result[i-1] = "FizzBuzz"
} else if i%3 == 0 {
// Делится только на 3
result[i-1] = "Fizz"
} else if i%5 == 0 {
// Делится только на 5
result[i-1] = "Buzz"
} else {
// Ни на что не делится
result[i-1] = strconv.Itoa(i)
}
}
return result
}
Решение
Анализ задачи
Требования:
Простое решение: пройти по слайсу один раз, сравнивая элементы.
Решение
func Min(nums []int) (int, error) {
// Проверка на пустой слайс
if len(nums) == 0 {
return 0, errors.New("empty slice")
}
min := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] < min {
min = nums[i]
}
}
return min, nil
}
func Max(nums []int) (int, error) {
// Проверка на пустой слайс
if len(nums) == 0 {
return 0, errors.New("empty slice")
}
max := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] > max {
max = nums[i]
}
}
return max, nil
}
Пояснения реализации
Решение
Анализ задачи
Требования:
Ключевой паттерн: select с двумя каналами — один для результата, один для таймаута.
Решение
Решение
Бинарный поиск — это фундаментальный алгоритм поиска в отсортированном массиве. Основная идея: разделить пространство поиска пополам на каждой итерации.
Подход
left = 0, right = len(arr) - 1left <= right:
mid = (left + right) / 2arr[mid] == target → возвращаем midarr[mid] < target → ищем в правой половине (left = mid + 1)arr[mid] > target → ищем в левой половине (right = mid - 1)-1Реализация
Поиск подстроки
Задача: найти первое вхождение needle в haystack.
Алгоритм Brute Force
Шаг 1: Если needle пустая, return 0 Шаг 2: Если needle длиннее haystack, return -1 Шаг 3: Для каждой позиции i в haystack (от 0 до len-len(needle)): Проверяем совпадает ли подстрока haystack[i:i+len(needle)] с needle Если совпадает, return i Шаг 4: Если не найдена, return -1
Пример
haystack = hello, needle = ll
Позиция 0: haystack[0:2] = he != ll Позиция 1: haystack[1:3] = el != ll Позиция 2: haystack[2:4] = ll == ll -> return 2
Сложность
Time: O(n*m) где n=len(haystack), m=len(needle) Space: O(1)
Граничные случаи
Оптимизация
Для очень больших строк использовать KMP или Rabin-Karp алгоритмы с O(n+m) временем.
Решение
Реализуем функцию вычисления чисел Фибоначчи с мемоизацией.
Простая версия с кэшем
func fibonacci(n int) int {
cache := make(map[int]int)
var fib func(int) int
fib = func(x int) int {
if x <= 1 {
return x
}
if val, ok := cache[x]; ok {
return val
}
result := fib(x-1) + fib(x-2)
cache[x] = result
return result
}
return fib(n)
}
Потокобезопасная версия с sync.Map
var fibCache sync.Map
func fibonacci(n int) int {
if n <= 1 {
return n
}
val, ok := fibCache.Load(n)
if ok {
return val.(int)
}
result := fibonacci(n-1) + fibonacci(n-2)
fibCache.Store(n, result)
return result
}
Быстрая итеративная версия
Решение: Найти баг — deadlock в select
Проблема 1: Бесконечный select без default
Основная проблема — бесконечный for цикл с select:
for {
select {
case q := <-ch:
fmt.Println(q)
}
}
Этот код никогда не завершится, потому что:
mu.Lock()chwg.Wait() никогда не достигаетсяDeadlock: основной поток ждёт горутины, но горутины не могут завершиться (ждут отправки в канал, который основной поток не успевает читать), а основной поток не может закончить читать, потому что for бесконечен.
Проблема 2: Неправильная логика синхронизации
Все горутины конкурируют за один mu.Mutex, но в буферизированном канале нет необходимости синхронизировать отправку. Мьютекс создаёт дополнительные задержки и усложняет диагностику проблем.
Исправленный вариант 1: С сигналом завершения
Решение
Min и Max — это базовые операции для работы со слайсами. Go в отличие от Python/JavaScript не имеет встроенных функций, поэтому нужно реализовать самостоятельно.
Подход
Реализация
package main
import (
"errors"
"fmt"
)
var ErrEmptySlice = errors.New("empty slice")
func Min(nums []int) (int, error) {
if len(nums) == 0 {
return 0, ErrEmptySlice
}
min := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] < min {
min = nums[i]
}
}
return min, nil
}
func Max(nums []int) (int, error) {
if len(nums) == 0 {
return 0, ErrEmptySlice
}
max := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] > max {
max = nums[i]
}
}
return max, nil
}
Решение Two Sum
Описание задачи
Задача требует найти два индекса элементов массива, сумма которых равна целевому значению. Ограничения: каждый элемент можно использовать только один раз, и решение существует всегда.
Подход с хеш-таблицей (O(n) по времени)
Оптимальное решение использует хеш-таблицу (map в Go) для хранения пройденных чисел и их индексов. Идея простая:
Время: O(n) — один проход по массиву. Пространство: O(n) — размер map в худшем случае.
Реализация
Решение
Это классическая задача на понимание closures в Go и того, как переменные захватываются. Результат может быть очень неожиданным!
Ответ на вопросы
Программа может вывести:
4
4
4
4
ИЛИ какую-то комбинацию вроде 2 3 4 4, но скорее всего 4 4 4 4.
НЕ выведет 0, 1, 2, 3 — это самое важное!
Проблема в классической ошибке с closures и переменными цикла:
Анализ кода
for i := 0; i < 4; i++ { // i = 0, 1, 2, 3
go func() {
ch <- &i // ключевая ошибка!
}()
}
Что происходит:
Итерация 1: i = 0
&i — это адрес переменной iИтерация 2: i = 1
Итерация 3: i = 2
Решение
Это подвох с nil в Go — одна из самых частых ошибок и источников confusion для разработчиков, особенно идущих из других языков. Ответ может удивить!
Ответ
ERROR
Программа выведет ERROR, хотя p явно равна nil и if false не выполняется.
Объяснение: nil в interface{} и error
Проблема в тонкой разнице между типизированным nil и истинным nil.
Каждый interface в Go — это пара (type, value):
interface{} = (type, value)
Когда вы присваиваете значение interface:
var p *MyError = nil // это nil указатель
err := error(p) // err = (*MyError, nil)
Важно: err НЕ равен nil в смысле interface! Это типизированный nil.
err = (*MyError, nil) // type = *MyError, value = nil
Сравнение err != nil проверяет не value, а всю пару:
if err != nil { // проверяет: тип не nil И value не nil
// true, если обе части ненулевые
}
Решение
Worker Pool — это паттерн параллельной обработки, где фиксированное число горутин-воркеров обрабатывают задачи из общей очереди. Это позволяет контролировать использование ресурсов и избежать создания неограниченного количества горутин.
Подход
numWorkers горутин (воркеров)jobsresultsjobs воркер корректно завершаетсяРеализация
import "sync"
Решение: Первый результат выигрывает
Основная идея
Паттерн "first wins" часто используется в production для:
Используем канал результатов и select для получения первого значения.
Простая реализация
import (
"context"
"fmt"
)
type result struct {
value int
err error
}
Решение
Singleton паттерн — создание только одного экземпляра объекта с потокобезопасным доступом.
Решение 1: sync.Once (РЕКОМЕНДУЕТСЯ)
var (
instance *Database
once sync.Once
)
func GetInstance() *Database {
once.Do(func() {
instance = &Database{
connection: "default-connection",
}
})
return instance
}
Преимущества sync.Once:
Решение 2: sync.Mutex (явное управление)
type databaseHolder struct {
mu sync.Mutex
instance *Database
}
var holder = &databaseHolder{}
Решение: Что выведет код с закрытым каналом
Ответ на вопрос 1
Программа выведет:
val=1, ok=true
val=2, ok=true
val=3, ok=true
val=0, ok=false
val=0, ok=false
Почему такой результат?
Шаг 1: Создание и заполнение канала
ch := make(chan int, 3) // Буферизированный канал на 3 элемента
ch <- 1 // Элемент 1 в буфер
ch <- 2 // Элемент 2 в буфер
ch <- 3 // Элемент 3 в буфер
// Буфер полон: [1, 2, 3]
Шаг 2: Закрытие канала
close(ch) // Канал закрыт, но элементы остаются в буфере
Шаг 3: Первые три итерации цикла
i=0: val, ok := <-ch // Читаем 1 из буфера
ok=true (элемент найден)
fmt.Printf("val=1, ok=true\n")
i=1: val, ok := <-ch // Читаем 2 из буфера
ok=true (элемент найден)
fmt.Printf("val=2, ok=true\n")
i=2: val, ok := <-ch // Читаем 3 из буфера
ok=true (элемент найден)
fmt.Printf("val=3, ok=true\n")
Решение
Reverse words in string — это классическая задача на манипуляцию строками. Нужно развернуть порядок слов, сохраняя сами слова неизменёнными.
Подход
Реализация
package main
import (
"fmt"
"strings"
)
func reverseWords(s string) string {
// Разбить на слова
words := strings.Fields(s) // автоматически удаляет пустые строки
// Развернуть слайс
for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
words[i], words[j] = words[j], words[i]
}
// Объединить обратно
return strings.Join(words, " ")
}
Решение: Все перестановки строки
Основная идея
Используем рекурсию с backtracking:
Рекурсивная реализация (наиболее эффективная)
func permutations(s string) []string {
var result []string
permute([]rune(s), 0, &result)
return result
}
Решение: Map и итерация в Go
Ответ на вопрос 1
НЕТ, порядок вывода не гарантирован и будет различаться между запусками.
Каждый запуск программы может вывести значения в разном порядке:
Запуск 1:
1: one
2: two
3: three
Запуск 2:
3: three
1: one
2: two
Запуск 3:
2: two
3: three
1: one
Ответ на вопрос 2: Почему нет гарантии порядка?
Go намеренно рандомизирует порядок итерации по map в целях безопасности и стимулирования правильного кода. Вот причины:
1. Реализация: Hash table
Map в Go реализована как hash table:
- Ключ преобразуется в hash через hash function
- Hash определяет бакет (позицию в массиве)
- Порядок итерации зависит от h
легких значений
2. Причины рандомизации:
Решение: Самая длинная подстрока без повторяющихся символов
Основная идея: Sliding Window
Используем два указателя (левый и правый):
Оптимальная реализация O(n)
Решение: Что выведет код со слайсами
Ответ на вопрос 1
Программа выведет:
[1 10 3 40]
Почему именно этот результат?
Чтобы понять, нужно разобраться в том, как слайсы передаются в функции.
Что такое слайс в Go
Слайс — это не массив, а структура, содержащая три поля:
type slice struct {
data *T // указатель на базовый массив
len int // текущая длина
cap int // ёмкость
}
Это очень важно: слайс передаётся по значению, но указатель на данные остаётся тем же!
Пошаговое выполнение
Инициализация:
s := []int{1, 2, 3}
// s содержит:
// data: [1, 2, 3]
// len: 3
// cap: 3
Вызов f2(&s) — передаём указатель на слайс:
func f2(s *[]int) {
(*s)[1] = 10 // меняем элемент базового массива
*s = append(*s, 40) // расширяем сам слайс
}
(*s)[1] = 10 — разыменовываем указатель и меняем элемент
Решение
Анализ задачи
Требования:
Сложность: нужно избежать бесконечного цикла, если n больше количества доступных чисел.
Решение 1: Использование map для отслеживания
Калькулятор - реальное тестовое от Kata Academy
Описание задачи
Реализовать калькулятор который:
Решение базовое (арабские цифры)
Алгоритм:
Приоритет операций:
Примеры: 8 / 2 + 3 = 4 + 3 = 7 2 + 2 * 2 = 2 + 4 = 6
Решение полное (с римскими)
Шаг 1: Определяем тип чисел (арабские или римские)
Шаг 2: Конвертируем в целые числа
Шаг 3: Вычисляем результат
Шаг 4: Конвертируем результат обратно
Проверки при парсинге
Pub/Sub система
Построим систему publish/subscribe с каналами.
Реализация
Основные компоненты:
Алгоритм Subscribe:
Алгоритм Publish:
Алгоритм Unsubscribe:
Алгоритм Close:
Сложность
Ключевые особенности
Buffered каналы: каждый канал размера 10 позволяет избежать блокировки издателя при отправке 10 сообщений
Решение
Анализ задачи
Требования:
Бонус: несколько подходов — арифметический, побитовый XOR и идиоматический Go.
Решение 1: Арифметический способ
func swapArithmetic(a, b *int) {
*a = *a + *b
*b = *a - *b
*a = *a - *b
}
Как это работает:
a = a + b (теперь a содержит сумму)b = (a + b) - b = a (b получает старое значение a)a = (a + b) - (a + b) - b = b (a получает старое значение b)Пример: a=5, b=10
Минусы: может привести к переполнению для больших чисел.
Решение 2: XOR (побитовое исключающее ИЛИ)
func swapXOR(a, b *int) {
*a = *a ^ *b
*b = *a ^ *b
*a = *a ^ *b
}
Решение: Генератор случайных чисел
Основная идея
Используем подход "Fisher-Yates shuffle" (также известный как "Knuth shuffle"):
Простая реализация
import (
"math/rand"
)
func UniqueRandomGenerator(min, max int) <-chan int {
ch := make(chan int)
go func() {
defer close(ch)
// Создаём слайс чисел [min, max]
numbers := make([]int, max-min+1)
for i := 0; i < len(numbers); i++ {
numbers[i] = min + i
}
// Fisher-Yates shuffle
for i := len(numbers) - 1; i > 0; i-- {
j := rand.Intn(i + 1)
numbers[i], numbers[j] = numbers[j], numbers[i]
}
// Отправляем числа в канал
for _, num := range numbers {
ch <- num
}
}()
return ch
}
Решение: Реализовать Queue на слайсе
Основная идея
Queue (очередь) — структура данных FIFO (First In, First Out). Элементы добавляются с конца и удаляются с начала. На слайсе это неэффективно для каждого Dequeue(), так как нужно смещать все элементы. Однако для учебных целей можно использовать простой подход или оптимизированный с индексами.
Наивный подход: с копированием
type Queue struct {
items []int
}
func NewQueue() *Queue {
return &Queue{
items: make([]int, 0),
}
}
func (q *Queue) Enqueue(val int) {
q.items = append(q.items, val)
}
func (q *Queue) Dequeue() (int, bool) {
if len(q.items) == 0 {
return 0, false
}
val := q.items[0]
q.items = q.items[1:]
return val, true
}
func (q *Queue) Front() (int, bool) {
if len(q.items) == 0 {
return 0, false
}
return q.items[0], true
}
func (q *Queue) IsEmpty() bool {
return len(q.items) == 0
}
Объединение map
Задача: объединить несколько map, суммируя значения при совпадении ключей.
Алгоритм
Реализация
Создаем map результатом. Итерируем по всем входным map. Для каждого ключа суммируем значения используя +=.
Cложность:
Особенности
Примеры
m1 = {a:1, b:2} m2 = {b:3, c:4} m3 = {a:5}
Параллельное чтение файла
Описание задачи
Обрабатывать большой файл параллельно:
Архитектура решения
Используем паттерн worker pool:
Параметры
Алгоритм
Шаг 1: Открыть файл Шаг 2: Создать буфер размера chunkSize Шаг 3: Запустить workers Шаг 4: В цикле:
Обработка ошибок
LRU Cache - полное решение
Описание задачи
LRU (Least Recently Used) Cache - это кэширующая структура данных с фиксированной ёмкостью, которая автоматически вытесняет наименее недавно использованный элемент при переполнении. Это часто используется для оптимизации доступа к часто используемым данным.
Архитектурное решение
Для достижения O(1) сложности для обеих операций используем комбинацию двух структур данных:
Двусвязный список позволяет за O(1) переместить элемент в конец (самый свежий) и удалить элемент из начала (самый старый).
Реализация
package main
import "fmt"
type Node struct {
key, value int
prev, next *Node
}
Решение
Задача требует найти элементы, которые присутствуют одновременно в обоих слайсах. Ключевой момент — входные данные неупорядочены, поэтому прямое сравнение неэффективно.
Подход
Используем map (хеш-таблицу) для оптимизации:
Реализация