Algorithms in Practice

• Time complexity: цикли, вкладені цикли, рекурсія
• Space complexity: стек рекурсії, heap allocations, вартість копіювання структур даних і приховані витрати пам'яті
• Асимптотичний аналіз складних ітеративних та рекурсивних алгоритмів
• Аналіз ймовірнісних алгоритмів та структур даних: коли точна відповідь надто дорога

Практика
• Реальний кейс з інфраструктури Facebook — серед мільйонів клієнтів знайти того єдиного, що DDOS-ить сервіс, маючи в пам'яті лише дві змінні. Розбираємо, чому хеш-таблиця тут програє і як алгоритм 1981 р. дає O(1) пам'яті за один прохід
• Беремо реальний бекенд із CRUD-ендпоінтами. Розбираємо Big-O кожного методу. Вчимося бачити справжню ціну кожного рядка коду крізь абстракції фреймворку

• Ітеративний перебір як baseline: коректне просте рішення, від якого відштовхуємося в оптимізації
• Як з аналізу коду зрозуміти, чи пройде рішення за часом і пам'яттю, ще до написання коду
• Stress testing — техніка, якою ловлять баги, що проходять крізь звичайні unit-тести

Практика
• Closest pair of points: серед тисяч об'єктів на екрані знайти два найближчі — задача, що виникає у collision detection в іграх, фізичних симуляціях і кластеризації даних
• Convex hull: побудувати мінімальну опуклу оболонку, що охоплює задану множину точок — задача, що лежить в основі визначення меж об'єктів у комп'ютерному зорі, виявлення колізій у CAD-системах та оптимізації маршрутів

• Рекурсія як декомпозиція: звести задачу до меншої копії себе і не втратити контроль над глибиною стека
• Класичні рекурсивні задачі: fast exponentiation (fast pow), towers of hanoi algorithm, recursive expression evaluation
• Backtracking з відсіканням — як не перебирати очевидно мертві гілки
• Генерація перестановок, підмножин, розміщень, комбінацій — каркас під будь-яку переборну задачу
• Хвостова рекурсія та Tail Call оптимізація
• Beam Search: як шукати не ідеальний, а достатньо хороший розвʼязок

Практика
• Пишемо мінімальний regex engine. Чому деякі регулярки "вбивають" сервіс через catastrophic backtracking (ReDoS) — реальний клас вразливостей
• Рекурсивний спуск, що парсить і рахує арифметичний вираз з дужками й пріоритетами — той самий кістяк, що в інтерпретаторах і калькуляторах
• 8 Queens і Sudoku Solver: як рекурсивно будувати розвʼязок, швидко перевіряти обмеження та відсікати неможливі гілки до того, як перебір вибухне

• Two pointers: opposite ends і same direction — паттерни, що перетворюють O(n²) на O(n) без зміни ідеї алгоритму
• Sliding window: робота з рухомим вікном даних і умови монотонності, за яких воно працює
• Prefix sums: O(1) на запит про суму діапазону замість O(n) — фундамент під range queries
• 2D prefix sums та integral images: основа Viola–Jones face detection, що досі живе у camera hardware
• Difference arrays: bulk-оновлення діапазонів за O(1) на запит — як це працює у системах бронювання

Практика
• Алгоритм, що лежить в основі SQL JOIN, повнотекстового пошуку (inverted index у Google і Elasticsearch) та рекомендацій типу «common friends» у соцмережах
• Реалізуємо integral image — структуру з 2D prefix sums, яку у 2001 році використали в алгоритмі Viola–Jones для першого face detection у реальному часі на CPU тих років

• Інваріанти як спосіб писати код без помилок. Binary search без off-by-one — раз і назавжди, замість вгадування <= чи <
• Лінійний пошук для гри Minesweeper та Run-length encoding. Sentinel linear search
• Коренева декомпозиція (sqrt decomposition): техніка для прискорення коду. Коли segment tree — overkill?
• Binary search не по масиву, а по відповіді: шукаємо мінімальне валідне значення, коли явного відсортованого масиву взагалі немає
• Binary search на невідсортованих і «майже відсортованих» даних
• Jump search і Galloping search: коли бінарний пошук — не єдиний вихід
• Чи можливо в теорії шукати швидше ніж за log n? Нижня межа складності задачі пошуку

Практика
• git bisect як binary search по комітах: знайти один баг-коміт серед тисяч за log(n) кроків
• Реалізуємо versioned key-value store, який пам'ятає, яке значення мав ключ у будь-який момент часу
• Знайти кінець лога на S3 без сортування. Append-only лог, файли з послідовними номерами, машина впала — треба знайти найбільший номер. Сканувати весь bucket дорого (LIST коштує як PUT), верхньої межі немає
• Скільки насправді коштує «вигідний» автокредит (binary search on answer). Дилер говорить лише про розмір місячного платежу, а справжню процентну ставку — мовчки приховує

• External sort: як відсортувати 100 GB на машині з 8 GB RAM — те, що реально роблять бази даних і MapReduce
• Quick sort і Quick select: пошук k-ї статистики за O(n) і задача Dutch National Flag
• Зв’язок між Selection sort та Heap sort
• Неасимптотичні оптимізації Merge sort та Insertion sort
• Radix sort: як відсортувати 1 000 000 чисел швидше за Quick sort
• Метод Scanline: обробка подій у відсортованому порядку

