# Экзаменация — сквозной прогресс

Таблица всех 32 задач. Баллы по раундам (0–3, `—` — не отвечен). Колонка **Лучший** — максимум по раундам, **Вердикт** — по последнему раунду.

Легенда: 🟢 passed (3) · 🟡 partial (2) · 🔴 failed (0–1) · ⚪ not_attempted · ⬜ не пройдено.

## Must Have (19)

| № | Задача | Тема | Слож. | R1 | R2 | R3 | R4 | R5 | Лучший | Вердикт |
|---|--------|------|-------|----|----|----|----|----|--------|---------|
| 1 | Container With Most Water | Two Pointers | Medium | 2 | | | | | 2 | 🟡 |
| 2 | Partition Labels | Two Pointers | Medium | 2 | | | | | 2 | 🟡 |
| 3 | Squares of a Sorted Array | Two Pointers | Easy | 2 | | | | | 2 | 🟡 |
| 4 | Summary Ranges | Two Pointers | Easy | 2 | | | | | 2 | 🟡 |
| 5 | Find All Anagrams in a String | Hash Table | Medium | 2 | | | | | 2 | 🟡 |
| 6 | Permutation in String | Hash Table | Medium | 2 | | | | | 2 | 🟡 |
| 7 | Single Number | Hash Table | Easy | 2 | | | | | 2 | 🟡 |
| 8 | Two Sum | Hash Table | Easy | 1 | 2 | | | | 2 | 🟡 |
| 9 | Group Anagrams | Hash Table | Medium | 2 | | | | | 2 | 🟡 |
| 10 | Valid Anagram | Hash Table | Easy | 2 | | | | | 2 | 🟡 |
| 11 | Subarray Sum Equals K | Hash Table | Medium | 1 | 2 | | | | 2 | 🟡 |
| 12 | Merge Intervals | Sort | Medium | 2 | | | | | 2 | 🟡 |
| 13 | Valid Parentheses | Queue / Stack | Easy | 2 | | | | | 2 | 🟡 |
| 14 | Sliding Window Median | Sliding Window | Hard | 2 | | | | | 2 | 🟡 |
| 15 | Sliding Window Maximum | Sliding Window | Hard | 2 | | | | | 2 | 🟡 |
| 16 | Peeking Iterator | Iterator | Medium | 2 | | | | | 2 | 🟡 |
| 17 | Best Time to Buy and Sell Stock | Greedy | Easy | 1 | 2 | | | | 2 | 🟡 |
| 18 | Best Time to Buy and Sell Stock II | Greedy | Medium | 2 | | | | | 2 | 🟡 |
| 19 | Best Time with Transaction Fee | Greedy | Medium | 2 | | | | | 2 | 🟡 |

## Дополнительная тренировка (13)

| № | Задача | Тема | Слож. | R1 | R2 | R3 | R4 | R5 | Лучший | Вердикт |
|---|--------|------|-------|----|----|----|----|----|--------|---------|
| 20 | Merge k Sorted Lists | Linked Lists | Hard | 1 | 2 | | | | 2 | 🟡 |
| 21 | Reverse Linked List | Linked Lists | Easy | 2 | | | | | 2 | 🟡 |
| 22 | Number of Islands | DFS / BFS | Medium | 2 | | | | | 2 | 🟡 |
| 23 | Remove Invalid Parentheses | DFS / BFS | Hard | 2 | | | | | 2 | 🟡 |
| 24 | Top K Frequent Words | Heap / Hash | Medium | 2 | | | | | 2 | 🟡 |
| 25 | Binary Search | Binary Search | Easy | 2 | | | | | 2 | 🟡 |
| 26 | Same Tree | Tree | Easy | 2 | | | | | 2 | 🟡 |
| 27 | Symmetric Tree | Tree | Easy | 2 | | | | | 2 | 🟡 |
| 28 | Subtree of Another Tree | Tree | Easy | 2 | | | | | 2 | 🟡 |
| 29 | Find Duplicate Subtrees | Tree | Medium | 2 | | | | | 2 | 🟡 |
| 30 | Add Binary | Math / String | Easy | 2 | | | | | 2 | 🟡 |
| 31 | Add Strings | Math / String | Easy | 2 | | | | | 2 | 🟡 |
| 32 | Multiply Strings | Math / String | Medium | 2 | | | | | 2 | 🟡 |

## Разбивка по темам

| Тема | Задач | 🟢 | 🟡 | 🔴 | Средний балл |
|------|-------|----|----|----|--------------|
| Two Pointers | 4 | 0 | 4 | 0 | 2.00 |
| Hash Table | 7 | 0 | 7 | 0 | 2.00 |
| Sort | 1 | 0 | 1 | 0 | 2.00 |
| Queue / Stack | 1 | 0 | 1 | 0 | 2.00 |
| Sliding Window | 2 | 0 | 2 | 0 | 2.00 |
| Iterator | 1 | 0 | 1 | 0 | 2.00 |
| Greedy | 3 | 0 | 3 | 0 | 2.00 |
| Linked Lists | 2 | 0 | 2 | 0 | 2.00 |
| DFS / BFS | 2 | 0 | 2 | 0 | 2.00 |
| Heap / Hash | 1 | 0 | 1 | 0 | 2.00 |
| Binary Search | 1 | 0 | 1 | 0 | 2.00 |
| Tree | 4 | 0 | 4 | 0 | 2.00 |
| Math / String | 3 | 0 | 3 | 0 | 2.00 |
| **Итого** | **32** | **0** | **32** | **0** | **2.00** |

