📐 Big-O ReasoningОценка сложности Big-O▾
Always state the complexity of your approach out loud, before coding, and reconfirm after. Data engineers work at scale (billions of rows/day), so connect to "what happens at 109".
Всегда формулируй сложность своего подхода вслух, до кода и подтверждай после. Дата-инженеры работают на масштабе (миллиарды строк/день), поэтому увязывай с вопросом «что будет на 109».
Complexity ladder (best → worst)Лестница сложности (лучшая → худшая)
| n size | Safe complexity for ~1s |
|---|---|
| n ≤ 10–12 | O(n!) / O(2ⁿ) — brute force / backtracking OK |
| n ≤ ~5,000 | O(n²) |
| n ≤ 10⁶ | O(n log n) — sort-based |
| n ≤ 10⁸+ | O(n) / O(log n) — single pass, hashmap, two-pointer |
| Размер n | Безопасная сложность на ~1 сек |
|---|---|
| n ≤ 10–12 | O(n!) / O(2ⁿ) — brute force / backtracking приемлемы |
| n ≤ ~5 000 | O(n²) |
| n ≤ 10⁶ | O(n log n) — на основе сортировки |
| n ≤ 10⁸+ | O(n) / O(log n) — один проход, hashmap, два указателя |
Reasoning rulesПравила оценки
- Drop constants and lower-order terms: O(2n+5) → O(n).
- Sequential code adds; nested loops multiply.
- Amortized vs worst-case: dynamic array append is O(1) amortized, O(n) on resize. Hashmap lookup O(1) average, O(n) worst (collisions).
- Space includes recursion stack: DFS on a tree is O(h) stack; on a skewed tree h = n.
- Sorting is the default O(n log n) tool; if you need better, look for hashing / counting / bucketing.
- Отбрасывай константы и младшие члены: O(2n+5) → O(n).
- Последовательный код складывается; вложенные циклы умножаются.
- Амортизированная vs худшая сложность: append динамического массива — O(1) амортизированно, O(n) при resize. Lookup в hashmap — O(1) в среднем, O(n) в худшем случае (коллизии).
- Пространство включает стек рекурсии: DFS по дереву — стек O(h); на перекошенном дереве h = n.
- Сортировка — инструмент O(n log n) по умолчанию; если нужно лучше, ищи хеширование / подсчёт / бакетинг.
🧩 Core Patterns — when to reach for whatКлючевые паттерны — когда что применять▾
| Signal in the problem | Pattern | Typical cost |
|---|---|---|
| "count / dedupe / seen before / pair sums to target" | Hashmap / set | O(n) time, O(n) space |
| Sorted array, "pair / triplet", in-place | Two pointers | O(n) after sort |
| "contiguous subarray/substring", "window of size k", "longest/shortest ... with constraint" | Sliding window | O(n) |
| "top-k / k smallest / k closest / merge k / running median" | Heap (priority queue) | O(n log k) |
| "shortest path (unweighted)", "level order", "min steps" | BFS | O(V+E) |
| "connected components", "reachability", "cycle", "topological order" | DFS / Union-Find / topo | O(V+E) |
| "ancestor / path / depth / BST" | Tree traversal (DFS) | O(n) |
| "overlapping ranges / merge / meeting rooms" | Intervals (sort by start) | O(n log n) |
| "order doesn't matter but values cluster", small range | Counting / bucket sort | O(n+k) |
| "choices / combinations / partitions", n small | Backtracking | exponential |
| "min/max ways, overlapping subproblems" | DP / memoization | states × transition |
| Сигнал в задаче | Паттерн | Типичная цена |
|---|---|---|
| «подсчитать / дедуплицировать / видели раньше / пара с суммой = target» | Hashmap / set | O(n) время, O(n) память |
| Отсортированный массив, «пара / тройка», in-place | Два указателя | O(n) после сортировки |
| «непрерывный подмассив/подстрока», «окно размера k», «самый длинный/короткий ... с ограничением» | Скользящее окно | O(n) |
| «top-k / k наименьших / k ближайших / merge k / running median» | Heap (priority queue) | O(n log k) |
| «кратчайший путь (невзвешенный)», «level order», «минимум шагов» | BFS | O(V+E) |
| «компоненты связности», «достижимость», «цикл», «топологический порядок» | DFS / Union-Find / topo | O(V+E) |
| «предок / путь / глубина / BST» | Обход дерева (DFS) | O(n) |
| «пересекающиеся интервалы / merge / meeting rooms» | Интервалы (сортировка по началу) | O(n log n) |
| «порядок не важен, но значения кластеризуются», малый диапазон | Подсчёт / bucket sort | O(n+k) |
| «варианты / комбинации / разбиения», малое n | Backtracking | экспоненциальная |
| «мин/макс способов, перекрывающиеся подзадачи» | DP / мемоизация | состояния × переход |
Two pointers — three flavorsДва указателя — три варианта
- Opposite ends: sorted-pair-sum, palindrome, container-with-water. Move the side that can improve the answer.
- Same direction (fast/slow): cycle detection (Floyd), remove duplicates in place, find midpoint.
- Read/write pointer: in-place compaction (move zeros, remove element).
- С противоположных концов: sorted-pair-sum, палиндром, container-with-water. Двигай ту сторону, которая может улучшить ответ.
- В одном направлении (быстрый/медленный): обнаружение цикла (Floyd), удаление дублей in-place, поиск середины.
- Read/write указатель: in-place уплотнение (передвинуть нули, удалить элемент).
Sliding window — the templateСкользящее окно — шаблон
def window(s): left = 0; state = {} # counts/freq in window best = 0 for right in range(len(s)): add(s[right], state) # expand right while invalid(state): # shrink from left remove(s[left], state); left += 1 best = max(best, right - left + 1) return best
right-left+1 > k. Variable window: shrink with a while until valid again. Mixing these up is the #1 bug.right-left+1 > k. Переменное окно: сжимай с помощью while, пока не станет валидным. Путаница здесь — самый частый баг.BFS vs DFSBFS vs DFS
| BFS | DFS | |
|---|---|---|
| Structure | Queue (deque) | Stack / recursion |
| Best for | Shortest path (unweighted), level order | Path existence, components, cycles, topo, backtracking |
| Space | O(width) | O(depth) |
| Shortest path? | Yes (unweighted) | No (not guaranteed) |
| BFS | DFS | |
|---|---|---|
| Структура | Queue (deque) | Stack / рекурсия |
| Лучше для | Кратчайший путь (невзвешенный), level order | Существование пути, компоненты, циклы, topo, backtracking |
| Память | O(ширина) | O(глубина) |
| Кратчайший путь? | Да (невзвешенный) | Нет (не гарантируется) |
🗃️ Data Structures — costs & gotchasСтруктуры данных — цена и подводные камни▾
| Structure | Access | Search | Insert | Delete | Notes |
|---|---|---|---|---|---|
| Dynamic array | O(1) | O(n) | O(1)*amort | O(n) | append amortized O(1); insert-mid O(n) |
| Hashmap / set | — | O(1) avg | O(1) avg | O(1) avg | O(n) worst; unordered |
| Balanced BST / TreeMap | — | O(log n) | O(log n) | O(log n) | ordered; range queries, floor/ceil |
| Heap (binary) | peek O(1) | O(n) | O(log n) | pop O(log n) | min/max, top-k, streaming median |
| Linked list | O(n) | O(n) | O(1) at node | O(1) at node | O(1) splice if you hold the node |
| Stack / Queue | — | — | O(1) | O(1) | deque is both ends O(1) |
| Trie | — | O(L) | O(L) | O(L) | prefix search; L = key length |
| Структура | Доступ | Поиск | Вставка | Удаление | Заметки |
|---|---|---|---|---|---|
| Динамический массив | O(1) | O(n) | O(1)*аморт | O(n) | append амортизированно O(1); вставка в середину O(n) |
| Hashmap / set | — | O(1) среднее | O(1) среднее | O(1) среднее | O(n) худший случай; неупорядочены |
| Сбалансированное BST / TreeMap | — | O(log n) | O(log n) | O(log n) | упорядочено; range-запросы, floor/ceil |
| Heap (бинарная) | peek O(1) | O(n) | O(log n) | pop O(log n) | min/max, top-k, streaming median |
| Связный список | O(n) | O(n) | O(1) у узла | O(1) у узла | O(1) splice, если держишь узел |
| Stack / Queue | — | — | O(1) | O(1) | deque — с обоих концов O(1) |
| Trie | — | O(L) | O(L) | O(L) | поиск префикса; L = длина ключа |
Heap mental modelМентальная модель heap
heapq is a min-heap only. For a max-heap, push -x. For top-k largest, keep a min-heap of size k and heappushpop.heapq — это только min-heap. Для max-heap засовывай -x. Для top-k наибольших держи min-heap размера k и используй heappushpop.Union-Find (Disjoint Set) — for connectivityUnion-Find (Disjoint Set) — для связности
def find(p, x): while p[x] != x: p[x] = p[p[x]] # path compression x = p[x] return x
Near-O(1) per op with path compression + union by rank. Reach for it on "number of islands as a stream", "accounts merge", "redundant connection".
Почти O(1) на операцию с path compression + union by rank. Используй для «число островов в потоке», «слияние аккаунтов», «избыточное ребро».
⚡ 10 Representative Problems10 типичных задач
Click to expand. Each = signal → approach → complexity → gotcha. These cover every pattern a coding screen pulls from.
Кликни, чтобы развернуть. Каждая = сигнал → подход → сложность → подводный камень. Покрывают все паттерны, которые встречаются на экране.
Ask: indices of two numbers summing to target.
Задача: индексы двух чисел с суммой = target.
Approach: one pass, hashmap of value → index. For each x, check if target - x seen.
Подход: один проход, hashmap значение → индекс. Для каждого x проверяй, видели ли target - x.
Complexity: O(n) time, O(n) space. Beats sort + two-pointer O(n log n) when you must return original indices.
Сложность: O(n) время, O(n) память. Выигрывает у sort + two-pointer O(n log n), когда нужно вернуть исходные индексы.
Signal: "longest substring with constraint" → variable sliding window.
Сигнал: «самая длинная подстрока с ограничением» → переменное скользящее окно.
Approach: window + last-seen-index map. When char repeats inside window, jump left = max(left, last[c]+1).
Подход: окно + карта «последний-встреченный-индекс». Когда символ повторяется в окне, прыгай left = max(left, last[c]+1).
Complexity: O(n) time, O(min(n, charset)) space.
Сложность: O(n) время, O(min(n, charset)) память.
Approach: sort by start; iterate; if cur.start <= last.end merge (last.end = max(...)), else push.
Подход: сортируй по началу; итерируй; если cur.start <= last.end мёржь (last.end = max(...)), иначе добавь.
Complexity: O(n log n) dominated by sort, O(n) output.
Сложность: O(n log n) определяется сортировкой, O(n) выход.
Cousins: Insert Interval, Meeting Rooms II (min rooms = max concurrent → min-heap of end times, or sweep line).
Родственные задачи: Insert Interval, Meeting Rooms II (мин комнат = макс одновременных → min-heap времён окончания, или sweep line).
Approach A: count freq (hashmap), then min-heap of size k → O(n log k).
Подход А: считай частоту (hashmap), затем min-heap размера k → O(n log k).
Approach B (better): bucket sort by frequency (index = count) → O(n).
Подход Б (лучше): bucket sort по частоте (индекс = счётчик) → O(n).
Approach: grid = implicit graph. Scan cells; on unvisited '1', flood-fill (DFS/BFS) marking visited, increment count.
Подход: сетка = неявный граф. Сканируй клетки; на непосещённой '1' flood-fill (DFS/BFS), отмечая посещённые, увеличь счётчик.
Complexity: O(rows × cols) time & space.
Сложность: O(строк × столбцов) время и память.
Signal: "can you finish given prerequisites" = detect cycle in directed graph / produce topo order.
Сигнал: «можно ли закончить при заданных prerequisite» = обнаружить цикл в направленном графе / построить topo-порядок.
Approach: Kahn's algorithm — compute in-degrees, queue of zero-indegree nodes, peel them off. If processed count < n → cycle.
Подход: алгоритм Кана — считай входящие степени, очередь узлов с нулевой степенью, снимай их. Если обработано < n → цикл.
Complexity: O(V+E).
Сложность: O(V+E).
Maps directly to DAG-based pipeline scheduling (Airflow/Dataswarm/Chronos): a cycle = an impossible dependency graph.
Прямо соответствует DAG-планированию пайплайнов (Airflow/Dataswarm/Chronos): цикл = невозможный граф зависимостей.
Approach: BFS with a queue; per level, snapshot len(queue) and process exactly that many.
Подход: BFS с очередью; на каждом уровне запомни len(queue) и обработай ровно столько.
Complexity: O(n) time, O(width) space.
Сложность: O(n) время, O(ширина) память.
Variants: zigzag (reverse alternate levels), right-side view (last node per level), max depth.
Варианты: zigzag (переворачивай чередующиеся уровни), right-side view (последний узел на уровне), max depth.
Approach: recurse; if node is p or q return node; recurse left & right; if both non-null → current is LCA; else bubble up the non-null one.
Подход: рекурсия; если узел — p или q, верни узел; рекурси left и right; если оба не-null → текущий узел — LCA; иначе всплывает не-null.
Complexity: O(n) time, O(h) stack.
Сложность: O(n) время, O(h) стек.
Approach: min-heap of the current head of each list; pop smallest, push its next.
Подход: min-heap текущих голов всех списков; pop наименьший, добавь его next.
Complexity: O(N log k) where N = total nodes, k = lists. Beats naive O(Nk).
Сложность: O(N log k), где N = всего узлов, k = списков. Выигрывает у наивного O(Nk).
Approach A: min-heap of size k → O(n log k), easy, streaming-friendly.
Подход А: min-heap размера k → O(n log k), просто, поддерживает streaming.
Approach B: Quickselect (partition like quicksort, recurse one side) → O(n) average, O(n²) worst.
Подход Б: Quickselect (partition как в quicksort, рекурси одну сторону) → O(n) в среднем, O(n²) худший случай.
🃏 Flip-to-Reveal Self-QuizСамопроверка с переворотом
Tap a card to flip. Drill these until the answer is instant.
Кликни карточку, чтобы перевернуть. Повторяй, пока ответ не станет мгновенным.
if). Variable: shrink with a while until the window is valid again.if). Переменное: сжимай с помощью while, пока окно не станет валидным.🐍 Code in Python · Reason in Scala / JavaКод на Python · Рассуждения на Scala / Java▾
Many DE roles require Java or Scala. You'll likely code in Python (fastest for you) but they may ask you to reason in Scala/Java idioms. Be fluent in the mapping.
Многие DE-роли требуют Java или Scala. Ты, скорее всего, кодишь на Python (для тебя быстрее), но могут попросить рассуждать на идиомах Scala/Java. Будь бегл в маппинге.
| Concept | Python | Scala | Java |
|---|---|---|---|
| Hashmap | dict / defaultdict | mutable.Map / Map | HashMap |
| Set | set | mutable.Set | HashSet |
| Min-heap | heapq | mutable.PriorityQueue (max by default; reverse Ordering) | PriorityQueue |
| Queue/Deque | collections.deque | mutable.Queue / ArrayDeque | ArrayDeque |
| Ordered map | —(use sortedcontainers) | TreeMap / SortedMap | TreeMap |
| Counter | collections.Counter | groupBy(identity).mapValues(_.size) | manual merge(k,1,Integer::sum) |
| Концепция | Python | Scala | Java |
|---|---|---|---|
| Hashmap | dict / defaultdict | mutable.Map / Map | HashMap |
| Set | set | mutable.Set | HashSet |
| Min-heap | heapq | mutable.PriorityQueue (макс по умолчанию; reverse Ordering) | PriorityQueue |
| Queue/Deque | collections.deque | mutable.Queue / ArrayDeque | ArrayDeque |
| Ordered map | —(используй sortedcontainers) | TreeMap / SortedMap | TreeMap |
| Counter | collections.Counter | groupBy(identity).mapValues(_.size) | вручную merge(k,1,Integer::sum) |
HashMap treeify-on-collision; the JVM boxing cost of Integer vs int in hot loops.HashMap treeify-on-collision; цена boxing JVM — Integer vs int в горячих циклах.Scala idiom worth saying out loudИдиома Scala, которую стоит произнести вслух
// pattern matching makes tree recursion clean & total def sum(t: Tree): Int = t match { case Leaf(v) => v case Node(l, _, r) => sum(l) + sum(r) }
✅ In-Interview Checklist (UMPIRE)Чеклист на интервью (UMPIRE)
- U — Understand: restate the problem; ask about input size, types, nulls, duplicates, sorted?, empty, negatives, Unicode, in-place allowed?
- M — Match: name the pattern out loud ("this looks like a sliding-window / hashmap problem").
- P — Plan: describe the approach & state complexity before coding. Mention the brute force, then the optimization.
- I — Implement: write clean code, talk through it, meaningful names, no premature golfing.
- R — Review: dry-run a small example AND an edge case (empty, single element, all same).
- E — Evaluate: restate final time/space; discuss trade-offs, scaling to billions, how you'd test it.
- U — Understand (Понимание): переформулируй задачу; спроси про размер входа, типы, null, дубли, отсортирован?, пуст, отрицательные, Unicode, можно ли in-place?
- M — Match (Сопоставление): назови паттерн вслух («это похоже на sliding-window / hashmap-задачу»).
- P — Plan (План): опиши подход & сформулируй сложность до кода. Упомяни brute force, затем оптимизацию.
- I — Implement (Реализация): пиши чистый код, говори, что делаешь, осмысленные имена, не гольфь преждевременно.
- R — Review (Проверка): прогони вручную маленький пример И граничный случай (пусто, один элемент, все одинаковые).
- E — Evaluate (Оценка): переформулируй финальное время/память; обсуди компромиссы, масштабирование на миллиарды, как бы ты тестировал.
long); mutating while iterating; forgetting the visited set in graph traversal.long); мутируешь во время итерации; забыл visited set в обходе графа.