Practical SRE & DevOps guides. Linux debugging. Lifestyle

Підготовка до співбесід: глибоке розуміння алгоритмів, структур даних та архітектури

Як читати цю статтю: Можна по порядку, можна стрибати до потрібного розділу. Кожна тема самодостатня. Але читаючи все разом — побачиш, як теми з’єднані між собою.

Зміст

  1. Heap і Priority Queue
  2. Binary Search: один шаблон для всього
  3. Рекурсія і Leap of Faith
  4. Doubly Linked List і Memory Leak
  5. LRU Cache
  6. LFU Cache
  7. Хеш-таблиці зсередини
  8. Memory Model: як компілятор і CPU можуть тебе здивувати
  9. Транзакції: ACID і BASE
  10. Рівні ізоляції транзакцій і аномалії
  11. Concurrency Control: як синхронізувати доступ до даних
  12. Dynamic Programming: мислення, а не заучування
  13. Чистий код і архітектура
  14. Golang Scheduler зсередини
  15. Як вчити алгоритми ефективно
  16. Критичне мислення для розробника

Heap і Priority Queue

Що це таке і навіщо

Priority Queue (черга з пріоритетом) — абстракція: черга, де кожен елемент має пріоритет. Елемент з найвищим (або найнижчим) пріоритетом виходить першим, незалежно від порядку додавання.

Heap (купа) — конкретна структура даних, яка реалізує Priority Queue ефективно. Це бінарне дерево з одним правилом: батько завжди більший (Max-Heap) або менший (Min-Heap) за своїх дітей.

       Max-Heap:              Min-Heap:
           9                     1
          / \                   / \
         7   8                 3   2
        / \ / \               / \ / \
       4  6 5  3             7  4 5  6

Як зберігається в пам’яті

Heap зберігається як масив, не як вказівники на вузли. Це важливо — немає витрат на вказівники, краща cache locality (дані поруч у пам’яті).

Індексація:

Дерево:    [9, 7, 8, 4, 6, 5, 3]
Індекси:    0  1  2  3  4  5  6

9 (індекс 0) → діти: 7 (1) та 8 (2)
7 (індекс 1) → діти: 4 (3) та 6 (4)

Операції та їх складність

ОпераціяСкладністьПояснення
InsertO(log n)Додаємо в кінець, спливаємо вгору (Heapify Up)
Extract Max/MinO(log n)Беремо корінь, ставимо останній, тонемо вниз (Heapify Down)
Peek (подивитись без видалення)O(1)Корінь завжди максимум/мінімум
Build Heap з масивуO(n)Не O(n log n)! Пояснення нижче

Чому Build Heap — O(n), а не O(n log n)?

Це класичне питання. Якщо вставляти n елементів по одному — O(n log n). Але якщо будувати через Heapify Down з середини масиву:

Сума цього ряду сходиться до O(n). Математично: Σ k * n/2^k = O(n).

Heap Sort: сортування за O(n log n)

1. Build Max-Heap з масиву: O(n)
2. Повторно: беремо максимум (корінь), 
   ставимо в кінець, зменшуємо розмір, 
   відновлюємо Heap: O(n log n)

Переваги: in-place (не потребує додаткової пам’яті), O(n log n) гарантовано. Недолік: cache-unfriendly на практиці, тому Quick Sort часто швидший.

Де застосовується в реальному житті

Проблема зі стандартними поясненнями

Більшість туторіалів показують простий пошук числа в масиві. А потім на практиці виявляється: умови циклу різні (<=, <, !=), межі (lo <= hi, lo < hi, lo + 1 < hi) плутають, і з’являються нескінченні цикли.

Причина: вчать конкретний код, а не принцип.

Один універсальний шаблон

Ключова ідея Binary Search — бінарна властивість: весь простір пошуку можна розділити на дві частини: ліву (умова не виконується) і праву (умова виконується). Ми шукаємо границю між ними.

def binary_search(lo, hi, condition):
    # Інваріант: condition(lo-1) = False, condition(hi) = True
    while lo < hi:
        mid = lo + (hi - lo) // 2  # Без overflow
        if condition(mid):
            hi = mid          # Права частина звужується
        else:
            lo = mid + 1      # Ліва частина звужується
    return lo  # Перший індекс, де condition = True

Цей шаблон працює для всіх варіацій Binary Search. Змінюється тільки condition.

Приклади застосування

Пошук числа в масиві:

condition = lambda mid: arr[mid] >= target

Мінімальна швидкість, щоб встигнути до дедлайну:

condition = lambda speed: can_finish_in_time(speed)

Знайти мінімальний розмір підмасиву з сумою ≥ S:

condition = lambda size: exists_subarray_with_sum(size)

Binary Search не тільки на масивах

Binary Search застосовується скрізь, де є монотонна функція. Навіть у дебагінгу: якщо є 1000 коммітів і треба знайти той, де з’явився баг — git bisect використовує binary search. Замість 1000 перевірок — 10 (log₂(1000) ≈ 10).