Практика
• Як пришвидшити bubble sort в 2 рази, не міняючи основну ідею? А як в 50 разів?
• External merge sort на прикладі того, як PostgreSQL сортує результат ORDER BY, що не вміщається в work_mem
• Розбираємо production-кейс із MongoDB — чому сортування та побудова індексів на великих колекціях можуть впиратися в памʼять і диск

• Динамічні масиви зсередини: amortized O(1) на append, чому ріст саме ×2 і скільки реально коштує append у Python чи push_back у C++
• Як зробити зв'язний список швидким? Skip list на практиці
• Stack зсередини: реалізація через dynamic array і через linked list. Monotonic stack та як він використовується для аналізу ринку акцій
• Queue зсередини: від наївної реалізації до циклічного буфера — розбираємо, чому черга на масиві не повинна зсувати всі елементи після кожного pop, як head і tail перетворюють масив на кільце
• Heap та priority queue: структура для ситуацій, де дані постійно змінюються, але нам завжди треба швидко дістати “найважливіший” елемент

Практика
• TTL у Redis: як expiry мільйонів ключів робиться без сканування всієї бази
• Перевірка коректності XML та RPN для обчислення виразів
• Top-K найпопулярніших елементів в потоці даних
• Union-Find: міста зʼєднуються дорогами, користувачі — у кластери. Як підтримувати це ефективно?
• LRU cache: задача з реальних кешів, браузерів та баз даних
• Як написати свій простий Event loop?

• Коли жадібність взагалі коректна: exchange argument замість «здається, спрацює»
• Кешування як greedy-задача: чому LRU — це лише евристика. Який алгоритм кешування оптимальний?
• Huffman coding: як побудувати оптимальний код без втрат — те, що всередині gzip, JPEG і HTTP-стиснення
• Оптимальне планування подій: коли жадібний підхід працює?
• Minimum Spanning Tree через Kruskal/Prim: найдешевший спосіб з'єднати все — від мереж до кластеризації

Практика
• Реалізуємо Huffman-кодер і стискаємо реальний текстовий файл
• Interval scheduling: максимум несуперечливих задач — основа планувальників, бронювань і розподілу ресурсів

• Чому хеш-таблиці працюють швидко?
• Хеш-функції й колізії: chaining vs open addressing, linear probing, load factor і чому resize неминучий
• Парадокс днів народжень (birthday paradox): чому колізії виникають набагато раніше, ніж здається?
• Bloom Filter: як за крихітну памʼять відповідати “цього точно немає” з ризиком false positive — і економити дорогі походи в БД, як у Cassandra чи Bigtable
• HyperLogLog: порахувати кількість унікальних серед мільярдів за кілька кілобайт — як це рахує unique visitors аналітика
• Rabin–Karp: хешування рядка для пошуку патерну й rolling hash, на якому будується дедуплікація і rsync

Практика
• LSH (Locality-Sensitive Hashing) — як швидко знаходити схожі обʼєкти серед мільйонів, не порівнюючи кожен з кожним
• Reservoir sampling: чесний випадковий семпл із потоку невідомої довжини — те, що працює в MapReduce та аналітиці на льоту
• Shuffle array: як чесно перемішати масив так, щоб кожна перестановка мала однакову ймовірність — від Fisher–Yates до типових помилок у “random sort”, які непомітно ламають випадковість

• Від рекурсії з memoization до bottom-up таблиці: одна й та сама ідея під двома кутами, і коли який вигідніший за пам'яттю
• Edit distance (Левенштейн): скільки правок між двома рядками — основа spell-check, fuzzy search і автокорекції
• Sequence alignment: git diff, LCS і той самий алгоритм, що вирівнює ДНК у біоінформатиці
• Задача про гру в Blackjack. Як dynamic programming допомагає рахувати не просто найкращий хід зараз, а найкращу стратегію на кілька кроків уперед
• Задача пакування рюкзака (knapsack problem): ресурсів мало, варіантів багато, а вибрати треба найкращу комбінацію
• Seam Carving — як зменшити картинку, не обрізаючи головне: алгоритм знаходить найменш помітні шляхи пікселів і прибирає саме їх.

Практика
• Реалізуємо edit distance і будуємо на ньому мінімальний «did you mean?» — той самий кістяк, що в пошуку й текстових редакторах
• Як LaTeX та Microsoft Word вирівнюють текст по ширині рядка?
• Robot paths — як навчити робота рахувати всі можливі маршрути на 2d площині?

• Як ефективно представити граф у памʼяті: adjacency list, matrix, edge list і CSR
• DFS і BFS як два погляди на обхід графу
• Topological sort та виявлення циклів: порядок збірки, розв'язання залежностей, dependency hell у пакетних менеджерах
• Знаходження найкоротших шляхів: Dijkstra vs. Bellman-Ford
• Бінарні дерева пошуку та як їх балансувати: AVL, Treap. Balanced binary search tree vs. randomized tree
• Trie і Ternary Search Tree для префіксного пошуку

Практика
• State machine як граф: вершини — стани системи, ребра — дозволені переходи, і граф ніде не заданий явно
• Пишемо web crawler на BFS — та сама модель, що в основі індексаторів пошуковиків
• Автодоповнення на Trie/TST: префіксний пошук із ранжуванням за популярністю — те, що відпрацьовує під рядком пошуку на кожному великому сайті
• Lowest common ancestor через binary lifting