## Слабые места

1. **Сложность и граничные случаи.** Единственный оставшийся системный пробел: ни в одном из ответов не названы одновременно время/память и edge cases. Идеи теперь верные во всех 32 задачах (после раунда 2), но формат «идея + структура + сложность + edge cases» не доводится до конца.
2. **Формат полного ответа.** Чтобы получить 3, нужно после идеи проговаривать: «время O(…), память O(…), граничные случаи: …». Сейчас это не делается ни в одной задаче — интервьюер будет тянуть эти детали вопросами.
3. **Hash Table.** Идеи исправлены (#8 проверка до вставки, #11 префиксы + счётчик), но сложность O(n)/O(n) и edge cases не называются.
4. **Linked Lists / Hard-приёмы.** #20 идея верна (heap + попарное слияние), но сложность O(N log k) не названа; #15 Sliding Window Maximum — всё ещё через кучу вместо монотонной deque.
5. **Follow-up'ы.** Unicode в Valid Anagram, O(1)-память в Single Number, улучшения в Subtree/Duplicate Subtrees — не отработаны.

## Комплексная оценка готовности

**По идеям:** 32/32 верных подходов после раунда 2 — все четыре провала раунда 1 закрыты (Two Sum, Subarray Sum Equals K, Merge k Sorted Lists, Best Time I). Обе Hard по структуре, деревья, строки — идеи стабильно верные.

**По полноте ответа:** пока нет. Формат ответа на интервью должен быть «идея + структура данных + сложность + граничные случаи + краткая проверка на примере»; сейчас стабильно проговаривается только первая половина. Это единственный оставшийся разрыв до оценки 3.

**Главные риски перед этапом 1:** (1) не называть сложность и edge cases — единственный системный пробел, из-за которого все ответы сейчас на 2; (2) Hard-приёмы, не доведённые до канона (deque вместо кучи в Sliding Window Maximum); (3) отсутствие привычки отвечать на follow-up.

**План:** раунд 3 — задачи с лучшим баллом < 3 (все 32), приоритет: сначала 4 задачи раунда 2 (8, 11, 17, 20) с обязательным проговариванием «время/память + 2–3 edge cases», затем Приоритет 2 и 3 из `round-02-2026-09-12/_round.md`. Формат ответа на тренировке: идея → структура → сложность → edge cases → проверка на примере.

## Журнал раундов

| Раунд | Дата | Билетов предъявлено | Сумма | Средний | Статус | Комментарий |
|-------|------|---------------------|-------|---------|--------|-------------|
| 1 | 2026-09-12 | 32/32 | 60 | 1.88 | completed | первый полный прогон: 28 частичных, 4 провала, ни одного полного ответа |
| 2 | 2026-09-12 | 4/4 | 8 | 2.00 | completed | рексэкзамен 4 провалов: идеи исправлены во всех 4, сложность и edge cases снова не названы |

## Наблюдения с тренировки по сложности (время + память), 2026-09-14

Интерактивная тренировка: 32 сниппета по времени (задачи 1–32) и 9 сниппетов по памяти (M1–M9), взятые из собственных разборов.

### Сильные стороны

- Уверенно вычисляет O(n) для линейных проходов, двух указателей, скользящего окна с фиксированным алфавитом.
- Хорошо понимает хеш-структуры: O(n) по времени, O(1) для массивов на 26 ячеек.
- Верно оценивает обход деревьев/сеток: O(n) по дереву, O(R·C) DFS/BFS по времени.
- После разбора быстро удерживает уроки; понимает монотонный стек/очередь и амортизацию.
- Готов работать в параметрической нотации (n, k, m) после подсказки.

### Повторяющиеся ловушки

**Время:**

- Свертка параметров: стремится выбросить лишний параметр (Group Anagrams: O(n log n) вместо O(n·k log k)).
- Геометрические vs арифметические суммы: сложности с удвоением данных на итерации (subsets, Remove Invalid Parentheses) сначала оцениваются как O(n) или O(n²).
- Рекуррентности: fib изначально O(n²); перебор подмножеств — не сразу 2ⁿ.
- Стоимость операций: `include?` vs `bsearch`, `sort + linear` — путается, если отсортированность не ускоряет операцию.
- Число итераций vs работа на итерацию: путает суммарное число push'ей с живым размером структуры.

**Память:**

- Первоначально считал вход и выход в дополнительную память; после фиксации конвенции считает только auxiliary.
- Глубина рекурсии vs общее число вызовов: Same Tree изначально O(2ⁿ) из-за смешения времени и памяти.
- Живой размер vs оборот структуры: Sliding Window Maximum deque изначально O(n) (считались общие добавления, а не живые элементы).
- Длина ключей в хеше: Group Anagrams изначально O(n), не учитывалась длина ключей → O(n·k).
- Экспонента в памяти: Remove Invalid Parentheses изначально n·n!, путались подмножества и перестановки.

### Что тренировать дальше

- Память: sort stack (Merge Intervals), рекурсивный/итеративный бинарный поиск, BFS по сетке с очередью, Merge k Sorted Lists (divide-and-conquer vs heap).
- Формат полного ответа: идея + структура + время + память + edge cases в одном билете.