Рекурсія

Декларативне мислення проти імперативного

Імперативне: пояснюєш комп’ютеру як робити крок за кроком. Декларативне: описуєш що маєш і що хочеш отримати.

Рекурсія — інструмент декларативного мислення. Замість “йди в цикл, відстежуй індекс, перевіряй умову…” описуєш: “якщо маємо X — робимо Y, далі те саме для меншої задачі”.

Leap of Faith — стрибок віри

Найважливіший принцип рекурсивного мислення. Коли пишеш рекурсивну функцію, вір, що вона вже правильно вирішує меншу підзадачу. Твоя робота — тільки:

  1. Визначити базовий випадок (base case) — коли відповідь відома без рекурсії
  2. Звести задачу до меншої
  3. Скористатись результатом підзадачі
# Сума списку: "якщо список порожній — 0,
# інакше перший елемент + сума решти"
def sum_list(lst):
    if not lst:          # base case
        return 0
    return lst[0] + sum_list(lst[1:])  # Leap of Faith: sum_list(lst[1:]) вже працює

Де рекурсія краща за ітерацію

Tail Recursion Optimization (TRO)

Хвостова рекурсія (tail recursion) — коли рекурсивний виклик є останньою операцією функції (не return f(n-1) + 1, а return f(n-1)). Компілятор може оптимізувати це в звичайний цикл, не нагромаджуючи стек.

Підтримують: Lisp, Rust (частково), C++ (залежить від компілятора), Kotlin (tailrec). Не підтримують: Python, Java, Go (там треба явно переписувати в цикл).

Pruning — відсікання гілок

Рекурсія може бути швидшою за цикли завдяки pruning: якщо бачимо, що гілка не може дати правильну відповідь — робимо return і не йдемо далі. У циклах це зробити складніше.

Linked List і Memory Leak

Doubly Linked List (двозв’язний список)

Кожен вузол зберігає вказівники на попередній і наступний елемент:

None ← [prev|data|next] ↔ [prev|data|next] ↔ [prev|data|next] → None

Переваги: вставка і видалення — O(1) якщо є вказівник на елемент; обхід в обидва боки. Недоліки: більше пам’яті (два вказівники); погана cache locality (елементи розкидані по пам’яті, тому CPU кешує їх погано).

Страуструп (автор C++) казав: “ніколи не використовуй linked list, завжди vector”. Потім пояснив, що мав на увазі загальну тенденцію — для більшості випадків vector (масив) швидший через cache locality. Але DLL незамінний там, де потрібні O(1) вставка/видалення у відомому місці.

Memory Leak через циклічні посилання

Класична пастка в C++ з shared_ptr:

struct Node {
    shared_ptr<Node> next;
    shared_ptr<Node> prev;  // Проблема!
};

shared_ptr рахує кількість посилань (reference counting). Якщо A → B і B → A (обидва через shared_ptr), лічильник ніколи не впаде до нуля — memory leak.

Рішення: prev робити weak_ptr. Слабкий вказівник не збільшує лічильник — цикл розривається.

struct Node {
    shared_ptr<Node> next;
    weak_ptr<Node> prev;  // Не збільшує reference count
};

Rule of 5 в C++: якщо визначаєш один з цих методів, визнач усі п’ять:

Або Rule of 0: якщо клас не управляє ресурсами — не визначай жодного, покладайся на компілятор.

LRU Cache

Що таке LRU

LRU (Least Recently Used) — алгоритм витіснення кешу. Коли кеш заповнений і треба додати новий елемент — видаляємо той, що використовувався найдавніше.

Приклад: браузер кешує вкладки. Якщо пам’яті не вистачає — видаляє ту, яку ти найдавніше переглядав.

Реалізація: Hash Map + Doubly Linked List

Ось де DLL стає незамінним:

Кеш розміром 3, операції: get(1), get(2), get(3), get(1), get(4)

Після get(1): [1]
Після get(2): [2, 1]
Після get(3): [3, 2, 1]
Після get(1): [1, 3, 2]  ← 1 переміщається на початок
Після get(4): [4, 1, 3]  ← 2 витісняється (найстаріший)

Операції — O(1):

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}              # key → node
        self.head = Node()           # dummy head (найновіший)
        self.tail = Node()           # dummy tail (найстаріший)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._move_to_front(node)
        return node.val

    def put(self, key, value):
        if key in self.cache:
            self.cache[key].val = value
            self._move_to_front(self.cache[key])
        else:
            if len(self.cache) == self.cap:
                lru = self.tail.prev  # Видаляємо найстаріший
                self._remove(lru)
                del self.cache[lru.key]
            node = Node(key, value)
            self.cache[key] = node
            self._insert_front(node)

Де застосовується

LFU Cache

LFU vs LRU: в чому різниця

