Что мы прошли

За 19 модулей мы прошли путь от Big-O до построения real-time pipeline. Ключевые вехи:

• Big-O и память. Не зубрить формулы, а понимать, почему list[i] — это O(1), а list.insert(0) — O(n). Cache-линии, pointer chasing, branch prediction.
• Массивы и динамические массивы. Почему list.append() амортизированно O(1) через growth factor.
• Связные списки. Почему они хороши для O(1) insert и плохи для random access — pointer chasing убивает cache.
• Стеки, очереди, deque. Right tool для своей задачи: list.append/pop — O(1), pop(0) — O(n), deque — обе O(1).
• Hash maps. Среднее O(1) через хеширование, worst case O(n) через коллизии. CPython dict — open addressing с probing.
• Деревья и BST. Балансировка, AVL, B-tree. Почему BST в Python проигрывает SortedList.
• Heap. Min-heap для top-K за O(n log k).
• Графы. Adjacency list vs matrix, BFS vs DFS. Сложности и память.
• Сортировки. Timsort, merge sort, quicksort. Когда какая.
• Поиск. Linear vs binary vs hash. Equality vs range.
• Рекурсия и divide-and-conquer. Стек, лимит, master theorem.
• Applied patterns. Batch, streaming, dedup, top-K, k-way merge.
• Capstone. Всё вместе в реальном pipeline.

Чему вы научились (надеюсь)

Не «выучили список алгоритмов». Что вы должны уметь после курса:

1. Видеть задачу и сразу выбирать структуру. «Нужна дедупликация» -> set. «Нужен top-K» -> heapq.nlargest. «Нужно скользящее окно» -> deque. Это рефлекс, не размышление.

2. Прикидывать память без запуска. «100k уникальных users в Counter = 7 МБ, поместится». «10 млн tuples = 1 ГБ, поместится». «10 млрд хешей в set = 1 ТБ, не поместится».

3. Понимать, почему ETL медленный. «У нас if x in big_list — O(n), исправление на set даст 1000x». «Сортируем 1М на каждый запрос — Counter решит за O(1) на ingest».

4. Не бояться железа. Cache miss = 100 ns. RAM = 100 ns. SSD = 100 us. Network = 1 ms. Эти числа должны быть в голове.

5. Различать big-O и реальную скорость. O(log n) с большим overhead может быть медленнее O(n) на маленьких данных. Cache locality матерится.

Типичные ошибки джунов

Чем чаще всего я вижу:

Ошибка 1: x in list вместо set. На больших данных это O(n²). Самая частая причина медленных ETL.

Ошибка 2: sorted()[:k] вместо heapq.nlargest(k). Полная сортировка ради 10 элементов.

Ошибка 3: list.pop(0) в скользящем окне. O(n) на каждое удаление. deque решает за O(1).

Ошибка 4: dict с миллионами записей вместо tuple/numpy. Overhead Python съедает гигабайты.

Ошибка 5: преждевременная оптимизация. Профилировать ДО оптимизации. Часто bottleneck — не там, где кажется.

Ошибка 6: рекурсия на глубоких данных. RecursionError или segfault. Итерация с явным стеком — спасение.

Ошибка 7: setrecursionlimit(106).** Не помогает, ведёт к segfault. Алгоритм нужно менять, не лимит.

Если избегаете этих семи ошибок — вы уже выше многих сениоров.

Что НЕ прошли (продвинутые темы)

DSA — большая область. Мы покрыли базу. Дальше есть:

Продвинутые структуры

• Skip list. Вероятностная структура, альтернатива balanced BST. Используется в Redis ZSET.
• B-tree, B+ tree. Многоуровневые деревья для disk-based индексов. Сердце PostgreSQL/MySQL.
• LSM tree. Log-Structured Merge tree. Write-optimized структура. Cassandra, RocksDB, ClickHouse.
• Trie. Деревья префиксов для поиска по строкам. Autocomplete, IP routing.
• Disjoint Set Union (Union-Find). Для clustering, MST (Kruskal), online connectivity.
• Suffix array, suffix tree. Для substring search в больших текстах.
• Persistent data structures. Immutable с эффективным копированием. Базовые в Clojure/Haskell.

Продвинутые алгоритмы

