интервью-паттерны, не курс CSinterview patterns, not a CS course

Алгоритмы и структуры данныхAlgorithms and data structures

Не учебник по CS — набор паттернов и триггеров их распознавания в условии задачи, с примерами на C++. Дополняет kb/algorithms.md (текстовая шпаргалка) страницами того же формата, что stl/ и libraries/. Каркас: ~60 паттернов по 14 категориям, страницы ещё не написаны.Not a CS textbook — a set of patterns and the triggers for recognizing them in a problem statement, with C++ examples. Complements kb/algorithms.md (the text cheat sheet) with pages in the same format as stl/ and libraries/. Skeleton: ~60 patterns across 14 categories, pages not yet written.

Массивы и строкиArrays & strings

Two Pointersпара/тройка в отсортированном массивеa pair/triple in a sorted array Sliding Windowподмассив/подстрока с условиемa subarray/substring with a condition Prefix Sumпрефиксные суммы, разностный массивprefix sums, difference array Kadane's Algorithmмаксимальный подмассив по суммеmaximum subarray by sum Dutch National Flagразбиение массива на 3 группы за один проходpartitioning an array into 3 groups in one pass Merge Intervalsслияние пересекающихся отрезковmerging overlapping intervals Matrix Traversalспираль, транспонирование, поворот на местеspiral, transpose, in-place rotation

ПоискSearching

Binary Searchклассический + "минимальное X при котором predicate true"classic + "minimum X for which the predicate is true"interview Binary Search on Answerпоиск по значению ответа, а не по индексуsearching over the answer's value, not an index Ternary Searchунимодальные функцииunimodal functions Rotated Sorted Arrayпоиск в развёрнутом отсортированном массивеsearching in a rotated sorted array

СортировкиSorting

Quicksort / Mergesort / Heapsortпринцип и сложности сравненияthe mechanism and complexity comparison Counting / Radix / Bucket Sortнецентрированные на сравнении сортировкиnon-comparison-based sorts Custom Comparatorsкомпараторы, устойчивость сортировкиcomparators, sort stability Partial Sort / nth_elementчастичная сортировка без полного упорядочиванияpartial sorting without full ordering

ХешированиеHashing

Frequency Countinghash map подсчёт частотfrequency counting Two Sum / Group Anagramsканонические паттерны на хеш-таблицахcanonical hash-table patternsinterview Canonicalization / Dedupхеширование для дедупликации и канонизацииhashing for deduplication and canonicalization

КучаHeap

Top-K ElementsK наибольших/наименьших через heapthe K largest/smallest via a heapinterview K Closest / K Largestчастный случай top-K с метрикой расстоянияa top-K special case with a distance metric Merge K Sorted Listsслияние через min-heapmerging via a min-heap Median from Data Streamдва heap — max-heap снизу, min-heap сверхуtwo heaps — a max-heap below, a min-heap above

Стек и очередьStack & queue

Monotonic Stacknext greater/smaller elementinterview Monotonic Queueмаксимум в скользящем окнеthe maximum in a sliding window Bracket Validation / Calculatorвалидация скобок, вычисление выраженийbracket validation, expression evaluation Queue via Two Stacksклассическая реализационная задачаa classic implementation exercise

Связные спискиLinked lists

Fast & Slow Pointersцикл, середина, палиндромcycle, middle, palindromeinterview Reverse Linked Listцеликом, группами, между позициямиwhole, in groups, between positionsinterview Merge Two/K Sorted Listsслияние отсортированных списковmerging sorted lists Detect & Remove CycleFloyd's cycle detection

ДеревьяTrees

DFS Traversalpreorder/inorder/postorder, рекурсивно и итеративно, recursive and iterativeinterview BFS / Level-Orderобход по уровнямlevel-by-level traversal BST Operationsinsert/delete/validate Lowest Common Ancestorнаименьший общий предокthe lowest common ancestorinterview Diameter / Height / Balanceметрики дерева через один DFS-проходtree metrics via a single DFS pass Serialize / Deserializeсохранение и восстановление структуры дереваsaving and restoring a tree's structure Trieпрефиксное деревоa prefix tree