LFU (Least Frequently Used) — витісняє елемент з найменшою кількістю звернень, а не найдавніший.

LRULFU
Критерій витісненняНайдавніше використанийНайрідше використаний
Підходить дляЗагальний веб-кеш, сесіїТрендовий контент, популярні дані
Складність реалізаціїСередняВища

Реалізація O(1)

Наївна реалізація — O(log n) через сортування. Але O(1) можлива через:

При зверненні до ключа: збільшуємо частоту, переміщуємо зі списку freq до списку freq+1, оновлюємо min_freq.

Коли LFU краще LRU

LRU має проблему: якщо ти нещодавно переглянув рідкісний файл, він витіснить популярний файл, до якого давно не зверталися. LFU краще для даних з чіткими патернами популярності (трендові відео, гарячі ключі в БД).

Хеш-таблиці

Як це працює зсередини

Уяви масив на 100 комірок. Хочемо зберегти "name" → "Alice":

  1. Застосовуємо хеш-функцію до ключа: hash("name") = 42
  2. Записуємо в array[42] = ("name", "Alice")
  3. При пошуку: хешуємо ключ → отримуємо індекс → читаємо значення

Весь процес — O(1) в середньому. Незалежно від кількості елементів.

Вимоги до хеш-функції

Load Factor і Resize

Load Factor (коефіцієнт завантаження) = кількість елементів / розмір масиву

Якщо Load Factor перевищує поріг (зазвичай 0.7–0.75):

  1. Створюємо новий масив вдвічі більшого розміру
  2. Перехешовуємо всі елементи в нові позиції
  3. Видаляємо старий масив

Це O(n) операція, але відбувається рідко. Амортизована складність insert залишається O(1).

Колізії: два ключі дають однаковий індекс

Chaining (ланцюжки):

array[42] → [("name", "Alice") → ("email", "Bob") → null]
array[43] → null

Кожна комірка — зв’язний список. При колізії — додаємо в список. Пошук: O(1) середнє, O(n) у найгіршому (якщо всі в одній комірці).

Open Addressing (відкрита адресація): При колізії шукаємо наступну вільну комірку за певним правилом:

Open Addressing краще cache-friendly (дані поруч), але складніше видалення (потрібен tombstone — маркер видаленого).

Коли хеш-таблиця може підвести

HashMap у різних мовах

МоваНазваРеалізація
PythondictOpen Addressing (compact)
GomapChaining з bucket’ами по 8 елементів
JavaHashMapChaining, при >8 елементів у bucket — Red-Black Tree
C++unordered_mapChaining

Memory Model

Що таке Memory Model і навіщо вона потрібна

Memory Model (модель пам’яті) — набір правил, що визначають:

Без Memory Model твій код може поводитись несподівано: і компілятор, і CPU переставляють інструкції для оптимізації.

Чому CPU і компілятор переставляють операції

CPU має кілька рівнів кешу (L1, L2, L3). Запис у пам’ять — дорогий. Щоб не чекати — CPU виконує операції out-of-order (не по порядку коду) і буферизує записи.

Компілятор теж може переставляти операції, якщо вважає їх незалежними.

Для однопоточного коду — результат однаковий. Для багатопоточного — не гарантовано.

Приклад проблеми

var ready bool
var data int

// Goroutine 1:
data = 42
ready = true    // CPU може виконати це РАНІШЕ ніж data = 42!

// Goroutine 2:
if ready {
    fmt.Println(data)  // Може надрукувати 0 замість 42!
}

Вирішення: Memory Barriers і атомарні операції

Memory Barrier (бар’єр пам’яті) — інструкція процесору: “всі операції до цього місця мають бути завершені перед продовженням”.

У Go: sync/atomic, sync.Mutex, канали — всі вони встановлюють неявні бар’єри.

var ready int32  // Атомарна змінна
var data int

// Goroutine 1:
data = 42
atomic.StoreInt32(&ready, 1)  // Гарантує, що data=42 видиме перед цим

// Goroutine 2:
if atomic.LoadInt32(&ready) == 1 {
    fmt.Println(data)  // Безпечно: 42
}

Memory Model у різних мовах

Транзакції: ACID і BASE

ACID — гарантії реляційних БД

ACID — абревіатура з чотирьох властивостей транзакції:

A — Atomicity (Атомарність) Транзакція або виконується повністю, або не виконується взагалі. Якщо під час переказу грошей з рахунку A на рахунок B сталась помилка — ні A не зменшиться, ні B не збільшиться.

C — Consistency (Узгодженість) Транзакція переводить БД з одного консистентного стану в інший. Всі обмеження (constraints, foreign keys, check constraints) виконуються.

I — Isolation (Ізольованість) Паралельні транзакції не бачать проміжних станів одна одної. Ступінь ізоляції налаштовується (детально — у наступному розділі).

D — Durability (Тривалість) Після успішного COMMIT дані збережені назавжди, навіть при збої системи. Забезпечується через Write-Ahead Log (WAL) — журнал, куди запис йде спершу.