• Dynamic programming. Memoization, bottom-up DP, classic problems (knapsack, LCS, edit distance).
• Graph algorithms. Dijkstra, Bellman-Ford (shortest path), Floyd-Warshall (all pairs), MST (Prim, Kruskal), max flow (Ford-Fulkerson).
• String matching. KMP, Boyer-Moore, Rabin-Karp, Aho-Corasick.
• Approximation algorithms. Greedy, LP relaxation. Для NP-hard задач.

Probabilistic structures

• HyperLogLog. Approximate cardinality count за O(log log n) bits.
• Count-Min Sketch. Approximate frequencies.
• Cuckoo filter. Альтернатива Bloom с поддержкой delete.
• MinHash, SimHash. Approximate similarity для документов.

Distributed computing

• MapReduce paradigm. Hadoop, основа для всех остальных.
• Spark. RDD, DataFrame, Dataset. Shuffle internals.
• Stream processing. Flink, Kafka Streams. Event time vs processing time. Watermarks.
• Distributed consensus. Raft, Paxos. Основа etcd, ZooKeeper, Kafka.
• CAP theorem, BASE vs ACID. Trade-offs distributed systems.

Книги и материалы

Базовые (после этого курса):

• Sedgewick «Algorithms», 4th edition. Самая дружелюбная книга по алгоритмам. С анимациями и кодом на Java.
• CLRS «Introduction to Algorithms», 4th edition. Стандартная фундаментальная книга, формальный подход. Для системного понимания.
• «Grokking Algorithms» (Aditya Bhargava). Очень наглядно для быстрого старта.

Продвинутые:

• «Designing Data-Intensive Applications» (Martin Kleppmann). Если работаете с большими данными — это обязательное чтение. Главы про индексы (B-tree, LSM), репликацию, partitioning.
• «The Algorithm Design Manual» (Skiena). Практичная, со списками war stories.
• «Algorithms on Strings, Trees, and Sequences» (Gusfield). Если занимаетесь bioinformatics или поиском.
• CMU 15-445 Database Systems. Лекции бесплатно онлайн. Лучшая по практическим аспектам БД.

Для практики:

• LeetCode. Алгоритмические задачи с разбором решений. Для интервью.
• Project Euler. Математические задачи через программирование.
• Codeforces. Соревновательное программирование.

Дальнейший путь для DE

Если ваша цель — стать middle/senior Data Engineer, рекомендую такой план на ближайшие 6-12 месяцев:

1. DBMS internals. Понять, как работает PostgreSQL индекс (B-tree), какие виды join (hash, merge, nested), execution plan. Курс CMU 15-445.

2. Distributed systems. Прочитать «Designing Data-Intensive Applications». Понять консистентность, репликацию, partitioning.

3. Spark. Не «как написать query», а «как Spark выполняет shuffle». Прочитать про Catalyst, Tungsten, shuffle internals.

4. Streaming. Flink или Kafka Streams. Event time vs processing time. Watermarks. State management.

5. Specific DBs. ClickHouse (LSM + columnar), Cassandra (Bloom + LSM), Neo4j (graph), Elasticsearch (inverted index). Понять, какая БД под какой workload.

6. Practical algorithms. Решить ~100 LeetCode задач medium-уровня. Не для собеседований, для тренировки видеть структуры в задачах.

Финальный совет

Не пытайтесь выучить всё DSA сразу. После этого курса у вас есть карта. Дальше вы будете попадать в ситуации, где нужно конкретное знание — и тогда копать глубже именно туда.

Пример: «нужно быстро считать unique users на миллиарде событий» -> копать HyperLogLog. «Pipeline в Spark медленный» -> копать shuffle internals. «БД с большим числом записей тормозит» -> копать индексы и query plans.

Профессионал DE — это не «знает все алгоритмы», а «видит задачу и знает, куда копать». Этому учит только практика.

Спасибо за курс

Если вы дошли до этого урока — вы реально вложились в самообразование. Это видно. Большинство людей бросают такие курсы на третьем модуле.

Главное, что вы должны вынести: выбор структуры данных — это 90% производительности. Микро-оптимизации и распараллеливание — оставшиеся 10%. Когда видите медленный код — сначала смотрите структуры, потом всё остальное.

Удачи в работе. Если этот курс помог — напишите, какой следующий курс хотели бы.