ГрафыGraphs

BFS / DFS / Componentsобход графа, связные компонентыgraph traversal, connected componentsinterview Topological SortKahn's / DFS-based Dijkstraкратчайший путь, неотрицательные весаshortest path, non-negative weights Bellman-Fordкратчайший путь с отрицательными весамиshortest path with negative weights Floyd-Warshallкратчайшие пути между всеми парамиall-pairs shortest paths Union-Find / DSUpath compression, union by rankpath compression, union by rankinterview Minimum Spanning TreeKruskal / Prim Cycle Detectionв направленном и ненаправленном графеin directed and undirected graphs Bipartite Checkпроверка двудольности графаchecking whether a graph is bipartite

Динамическое программированиеDynamic programming

1D DPclimbing stairs, house robberinterview 2D DPunique paths, edit distanceinterview Knapsack0/1 иand unbounded LCS / Longest Common Substringнаибольшая общая подпоследовательность/подстрокаlongest common subsequence/substring Longest Increasing SubsequenceO(n log n) через binary searchvia binary search Palindrome PartitioningDP на строкахon strings Tree DPDP на деревьяхon trees Bitmask DPсостояние как битовая маска подмножестваstate as a subset bitmask Memoization vs Tabulationи восстановление ответа по DP-таблицеand reconstructing the answer from the DP table

Backtracking

Permutations / Combinations / Subsetsгенерация всех вариантовgenerating all variantsinterview N-Queens / Sudoku Patternклассический шаблон backtrackingthe classic backtracking template Word Search / Path Findingпоиск с возвратом на сеткеbacktracking search on a grid Pruning Strategiesотсечение веток для ускорения перебораcutting branches to speed up the search

Жадные алгоритмыGreedy algorithms

Interval Schedulingпланирование непересекающихся интерваловscheduling non-overlapping intervals Activity Selectionклассическая жадная задачаthe classic greedy problem Huffman Codingпринцип построения оптимального префиксного кодаthe principle behind building an optimal prefix code When Greedy Worksдоказательство корректности, exchange argumentcorrectness proofs, the exchange argument

Битовые операцииBit manipulation

Bit Tricksпроверка/установка/снятие бита, count set bitschecking/setting/clearing a bit, counting set bits XOR Patternsпоиск уникального элемента и другие XOR-трюкиfinding a unique element and other XOR tricks Bitmask as Subsetбитовая маска как представление подмножестваa bitmask as a subset representation

Математика и теория чиселMath & number theory

GCD / LCMрасширенный алгоритм Евклидаthe extended Euclidean algorithm Sieve of Eratosthenesрешето Эратосфенаthe Sieve of Eratosthenes Fast Exponentiationбыстрое возведение в степеньfast exponentiation Modular Arithmeticобратный элемент, модульное возведение в степеньmodular inverse, modular exponentiation CombinatoricsnCr по модулюmodulo a prime

ПродвинутоеAdvanced

Sliding Window Maximumчерез monotonic dequevia a monotonic deque Reservoir Samplingслучайная выборка из потока неизвестной длиныrandom sampling from a stream of unknown length Rate Limiter Patternstoken bucket и другиеand others Segment Tree / Fenwick Treeдерево отрезков, BITsegment tree, BIT Sparse TableRMQ за O(1) на запросin O(1) per query

статус и связь с существующей шпаргалкойstatus and relation to the existing cheat sheet

Это каркас: 14 категорий и ~60 паттернов зафиксированы, страницы фич ещё не написаны. Метка interview отмечает паттерны, которые встречаются на технических собеседованиях чаще всего. При заполнении будет использоваться то же ядро, что уже есть в kb/algorithms.md (таблица сложностей, триггеры распознавания), но развёрнутое в полный формат страницы (что/зачем/как/примеры/грабли), а не сжатая шпаргалка.This is a skeleton: 14 categories and ~60 patterns are locked in, feature pages not yet written. The interview tag marks the patterns that come up most often in technical interviews. Filling this in will reuse the same core already present in kb/algorithms.md (the complexity table, recognition triggers), expanded into the full page format (what/why/how/examples/gotchas) rather than a condensed cheat sheet.