BASE — властивості NoSQL систем

BASE — протиставлення ACID для розподілених систем:

BA — Basically Available (Базова доступність) Система завжди відповідає, навіть якщо дані можуть бути застарілими або частково недоступними.

S — Soft State (М’який стан) Стан системи може змінюватись з часом навіть без зовнішніх запитів (через реплікацію).

E — Eventual Consistency (Можлива узгодженість) Система зрештою досягне консистентного стану, але не гарантує це в будь-який момент часу.

Приклад: Amazon DynamoDB. Якщо ти оновив кількість товарів на складі, інший сервіс може ще хвилину бачити старе значення. Але зрештою — побачить нове.

Теорема CAP

У розподілених системах неможливо одночасно гарантувати всі три:

Треба вибрати два. PostgreSQL — CP (жертвує доступністю). Cassandra — AP (жертвує консистентністю).

Рівні ізоляції транзакцій

Проблема паралельних транзакцій: аномалії

Коли кілька транзакцій працюють одночасно, можуть виникати аномалії читання:

Dirty Read (брудне читання) Транзакція B читає дані, які записала транзакція A, але ще не зробила COMMIT. Якщо A зробить ROLLBACK — B прочитала неіснуючі дані.

T1: UPDATE balance = 0 WHERE user=1
T2: SELECT balance FROM users WHERE user=1  → 0  (брудне читання!)
T1: ROLLBACK  → balance знову 100

Non-Repeatable Read (неповторюване читання) Транзакція читає один рядок двічі і отримує різні значення (між читаннями інша транзакція змінила рядок і зробила COMMIT).

Phantom Read (фантомне читання) Транзакція виконує запит двічі і отримує різні набори рядків (між запитами інша транзакція вставила або видалила рядки).

Lost Update (втрачене оновлення) Дві транзакції читають значення, обидві обчислюють нове і записують. Перший запис перезаписується другим.

T1: READ balance = 100
T2: READ balance = 100
T1: WRITE balance = 100 + 50 = 150
T2: WRITE balance = 100 + 30 = 130  ← Втрачено +50!

Рівні ізоляції (від найслабшого до найсильнішого)

Read Uncommitted Дозволяє всі аномалії. Практично не використовується. Транзакція бачить навіть незакомічені зміни.

Read Committed (default у PostgreSQL, Oracle) Усуває Dirty Read. Транзакція бачить тільки закомічені дані. Але Non-Repeatable Read і Phantom Read можливі.

SET TRANSACTION ISOLATION LEVEL READ COMMITTED;

Repeatable Read (default у MySQL InnoDB) Усуває Dirty Read і Non-Repeatable Read. Один і той самий SELECT поверне ті самі рядки протягом транзакції. Phantom Read теоретично можливий (у PostgreSQL через MVCC — ні).

Serializable Найсильніша ізоляція. Паралельні транзакції виконуються так, ніби послідовно. Усуває всі аномалії, але найповільніший.

MVCC — як PostgreSQL реалізує ізоляцію

MVCC (Multi-Version Concurrency Control) — багатоверсійний контроль конкурентності. Замість блокувань — кожен UPDATE створює нову версію рядка, стара залишається.

Рядок: id=1, balance=100, xmin=5, xmax=0   (версія від транзакції 5)

T7: UPDATE balance=150
→ Рядок v1: id=1, balance=100, xmin=5, xmax=7   (застаріла, видалена T7)
→ Рядок v2: id=1, balance=150, xmin=7, xmax=0   (актуальна)

T6 (стартувала раніше T7): SELECT balance
→ Бачить v1 (balance=100), бо xmax=7 > T6's snapshot_time

Переваги MVCC:

Недолік: накопичення мертвих версій рядків. Потрібен VACUUM — процес прибирання застарілих версій.

SSI — Serializable Snapshot Isolation

SSI (Serializable Snapshot Isolation) — сучасний підхід у PostgreSQL (з версії 9.1), що дає serializable ізоляцію без важких блокувань. Відстежує “небезпечні” залежності між транзакціями і відкочує тільки ті, що порушують serializable порядок.

На практиці SSI значно продуктивніший за класичний Serializable з S-блокуваннями.

Concurrency Control

Pessimistic vs Optimistic лocking

Pessimistic Locking (песимістичне блокування) “Хтось точно захоче змінити ці дані — заблокую одразу.”

BEGIN;
SELECT * FROM accounts WHERE id = 1 FOR UPDATE;  -- Блокуємо рядок
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
COMMIT;

FOR UPDATE — ексклюзивне блокування рядка. Інші транзакції чекають. Підходить при високій конкуренції за одні й ті ж дані.

FOR UPDATE NOWAIT — якщо рядок заблокований, одразу помилка (не чекає).

FOR SHARE — спільне блокування (інші можуть читати, але не писати).

Optimistic Locking (оптимістичне блокування) “Скоріш за все ніхто не змінить — запишу без блокування, але перевірю.”

-- Читаємо з версією
SELECT id, balance, version FROM accounts WHERE id = 1;
-- version = 5

-- Оновлюємо тільки якщо version не змінилась
UPDATE accounts 
SET balance = balance - 100, version = version + 1
WHERE id = 1 AND version = 5;

-- Якщо affected_rows = 0 → хтось встиг змінити → retry

Підходить при низькій конкуренції — менше блокувань, більша пропускна здатність.

Коли що використовувати

СитуаціяПідхід
Бронювання місць (висока конкуренція)Pessimistic (FOR UPDATE)
Рідкісні оновлення профілюOptimistic (version field)
Читання без записуFOR SHARE або без блокування
Не можна чекати (real-time)NOWAIT + обробка помилки

Distributed Transactions і Saga Pattern

У мікросервісах одна бізнес-операція може зачіпати кілька сервісів з різними БД. Класичні транзакції тут не працюють.

2PC (Two-Phase Commit) — класичний протокол розподілених транзакцій:

  1. Prepare phase: координатор питає всіх учасників “готові закомітити?”
  2. Commit phase: якщо всі “так” → commit; якщо хтось “ні” → rollback

Проблема: якщо координатор падає між фазами — невизначеність.

Saga Pattern — альтернатива для мікросервісів:

Замовлення: Reserve Inventory → Charge Payment → Ship Order
При збої на Ship: Refund Payment → Release Inventory

Dynamic Programming

Що таке DP і чим воно відрізняється від рекурсії

Dynamic Programming (динамічне програмування) — техніка оптимізації рекурсії через збереження результатів підзадач.

Рекурсія без DP може перераховувати одні й ті самі підзадачі мільйони разів. DP каже: “порахував раз — запам’ятай”.

Fibonacci без DP:
fib(5) → fib(4) + fib(3)
fib(4) → fib(3) + fib(2)  ← fib(3) рахується двічі!
fib(3) → fib(2) + fib(1)  ← fib(2) рахується тричі!
Складність: O(2^n)

Fibonacci з DP (мемоїзація):
fib(5) → fib(4) + fib(3)
fib(4) → fib(4) вже в кеші!
Складність: O(n)

Два підходи: Top-Down і Bottom-Up

Top-Down (мемоїзація): пишемо рекурсію, додаємо кеш. Природно, декларативно, але є overhead стеку.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Bottom-Up (табуляція): заповнюємо таблицю від базових випадків вгору. Без рекурсії, без стеку — часто швидше.

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Оптимізація: зберігаємо лише два попередніх
def fib_optimized(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Фреймворк для розв’язання DP задач

Замість заучування конкретних алгоритмів — універсальний підхід:

1. Визначити стан: що характеризує поточну підзадачу? Зазвичай: індекс + накопичені параметри (залишкова ємність, поточна сума, etc.)

2. Знайти переходи: які рішення можна прийняти в поточному стані? “Взяти елемент” або “пропустити”, “рухатись вліво” або “вправо”

3. Базовий випадок: коли відповідь відома без рекурсії?

4. Мета: що шукаємо — максимум, мінімум, кількість варіантів?

Knapsack Pattern — основа половини DP задач

Задача про рюкзак (0/1 Knapsack): Є n предметів з вагами w[i] і цінностями v[i]. Рюкзак витримує W. Максимізувати цінність.

def knapsack(weights, values, W):
    n = len(weights)
    
    @lru_cache(maxsize=None)
    def dp(i, capacity):
        if i == n or capacity == 0:   # Базовий випадок
            return 0
        
        # Не беремо предмет i
        skip = dp(i + 1, capacity)
        
        # Беремо предмет i (якщо влазить)
        take = 0
        if weights[i] <= capacity:
            take = values[i] + dp(i + 1, capacity - weights[i])
        
        return max(skip, take)
    
    return dp(0, W)

Цей самий патерн вирішує:

Відновлення елементів: не тільки значення, а й що взяли

Часто потрібно не просте “яке максимальне значення”, а “які елементи його дають”. Для цього при заповненні кешу зберігаємо рішення:

memo_choice = {}  # Зберігаємо: взяли чи пропустили

def dp(i, capacity):
    if i == n:
        return 0
    skip = dp(i + 1, capacity)
    take = values[i] + dp(i + 1, capacity - weights[i]) if weights[i] <= capacity else 0
    
    if take > skip:
        memo_choice[(i, capacity)] = 'take'
        return take
    else:
        memo_choice[(i, capacity)] = 'skip'
        return skip

# Відновлення шляху:
def restore(i, capacity):
    if i == n:
        return []
    if memo_choice[(i, capacity)] == 'take':
        return [i] + restore(i + 1, capacity - weights[i])
    else:
        return restore(i + 1, capacity)

Чистий код і архітектура

Головна ідея: код читають люди, не машини

Код пишеться один раз, але читається і змінюється десятки разів. Найдорожча операція в розробці — розібратися в чужому (або своєму старому) коді.

Чистий код — не стиль і не естетика. Це економіка: менший час на зміни = менше грошей = більше фіч.

Low Coupling і High Cohesion

Low Coupling (низька зв’язність): модулі мало знають один про одного. Зміна в одному не ламає інші.

High Cohesion (висока згуртованість): все, що разом відноситься до однієї відповідальності — знаходиться разом.

// Погано: висока зв'язність між модулями
// OrderService знає про деталі PaymentService
func (o *OrderService) CreateOrder(items []Item, cardNumber string, cvv string) {
    // бізнес логіка замовлення...
    charge(cardNumber, cvv, total)  // знає деталі платіжки!
}

// Добре: залежимо від абстракції
type PaymentProvider interface {
    Charge(amount float64) error
}

func (o *OrderService) CreateOrder(items []Item, payment PaymentProvider) {
    // бізнес логіка замовлення...
    payment.Charge(total)  // не знає, як саме відбувається оплата
}

SOLID — принципи, не правила

SOLID — абревіатура п’яти принципів проєктування:

S — Single Responsibility Principle (Принцип єдиної відповідальності) Клас/функція має одну причину для зміни. Не “робить одну річ” (це занадто вузько), а “змінюється через одну причину”.

O — Open/Closed Principle (Принцип відкритості/закритості) Відкрито для розширення (додавання нових типів), закрито для змін (не потрібно змінювати існуючий код). Досягається через поліморфізм і абстракції.

L — Liskov Substitution Principle (Принцип підстановки Ліскова) Підтип має повністю замінювати базовий тип без порушення поведінки. Якщо Duck реалізує Bird, то fly(Bird) має працювати з будь-яким Duck.

I — Interface Segregation Principle (Принцип розділення інтерфейсів) Краще кілька вузьких інтерфейсів, ніж один широкий. Клієнт не повинен залежати від методів, які не використовує.

D — Dependency Inversion Principle (Принцип інверсії залежностей) Залежи від абстракцій, не від конкретних реалізацій. Модулі вищого рівня не залежать від модулів нижчого.

Декомпозиція зверху вниз

Пиши код так, щоб перші кілька функцій розповідали що робить програма, без деталей як. Деталі — нижче.

// Читається як текст — одразу зрозуміло що відбувається
func HandleUserCommand(input string) string {
    cmd := parseCommand(input)
    if !isValidCommand(cmd) {
        return suggestSimilarCommands(cmd)
    }
    return executeCommand(cmd)
}

// Реалізація кожного кроку — окремо
func suggestSimilarCommands(input string) string {
    known := getAllKnownCommands()
    similar := findSimilar(input, known)  // Levenshtein distance
    return formatSuggestions(similar)
}

Абстракції в реальному світі (SOLID скрізь)

SOLID — не академічна теорія. Це те, як побудований весь великий софт:

Linux syscalls — твій код не знає, як ядро читає файл. Ти просто викликаєш read(). Абстракція приховує 10 000 рядків коду.

Файлові системи — ext4, btrfs, NTFS, і навіть FUSE (своя FS) — всі реалізують один інтерфейс. Open/Closed у чистому вигляді.

Завантажувані модулі ядра (Loadable Kernel Module) — кожен драйвер реалізує єдиний інтерфейс. Підключай і від’єднуй без перекомпіляції ядра.

POSIX pthreads — мільярди програм на всіх платформах використовують один API. Жодна не знає деталей реалізації.

Kafka / RabbitMQ — надсилаєш повідомлення через абстракцію RPC. Як саме воно зберігається в WAL — не твоя відповідальність.

Unix Philosophy: “Write programs that do one thing and do it well” — SRP з 1970-х.

Bash pipelines: cat file | grep error | sort | uniq -c — кожна програма робить одне, з’єднані абстракцією pipe. Ти ніколи не змінював код grep, бо він змінив формат pipe — бо є абстракція.

Premature Optimization і Premature Abstraction

Два однаково шкідливих явища:

"Premature optimization is the root of all evil" — Knuth
"Premature abstraction is evil" — загальна мудрість

Premature Optimization: оптимізувати те, що ще не є bottleneck’ом. 9 наносекунд різниці між switch і vtable при запиті в БД, який займає 200ms — це 0.0000045% часу. Irrelevant.

Premature Abstraction: вводити інтерфейси і шари там, де ще невідомо, що буде змінюватись. Результат — BBOM (Big Ball of Mud) з абстракціями.

Правило: Measure first, optimize where it matters. За законом Амдала (Amdahl’s Law) — загальне прискорення обмежене найповільнішою частиною системи.

Еволюційна розробка vs “великий дизайн спочатку”

Спроба продумати всю архітектуру заздалегідь (Waterfall) провалюється, бо вимоги змінюються. Краще:

  1. Почати просто — без зайвих абстракцій
  2. Писати код, що вирішує поточну задачу
  3. Рефакторити, коли бачиш повторення або зміни вимог
  4. Абстракції з’являються, коли стає зрозуміло, що змінюватиметься
"Проект починається не з абстракцій, 
а абстракції починаються з проекту"

Golang Scheduler

Навіщо Go зробив свій планувальник

Стандартні потоки ОС (OS threads) важкі: ~1-8 МБ пам’яті на поток, дорогий context switch (перемикання контексту) через системний виклик в ядро.

Горутини в Go — легкі: ~2-8 КБ початково, ростуть динамічно. Можна запустити мільйони горутин. Перемикання відбувається всередині Go runtime, без системного виклику.

Три сутності: G, P, M

G (Goroutine): легковага “задача”. Стек, реєстри, стан. Тисячі і мільйони.

P (Processor): логічний процесор. Черга горутин (Local Run Queue — LRQ), які він виконує. Кількість P = GOMAXPROCS (зазвичай = кількість CPU ядер).

M (Machine): справжній потік ОС. Виконує один P. Може бути більше M, ніж P (якщо P заблокований на системному виклику).

OS Thread (M) → P (логічний процесор) → G, G, G... (горутини)

Алгоритм пошуку горутин для виконання

Кожен P постійно шукає роботу за таким алгоритмом:

Крок 1 (з імовірністю 1/61): перевіряємо Global Run Queue (GRQ)
  → Дорогий виклик з блокуванням (lock), тому рідко
  → Але якщо ніколи не перевіряти — горутини в GRQ голодуватимуть

Крок 2: Local Run Queue (LRQ) — власна черга P
  → Найшвидше, без синхронізації, без locks

Крок 3: Global Run Queue (GRQ)
  → Берем горутини звідси, якщо LRQ порожня

Крок 4: NetPoller (fast path, non-blocking)
  → Горутини, що чекали мережевих подій і вже готові
  → epoll/kqueue повідомив ядро: "є дані для читання"
  → Забираємо пачку, решту розподіляємо по іншим P і GRQ

Крок 5: Work Stealing (крадіжка роботи)
  → Тільки за умов: LRQ/GRQ/NetPoller порожні І
    (поточний M починає spinning АБО spinning M < зайнятих P / 2)
  → Крадемо половину LRQ у іншого P

Крок 6: Допомагаємо GC (Garbage Collector)
  → Якщо GC зараз активний — допомагаємо з marking

Крок 7: GRQ знову (ще одна спроба)

Крок 8: NetPoller (blocking)
  → Блокуємось до появи I/O подій (з таймаутом pollUntil)

Крок 9: Park M
  → Нічого немає → поміщаємо потік у пул сплячих потоків

Spinning і чому це важливо

Spinning M (крутящийся поток) — M, що активно шукає роботу замість того, щоб засинати. Це свідоме рішення: краще витратити трохи CPU, ніж платити за пробудження сплячого потоку (це ~мкс затримка).

Але spinning M — дорого при бездіяльності. Тому Go обмежує: spinning_Ms <= зайняті_Ps / 2.

NetPoller: як Go обробляє мережу

Замість блокуючих мережевих викликів Go використовує epoll (Linux) / kqueue (macOS) / IOCP (Windows) — системні механізми асинхронного I/O.

Горутина, що чекає мережевих даних, паркується (не займає M). Окремий поток слідкує за подіями. Коли дані прийшли — горутина повертається в чергу.

Це і є причина, чому Go-сервери витримують сотні тисяч одночасних з’єднань без проблем.

Work Stealing: балансування між ядрами

Якщо одне P завалено горутинами, а інше простоює — голодуюче P краде половину LRQ завантаженого P. Автоматичне балансування навантаження між CPU ядрами без явного керування.

Як вчити алгоритми

Що насправді потрібно для 80% співбесід

Не потрібно знати всі алгоритми. Потрібна база і навик розпізнавання патернів:

80% часу → array, list, string, stack, hash table, queue, set,
           sorted set, sorting, binary search, heap, prefix sums,
           two pointers, sliding window, BFS, DFS

10% часу → recursion, trees (базові приклади)

10% часу → dynamic programming (базові приклади)

Принцип Парето: 20% тем дають 80% питань на реальних співбесідах.

Active Recall: чому пасивний перегляд не працює

Active Recall (активне пригадування) — техніка навчання, де ти витягуєш інформацію з пам’яті через зусилля, а не пасивно споживаєш.

Коли мозок змушений згадувати через “біль” невизначеності — він будує сильніші нейронні зв’язки. Наступного разу та сама інформація витягується швидше і легше.

Пасивний перегляд відео або читання коду — не працює. Мозку немає сенсу запам’ятовувати те, що завжди доступне ззовні.

Практично:

Spaced Repetition: як не забути

Spaced Repetition (інтервальне повторення) — повторюй матеріал в момент, коли починаєш трохи забувати. Тоді нейронний зв’язок зміцнюється найефективніше.

Крива забування Еббінгауза: без повторення людина забуває ~50% за перший день, ~70% за тиждень. Кожне повторення “скидає” криву і уповільнює забування.

Рекомендовані інтервали: 1 день → 3 дні → 1 тиждень → 2 тижні → 1 місяць.

Але краще — за відчуттями: “починаю трохи забувати → повторюю”. Не “забув повністю → вчу знову”.

Практично для алгоритмів:

Скільки часу витрачати на одну задачу

Є час → думай кілька днів, крути в голові

Немає часу →
  30 хв: пробуй різні патерни
  Нічого → підглянь ІДЕЮ (не код)
  Спробуй закодити сам
  Не вийшло → подивись конструкції коду, закрий
  Закодуй по пам'яті
  Розбери рішення крок за кроком
  Виклади патерн → додай до списку для повторення

Стрес уповільнює навчання

Мозок у стресі переходить в режим “бий або тікай” — ресурси йдуть на виживання, а не на навчання. Підвищений кортизол знижує здатність до формування нових нейронних зв’язків.

Переконай себе, що тобі цікаво, а не страшно. Це не метафора — мозок буквально краще запам’ятовує в стані зацікавленості.

Критичне мислення

Чому це важливо для розробника

Технічні дискусії, code review, вибір архітектурних рішень, співбесіди — всюди є аргументи, контраргументи, маніпуляції і когнітивні пастки. Без критичного мислення легко прийняти неправильне рішення або піддатися маніпуляції.

Confirmation Bias (упередженість підтвердження)

Ми схильні шукати інформацію, що підтверджує наші погляди, і ігнорувати те, що суперечить.

У розробці: вивчив ООП → бачиш ООП-рішення скрізь. Вивчив SOLID → хочеш абстракції всюди. Зайнявся low-level → оптимізуєш кожен байт навіть там, де це не має значення.

Як протидіяти: активно шукай найкращі аргументи проти своєї позиції. Питай: “Що могло б змінити мою думку?”

Straw Man Fallacy (підміна тези)

Замість відповіді на реальний аргумент — відповідаєш на викривлену версію.

Оригінал: “SOLID — корисні принципи, які застосовуються за ситуацією.” Straw Man: “Ти кажеш завжди робити 100 класів і 50 інтерфейсів на кожну функцію?”

Як розпізнати: “Отже ти хочеш сказати, що…” — і далі щось, чого ти не казав.

Ad Hominem (атака на особистість)

Замість критики аргументу — критика людини:

Аргумент не стає хибним від того, хто його висловлює.

Generalization Bias (надмірне узагальнення)

“Я ніколи не зустрічав цей алгоритм на роботі → алгоритми непотрібні.” “Мій прадід курив і прожив 100 років → куріння нешкідливе.”

Один приклад (або відсутність прикладу) — не доказ загальної закономірності.

False Dilemma (хибна дилема)

Представлення ситуації як вибору між двома варіантами, коли є інші:

Polarized Thinking (чорно-біле мислення)

Світ ділиться на “повністю добре” і “повністю погане”, без відтінків. У реальності більшість технічних рішень — trade-off (компроміс), а не абсолют.

Як думати краще: алгоритм

1. Сформулюй проблему максимально конкретно
   ("код повільний" → "запит займає 500ms при 1000 записах")

2. Розділи факти від думок
   Факт: "benchmark показав 500ms"
   Думка: "це через погані абстракції"

3. Знайди найсильніші аргументи проти своєї гіпотези

4. Виміряй (measure, don't guess)
   Profiler, benchmark, метрики — перед оптимізацією

5. Прийми рішення, явно зазначивши невизначеність
   "Ймовірно X, тому що Y, але можливо Z"

6. Перевір результат і оновлюй модель

Нарцисизм у IT і як не згоріти

Токсичні колеги, хейт в інтернеті, деструктивне code review — реальність IT. Важливо розрізняти:

Здорова критика: “Цей підхід має проблему X, бо Y. Розглянь альтернативу Z.”

Токсична поведінка: вирвати деталь з контексту, ігнорувати суть, атака на особистість, “допомога” через приниження.

Ознаки: прагнуть не вирішити проблему, а довести перевагу над тобою. Реагують агресивно на будь-яку незгоду. Закривають коментарі (бо бояться аргументів у відповідь).

Стратегія: аргументуй фактами і вимірами. Якщо людина не реагує на факти — це не технічна дискусія, а щось інше. Не трать на це енергію.

Висновок: одна ідея в різних формах

Усі теми цієї статті — прояви однієї фундаментальної ідеї:

Декомпозиція складного на просте через правильні абстракції.

Навчись думати так — і будь-яка нова тема буде лише новим виявом знайомого принципу.