eduplan-cpp-eltex/lessons/D7_mock.md

# D7 (30.09). Повтор и мок-интервью

Последний день — не новая тема, а тренировка в формате реального собеседования: 3 часа
алгоритмов вслух с таймером и 2 часа системных вопросов "объясни механизм за 30 секунд".
Ниже — карта, куда смотреть по слабым местам, и два мок-сценария с эталонными ответами.

## 1. Карта слабых мест

| Домен | Что спрашивают | Куда смотреть |
|---|---|---|
| O-нотация, хеш-таблица | сложности операций, устройство хеш-таблицы, коллизии, rehash | `D1_algo` §1–5 |
| fork/exec/wait/сигналы/errno | зомби, коды 137/139, `sigaction`, `EINTR`/`EAGAIN` | `D1_linux` |
| Деревья, BST, куча, top-K | обходы, инвариант BST, `sift-up`/`sift-down`, `nth_element` | `D2_algo` §1–6 |
| open/mmap/epoll/select/TIME_WAIT | буферизация, page fault, `FD_SETSIZE`, ET vs LT | `D2_linux` §1–7 |
| padding, правило 0/3/5, virtual-деструктор, move, UB | `sizeof`/`offsetof`, double-free, vtable, ASAN/UBSAN | `D2_cpp` §1–5 |
| Списки, стек/очередь, кольцевой буфер | разворот, цикл Флойда, dummy-узел, монотонный стек | `D3_algo` |
| Потоки, mutex, CV, deadlock, atomic | data race, 4 условия deadlock, `memory_order`, TSan | `D3_threads` |
| gdb, core dump, valgrind | точки останова, `bt`, ASAN vs gdb, `ulimit -c` | `D3_gdb` |
| Графы: BFS/DFS, топосортировка, Дейкстра, DSU | сложности `O(V+E)`, `O((V+E) log V)`, ранг+сжатие пути | `D4_algo` |
| Ethernet/ARP/VLAN/MTU/IPv4/TTL/ICMP/CIDR | заголовки по байтам, checksum, /24 vs /26 | `D4_net` |
| ДП: рюкзак, монеты, LCS, Edit Distance, LIS | таблица `(n+1)×(m+1)`, обратный проход по весу, `O(n log n)` LIS | `D5_algo` |
| TCP: заголовок, handshake, состояния, TIME_WAIT, UDP, NAT, DNS, DHCP | 20/8 байт заголовков, `2×MSL`, `tcpdump` | `D5_net` |
| bash: pipefail, xargs, awk/sed, `/proc`, ulimit, strace | коды возврата, `set -euo pipefail`, дескрипторы | `D5_bash` |
| Ядро обзорно: syscall, модуль, `/proc`/`/sys`, chardev, ioctl, device tree | user space vs kernel space, `copy_to_user` | `D6_kernel` |

Механизмы уровня "откуда это следует" (ООП, STL, Git/Docker/GDB детальнее) — в
`HR_BASE_deep.md`, если конкретный урок дня даёт ответ слишком коротко.

**Факты для карточек**
- base | Сколько уроков покрывает план перед D7? — 13 файлов (`D1_algo`…`D6_docker`) по алгоритмам, Linux, C++, сетям, потокам, отладке, bash и ядру
- core | Где искать формулировки механизмов, если в уроке дня их не хватает? — `HR_BASE_deep.md`
- base | Сколько часов длится каждый мок сегодня? — мок №1 (алгоритмы) 3 часа, мок №2 (системное) 2 часа

Почему дальше: карта показывает, где искать теорию; дальше — тренировка в формате реального
таймера, начиная с алгоритмов.

## 2. Мок №1. Алгоритмы (3 часа, 6 задач × 25 минут)

Формат: 25 минут на задачу — сначала вслух проговорить план и уточняющие вопросы (первые
3–5 минут), потом решение. На реальном скрининге читаемый план ценится не меньше кода: если
план верный, а код не дописан за 25 минут, это всё ещё сильный ответ. Ниже — не готовый код,
а эталонная последовательность шагов для каждой задачи; сам код — в соответствующем уроке дня.

### Задача 1. Хеш-таблица с нуля (`tasks/10_hash`, теория — `D1_algo` §3, §5)

**Что проверяет интервьюер:** понимание механизма, а не вызов готового `std::unordered_map` —
обоснование выбора разрешения коллизий и сложности, а не память формул.

**Критерии сильного ответа:** называет компоненты (массив корзин, хеш-функция, коллизии,
load factor) без подсказки; сразу разделяет среднюю сложность `O(1)` и худший случай `O(n)`;
осознанно выбирает chaining или open addressing и объясняет цену выбора; упоминает rehash при
превышении порога загрузки.

**Ловушки**
- Путают среднюю и худшую сложность операций → на вопрос "а что если все ключи попали в одну корзину" отвечают "всё равно O(1)" → сразу видно, что структура не понята, а заучена.
- При open addressing не знают про удаление через tombstone → предлагают просто очищать ячейку → следующий поиск обрывается раньше времени, не находя элемент дальше по цепочке зондирования.
- Не проговаривают степень двойки для capacity → используют деление по модулю вместо `hash & (cap - 1)`, не объясняя, зачем вообще нужна степень двойки.

**Эталонный план по шагам:**
1. Уточнить тип ключей (строки/числа), нужен ли `erase`, ожидаемый порядок `N`.
2. Взять `capacity` степенью двойки, задать порог load factor (например, 0.7).
3. Выбрать хеш-функцию: для строк — FNV-1a или `std::hash<std::string>`.
4. Выбрать разрешение коллизий: chaining — проще и безопаснее уложить в 25 минут.
5. `insert`: посчитать `idx = hash & (cap - 1)`, добавить в корзину; если load factor превышен — rehash в массив вдвое больше, перенести все элементы.
6. `get`/`erase`: пройти цепочку по индексу; для open addressing `erase` — пометить tombstone, не очищать ячейку.
7. Проговорить итоговые сложности и триггер rehash.

**Сложность:** амортизированно `O(1)` на вставку/поиск/удаление; худший случай (плохой хеш,
все ключи в одной корзине) — `O(n)`; сам rehash — `O(n)`, но происходит редко, поэтому не
портит амортизированную оценку.

**Уточняющие вопросы кандидата:** нужна ли потокобезопасность? Ключи известны заранее (тогда
возможен perfect hashing)? Важен ли порядок вставки при обходе?

**Факты для карточек**
- base | Средняя сложность операций хеш-таблицы? — амортизированное O(1)
- core | При каком load factor обычно триггерят rehash при open addressing? — около 0.7
- core | Зачем capacity берут степенью двойки? — `idx = hash & (cap - 1)` вместо дорогого деления по модулю
- deep | Каков стандартный max_load_factor по умолчанию у `std::unordered_map` в большинстве реализаций (libstdc++, MSVC)? — 1.0

Почему дальше: хеш-таблица даёт O(1) доступ по ключу без порядка; следующая задача — структура
с O(1) доступом к экстремуму и осмысленным порядком по величине.

### Задача 2. Куча / top-K (`tasks/11_heap`, теория — `D2_algo` §5–6)

**Что проверяет интервьюер:** различие между построением кучи и потоковым top-K; выбор между
полной кучей, min-heap размера k и `nth_element` по контексту задачи.

**Критерии сильного ответа:** первым делом спрашивает про размер данных (влезают ли в
память); знает сложности всех трёх подходов; не путает направление кучи для потокового
top-K (для top-K наибольших нужен именно min-heap размера k).

**Ловушки**
- Строят кучу через `push` в цикле вместо bottom-up `heapify` → результат корректный, но `O(n log n)` вместо `O(n)` → на миллионах элементов заметно медленнее, видно по времени выполнения.
- В потоковом top-K сравнивают новый элемент с максимумом кучи, а не с минимумом → кандидаты вытесняются в обратном порядке → итоговый top-K оказывается неверным набором.
- Используют `nth_element` там, где нужен отсортированный результат, и забывают досортировать k-элементный префикс → набор элементов верный, порядок — нет.

**Эталонный план по шагам:**
1. Уточнить `k`, `N`, влезают ли данные в память целиком, нужен ли отсортированный результат.
2. Если данные помещаются в память — `heapify` за `O(n)`, затем `k` раз `pop` по `O(log n)`.
3. Если поток / не влезает — держать min-heap размера `k`: сравнивать новый элемент с `top()` кучи (O(1)); если новый больше минимума — вытеснить минимум, добавить новый.
4. Альтернатива без построения кучи — `nth_element` (quickselect), в среднем `O(n)`, но без готового порядка внутри половин.
5. Если нужен отсортированный top-K через `nth_element` — досортировать k-элементный префикс отдельно.
6. Проговорить, почему выбран именно этот вариант.

**Сложность:** полная куча — `O(n + k log n)` время, `O(n)` память; потоковый min-heap —
`O(n log k)` время, `O(k)` память; `nth_element` — среднее `O(n)`, худшее `O(n²)`.

**Уточняющие вопросы кандидата:** данные статичны или стримятся? Нужен ли устойчивый порядок
при равных ключах? Есть ли жёсткое ограничение по памяти?

**Факты для карточек**
- base | Сложность top-K через полную кучу? — O(n + k log n)
- core | Какую кучу держат для потокового top-K наибольших элементов размера k? — min-heap размера k
- core | Средняя и худшая сложность nth_element? — среднее O(n), худшее O(n²)
- deep | Как получить top-K частых элементов за O(n) без log-множителя? — подсчёт хеш-таблицей O(n) + bucket sort по частоте (массив корзин размера n+1)

Почему дальше: куча и top-K работают со случайным доступом по значению; следующая задача —
структура, где доступ строго последовательный через указатели, и там есть собственный класс
ошибок — циклы.

### Задача 3. Связный список с циклом (`tasks/02_list`, теория — `D3_algo` §5)

**Что проверяет интервьюер:** понимание, почему указатели вообще встречаются (а не просто
память алгоритма Флойда), корректная обработка граничных случаев.

**Критерии сильного ответа:** объясняет механизм через относительную скорость (`fast`
догоняет `slow` на 1 узел за шаг внутри цикла), а не просто произносит "медленный и быстрый
указатель"; корректно достраивает поиск входа в цикл вторым проходом.

**Ловушки**
- Сравнивают значения узлов вместо указателей → на списке с повторяющимися значениями без реального цикла даёт ложное срабатывание.
- Забывают проверку `fast && fast->next` перед `fast->next->next` → падение на `nullptr` для списка без цикла чётной/нечётной длины на границе.
- Не могут объяснить вторую часть (поиск входа в цикл) без домашней заготовки → интервьюер спрашивает "почему это работает", а не "какой код писать".

**Эталонный план по шагам:**
1. Уточнить: список одно- или двусвязный, возможны ли пустой список и self-loop (узел ссылается сам на себя).
2. `slow = head`, `fast = head`.
3. Пока `fast && fast->next`: `slow` на 1 шаг, `fast` на 2 шага; если `slow == fast` — цикл найден, выйти из цикла проверки.
4. Если `fast` дошёл до `nullptr` — цикла нет.
5. Для входа в цикл: сбросить один указатель на `head`, второй оставить в точке встречи; двигать оба по 1 шагу — встретятся ровно на входе в цикл.
6. Кратко обосновать почему (из `2(a+b) = a+b+n·c` следует `a = (n-1)c + (c-b)`).

**Сложность:** время `O(n)`, память `O(1)` — без хеш-множества посещённых узлов.

**Уточняющие вопросы кандидата:** нужна ли длина цикла отдельно от факта его наличия? Список
гарантированно не пуст?

**Факты для карточек**
- base | Сложность обнаружения цикла алгоритмом Флойда по времени и памяти? — O(n) время, O(1) память
- core | С какой относительной скоростью fast догоняет slow внутри цикла? — 1 узел за шаг
- core | Как найти вход в цикл после первой встречи указателей? — сбросить один указатель на head, оба двигать по 1 шагу — встретятся на входе

Почему дальше: список — структура с одним "соседом" на узел; граф — структура с произвольным
числом соседей, и обход там даёт другие гарантии в зависимости от порядка обхода.

### Задача 4. BFS по матрице/графу (теория — `D4_algo` §2)

**Что проверяет интервьюер:** умение свести сетку к неявному графу соседей, правильный момент
пометки `visited`, вывод сложности через размеры входа.

**Критерии сильного ответа:** явно проговаривает, что кратчайший путь по рёбрам гарантирован
именно порядком FIFO очереди, а не самим фактом использования BFS "потому что так учили";
помечает узел посещённым в момент постановки в очередь, а не при извлечении.

**Ловушки**
- Помечают `visited` при извлечении из очереди, а не при добавлении → один и тот же узел кладётся в очередь несколько раз → деградация по времени, иногда неверный `dist`.
- Не проверяют границы сетки перед обращением к соседней клетке → выход за границы массива.
- Считают диагональных соседей, хотя задача просила 4-связность (или наоборот) → неверный граф с самого начала, весь дальнейший разбор бессмыслен.

**Эталонный план по шагам:**
1. Уточнить: сетка или произвольный граф; 4 или 8 соседей; есть ли препятствия или веса рёбер.
2. Представление: список смежности для явного графа; прямой обход соседних клеток для сетки.
3. `dist[] = -1` (или `visited[][] = false`), очередь, `dist[src] = 0`, `push(src)`.
4. Пока очередь не пуста: `pop u`; для каждого непосещённого соседа `v` — `dist[v] = dist[u] + 1`, `push(v)`, пометить как посещённый сразу здесь.
5. Ответ — `dist[target]` (или число посещённых клеток для задач на компоненты/острова).

**Сложность:** `O(V+E)` для графа; для сетки `R×C` — `O(R·C)`, так как `V = R·C`, а `E`
пропорционально `V` при фиксированном числе соседей на клетку (4 или 8).

**Уточняющие вопросы кандидата:** веса рёбер одинаковы? Граф ориентированный? Нужен сам путь
или только его длина?

**Факты для карточек**
- base | Сложность BFS на сетке R×C? — O(R·C)
- core | Почему BFS гарантирует кратчайший путь по числу рёбер? — FIFO-очередь раскрывает граф строго по слоям расстояния
- core | В какой момент нужно помечать узел посещённым, чтобы избежать повторных вставок в очередь? — в момент постановки в очередь, а не при извлечении
- deep | Как обойти граф со весами рёбер только 0 и 1 за O(V+E) без полноценной Дейкстры? — 0-1 BFS: deque, вес 0 — push_front, вес 1 — push_back

Почему дальше: BFS решает граф с одинаковой "ценой" каждого ребра; следующая задача — с
одномерным массивом, где решение каждого следующего элемента зависит от предыдущих
подрешений, а не от соседей в структуре — это динамическое программирование.

### Задача 5. ДП на строки: LCS / Edit Distance (теория — `D5_algo` §6)

**Что проверяет интервьюер:** умение построить таблицу `(n+1)×(m+1)`, объяснить переходы
словами, а не просто написать формулу по памяти.

**Критерии сильного ответа:** явно объясняет базовый случай (пустая строка/префикс) и почему
размер таблицы `(n+1)×(m+1)`, а не `n×m`; для Edit Distance проговаривает все три операции
(замена/удаление/вставка) и почему берётся минимум трёх соседних ячеек.

**Ловушки**
- Заводят таблицу `n×m` вместо `(n+1)×(m+1)` → нет места под базовый случай "один из префиксов пуст" → неверные значения на границе или выход за границы массива.
- В Edit Distance забывают инициализировать нулевую строку/столбец → сравнение с мусорными значениями → неверный ответ без падения программы (тихая ошибка).
- Путают направление переходов LCS (берут `min` вместо `max` при несовпадении символов) → результат заведомо меньше правильного.

**Эталонный план по шагам:**
1. Уточнить: нужна длина LCS, сама подпоследовательность (восстановление пути) или Edit Distance.
2. Завести таблицу `dp[(n+1)][(m+1)]`; строка/столбец 0 — базовый случай "один из префиксов пуст".
3. LCS: при совпадении символов — `dp[i-1][j-1] + 1`; иначе — `max(dp[i-1][j], dp[i][j-1])`.
4. Edit Distance: `dp[i][0] = i`, `dp[0][j] = j`; при совпадении — `dp[i-1][j-1]`; иначе — `1 + min(замена, удаление, вставка)`.
5. Ответ — `dp[n][m]`.
6. Если нужна экономия памяти и не нужно восстановление пути — держать только 2 строки таблицы.

**Сложность:** время и память `O(n·m)`; при экономии памяти (без восстановления пути) —
`O(min(n,m))` память.

**Уточняющие вопросы кандидата:** нужна ли сама подпоследовательность/путь операций, или
только число? Укладывается ли `n·m` в лимит по времени при заданных ограничениях на длину строк?

**Факты для карточек**
- base | Размер таблицы LCS/Edit Distance для строк длины n и m? — (n+1)×(m+1)
- base | Временная и пространственная сложность LCS/Edit Distance? — O(n·m) и по времени, и по памяти
- core | Три операции, между которыми выбирают минимум в Edit Distance? — замена, удаление, вставка

Почему дальше: LCS и Edit Distance решают задачу за O(n·m) явной таблицей; следующая
классическая задача решается той же схемой за O(n²), но улучшается до O(n log n) совсем
другим приёмом — это повод спросить про компромисс между простотой и асимптотикой.

### Задача 6. ДП/НВП — LIS (`tasks/05_lis`, теория — `D5_algo` §7)

**Что проверяет интервьюер:** знание наивного `O(n²)` и продвинутого `O(n log n)` подходов,
умение оценить ограничения по `N` и сразу выбрать нужный алгоритм.

**Критерии сильного ответа:** сразу считает, влезает ли наивный `O(n²)` в лимит времени при
данном `N` (например, на `N = 100 000` это `10¹⁰` операций — не укладывается в 2 секунды);
понимает, что массив `tails[]` — не сама LIS, а вспомогательная структура минимальных хвостов.

**Ловушки**
- Путают длину массива `tails[]` (результат) с самой LIS-последовательностью → на просьбу "выведите саму подпоследовательность" отвечают неверно, потому что `tails[]` не хранит реальный путь.
- Делают линейный поиск позиции вместо `lower_bound` в `tails[]` → теряют весь выигрыш от `O(n log n)`, получают снова `O(n²)`.
- Не уточняют строгое или нестрогое возрастание → готовое решение может не соответствовать формулировке задачи.

**Эталонный план по шагам:**
1. Уточнить `N` и лимит по времени/памяти, строгое или нестрогое возрастание.
2. Если `N` мало — наивный `O(n²)`: `dp[i]` — длина LIS, заканчивающейся на `a[i]`, перебор `j < i` с `a[j] < a[i]`.
3. Если `N` большое — массив `tails[]`: для каждого нового элемента бинарным поиском (`lower_bound`) найти позицию замены или расширения `tails`.
4. Ответ — текущая длина `tails[]`.
5. Проговорить: для восстановления самой подпоследовательности нужен отдельный массив индексов-предков, `tails[]` для этого не подходит.

**Сложность:** наивный подход — `O(n²)` время, `O(n)` память; продвинутый — `O(n log n)`
время, `O(n)` память.

**Уточняющие вопросы кандидата:** нужна ли сама подпоследовательность или только длина?
Строгое возрастание или нестрогое (допускаются равные соседние значения)?

**Факты для карточек**
- base | Сложность наивного LIS и продвинутого через tails[]? — O(n²) и O(n log n) соответственно
- core | Почему наивный O(n²) не проходит на N=100 000 за 2 секунды? — 10¹⁰ операций, не укладывается в типичный лимит времени внутреннего теста
- core | Что хранит tails[k]? — минимальный возможный последний элемент возрастающей подпоследовательности длины k+1
- deep | Как называется классический приём построения tails[] с заменой через бинарный поиск? — patience sorting (раскладка карт по кучкам)

Почему дальше: алгоритмическая часть проверяет чистые структуры данных с однозначным
эталонным ответом; системная часть мока проверяет то же самое качество понимания, но в формате
устного объяснения без кода — и там интервьюер чаще всего задаёт один и тот же вопрос дважды,
разными словами, чтобы проверить глубину.

## 3. Мок №2. Системное (2 часа, 12 вопросов)

Формат: интервьюер задаёт короткий вопрос, ждёт ответ на 20–40 секунд, затем "углубляет" —
задаёт уточняющий вопрос, который проверяет, понята ли причина, а не просто выучен факт.
Ниже — по 4 вопроса на C/C++, Linux и сети.

### C/C++

**Вопрос 1. Посчитайте `sizeof(struct { char a; int b; char c; })` на x86-64 и объясните откуда взялось число.**

Чего ждёт интервьюер: конкретное число (12) и раскладку по смещениям, а не "наверное, 6".

Заготовка ответа (20–40 сек): "Поля дают 6 байт, но `sizeof` будет 12. `a` на смещении 0;
дальше 3 байта паддинга, потому что `int b` требует выравнивания на 4 байта; `b` занимает
смещения 4–7; `c` на смещении 8. Полезные данные кончаются на 9 байте, но размер всей
структуры округляется вверх до кратного выравниванию самого строгого поля — здесь `int`,
выравнивание 4 — отсюда ещё 3 байта хвостового паддинга и итог 12."

Углубление: "А если переставить поля — `char a; char c; int b`?" → 8 байт: два `char` подряд
без паддинга между ними, потом `int` с выравниванием 4, конец уже кратен 4 — экономия 4
байта на объект. "Что делает `#pragma pack(1)`?" → убирает паддинг (`sizeof` станет 6), но
доступ к невыровненным полям дороже на x86 и может аппаратно упасть на платформах со строгим
выравниванием.

**Факты для карточек**
- base | sizeof(struct { char a; int b; char c; }) на x86-64? — 12 байт
- core | sizeof той же структуры с полями в порядке char a; char c; int b? — 8 байт

**Вопрос 2. Что такое правило 0/3/5 и когда его нужно применять?**

Чего ждёт интервьюер: связь между "класс владеет ресурсом" и необходимостью явно писать
копирование/перемещение.

Заготовка ответа: "Если класс сам управляет ресурсом (владеющий указатель, файловый
дескриптор) и поэтому определяет деструктор, он почти наверняка должен явно определить и
конструктор/оператор копирования (правило трёх), а с C++11 — ещё и перемещения (правило
пяти). Если ни одну из пяти функций не объявить, компилятор сгенерирует все сам, и
сгенерированное копирование — побитовое: для владеющего указателя это значит, что обе копии
получат один и тот же адрес, и оба деструктора вызовут `delete` на нём — double-free."

Углубление: "А правило нуля?" → не писать ни одну из пяти вручную, доверив владение готовой
RAII-обёртке (`unique_ptr`, `vector`, `string`) — её сгенерированные копирование/перемещение
уже корректны.

**Факты для карточек**
- base | Какие 5 функций входят в правило пяти? — деструктор, конструктор копирования, оператор присваивания копированием, конструктор перемещения, оператор присваивания перемещением
- core | Что делает сгенерированный компилятором конструктор копирования по умолчанию? — побитовое (memberwise) копирование каждого поля

**Вопрос 3. Что физически делает `std::move`?**

Чего ждёт интервьюер: развенчание мифа "move перемещает данные во время выполнения".

Заготовка ответа: "Ничего во время выполнения — это `static_cast<T&&>(x)`, явный каст к
rvalue-ссылке. Единственный эффект — при выборе перегрузки компилятор теперь предпочитает
move-конструктор, а не копирующий. Реальную работу делает move-конструктор конкретного типа:
для `vector` это перенос трёх указателей (начало, конец данных, конец ёмкости) и обнуление их
у источника — O(1), без копирования элементов."

Углубление: "В каком состоянии объект после `std::move`?" → в валидном, но неопределённом
состоянии по стандарту; использование старых данных — не UB, но логическая ошибка, не ловится
санитайзерами.

**Факты для карточек**
- base | Что физически делает std::move во время выполнения? — ничего: это static_cast к rvalue-ссылке
- core | За какое время перемещается std::vector и что именно переносится? — O(1): три внутренних указателя (начало, конец данных, конец ёмкости)

**Вопрос 4. Назовите 2–3 примера UB в C++ и объясните разницу ASAN/UBSAN.**

Чего ждёт интервьюер: конкретные примеры (не общее "неопределённое поведение — это плохо") и
чёткое разделение зон ответственности двух санитайзеров.

Заготовка ответа: "Знаковое переполнение `int` (`INT_MAX + 1`), сдвиг на число бит больше или
равное разрядности типа (`1 << 32` для 32-битного `int`), разыменование `nullptr` — всё UB.
ASAN проверяет ошибки работы с памятью: границы, use-after-free, double-free. UBSAN проверяет
сами операции языка, являющиеся UB по стандарту: переполнение, сдвиг, выравнивание. Они не
заменяют друг друга, включают вместе: `-fsanitize=address,undefined`."

Углубление: "Почему код может работать в `-O0` и падать в `-O2`?" → оптимизатор релизной
сборки строит код в предположении, что UB не происходит, и может убрать проверки, на которые
программист рассчитывал.

**Факты для карточек**
- base | Значение INT_MAX для 32-битного int? — 2147483647
- core | Флаг компилятора, включающий сразу ASAN и UBSAN? — -fsanitize=address,undefined

Почему дальше: C++ отвечает за корректность в пределах одного процесса; следующий блок
вопросов — про то, что происходит на границе процесса и ядра.

### Linux

**Вопрос 5. Процесс упал, echo $? показывает 139. Что произошло?**

Чего ждёт интервьюер: связь оболочечного кода возврата с сигналом, а не просто "процесс
упал".

Заготовка ответа: "Оболочка кодирует код возврата как 128 + номер сигнала. 139 = 128 + 11 —
`SIGSEGV`, падение по памяти. 137 = 128 + 9 — `SIGKILL`, часто это OOM-killer. 143 = 128 + 15
— `SIGTERM`, корректный запрос на завершение. В коде это разбирается макросами
`WIFSIGNALED`/`WTERMSIG` над `status` из `waitpid`, а не вручную арифметикой."

Углубление: "Можно ли перехватить SIGKILL обработчиком?" → нет, `SIGKILL` (9) и `SIGSTOP` (19)
нельзя ни перехватить, ни заблокировать — ядро обрабатывает их безусловно, это единственный
гарантированный способ остановить процесс, который сам игнорирует остальные сигналы.

**Факты для карточек**
- base | Откуда взялись коды возврата 137 и 139? — 128 + номер сигнала: 137 = SIGKILL(9), 139 = SIGSEGV(11)
- core | Какие два сигнала нельзя перехватить или заблокировать? — SIGKILL (9) и SIGSTOP (19)

**Вопрос 6. Что такое зомби-процесс?**

Чего ждёт интервьюер: точное понимание, что зомби не расходует память, а занимает запись в
таблице процессов.

Заготовка ответа: "Завершившийся ребёнок не исчезает полностью — ядро держит его запись (код
возврата) в таблице процессов, пока родитель не заберёт её через `wait`/`waitpid`. Такой
процесс — зомби, состояние `Z` в `ps`. Памяти он не занимает, но занимает слот в таблице
процессов; накопление зомби — это утечка слотов, а не утечка памяти."

Углубление: "Как избавиться от зомби, если родитель не вызывает wait?" → либо родитель обязан
вызывать `waitpid` (часто в обработчике `SIGCHLD`), либо если родитель сам умирает раньше
ребёнка — ребёнка усыновляет init/systemd (PID 1), который делает `wait` за него, и ребёнок
зомби не остаётся.

**Факты для карточек**
- base | Состояние зомби-процесса в выводе ps? — Z
- core | Что именно занимает зомби-процесс — память или что-то другое? — слот в таблице процессов, не память

**Вопрос 7. Чем epoll лучше select для сервера с тысячами соединений?**

Чего ждёт интервьюер: количественное сравнение сложности и лимитов, а не общую фразу "epoll
быстрее".

Заготовка ответа: "select ограничен `FD_SETSIZE` = 1024 дескриптора и на каждый вызов
проходит весь набор целиком — `O(n)` независимо от того, сколько реально готово, плюс
`fd_set` надо пересобирать перед каждым вызовом. epoll разносит регистрацию (`epoll_ctl`,
список интереса на красно-чёрном дереве в ядре) и ожидание (`epoll_wait`, который просто
возвращает уже готовые дескрипторы) — `O(1)` на каждое готовое событие, без лимита 1024."

Углубление: "Level-triggered или edge-triggered по умолчанию?" → level-triggered — у epoll по
умолчанию и всегда у select/poll: событие сообщается, пока условие истинно. Edge-triggered —
явный флаг `EPOLLET`, требует вычитывать данные до `EAGAIN` на неблокирующем дескрипторе,
иначе остаток данных не будет сигнализирован повторно.

**Факты для карточек**
- base | Жёсткий лимит select и его значение? — FD_SETSIZE, 1024
- core | Сложность epoll_wait на одно готовое событие против select/poll на весь набор? — epoll_wait O(1) на событие; select/poll O(n) на весь набор при каждом вызове

**Вопрос 8. Что делает mmap и чем MAP_SHARED отличается от MAP_PRIVATE?**

Чего ждёт интервьюер: механизм ленивого отображения через page fault, а не "mmap читает файл
в память".

Заготовка ответа: "mmap резервирует диапазон виртуальных адресов и связывает его со
страницами файла в страничном кэше ядра; физического чтения при самом вызове нет. При первом
обращении к странице — page fault: minor, если страница уже в кэше (дёшево), major, если её
нужно реально прочитать с диска (дорого). `MAP_SHARED` — изменения видны всем процессам и
попадают в файл на диске; `MAP_PRIVATE` — copy-on-write, как при `fork`: страницы общие, пока
не начинается запись, тогда процесс получает свою копию, а файл на диске не меняется."

Углубление: "Когда read быстрее mmap?" → при однократном последовательном чтении небольшого
файла — накладные расходы на настройку отображения и page fault на каждую новую страницу не
амортизируются, обычный `read` одним вызовом дешевле.

**Факты для карточек**
- base | Разница MAP_SHARED и MAP_PRIVATE? — MAP_SHARED: изменения видны другим и попадают в файл; MAP_PRIVATE: copy-on-write, изменения приватны
- core | Чем minor page fault отличается от major? — minor: страница уже в кэше (дёшево); major: страница читается с диска (дорого)

Почему дальше: Linux управляет одним узлом; следующий блок — про то, как узлы вообще находят
друг друга и обмениваются байтами по проводу.

### Сети

**Вопрос 9. Из чего состоит Ethernet-заголовок и что меняет VLAN?**

Чего ждёт интервьюер: точные числа байт заголовка и понимание, зачем и куда вставляется тег.

Заготовка ответа: "Ethernet-заголовок — 14 байт: 6 байт MAC получателя, 6 байт MAC
отправителя, 2 байта EtherType. После полезной нагрузки — 4-байтовый трейлер FCS, в заголовок
не входит. VLAN-тег 802.1Q по стандарту вставляет 4 дополнительных байта между MAC
отправителя и EtherType: TPID (2 байта, фиксировано 0x8100) и TCI (2 байта: PCP 3 бита, DEI 1
бит, VID 12 бит, диапазон реально используемых значений 1–4094). Заголовок с тегом растёт с
14 до 18 байт."

Углубление: "Что будет, если не учесть эти 4 байта при расчёте MTU?" → ошибка ровно на 4
байта — типично ловится сравнением дампа `tcpdump` с ожидаемой длиной кадра.

**Факты для карточек**
- base | Длина Ethernet-заголовка и длина заголовка с VLAN-тегом? — 14 байт без тега, 18 байт с тегом 802.1Q
- core | Значение TPID и число бит поля VID? — TPID = 0x8100, VID = 12 бит (диапазон 1–4094)

**Вопрос 10. Дана подсеть 10.0.1.130/26. Назовите сеть, broadcast и диапазон хостов.**

Чего ждёт интервьюер: расчёт на лету, а не заученный пример из урока.

Заготовка ответа: "/26 — 6 бит под хосты, 64 адреса всего, 62 доступно хостам (минус адрес
сети и broadcast). Маска в десятичном виде — 255.255.255.192. Для 10.0.1.130/26: сеть —
10.0.1.128, broadcast — 10.0.1.191, диапазон хостов — 129..190."

Углубление: "Как быстро найти самую узкую подсеть под 100 хостов?" → формула `32 -
ceil(log2(h+2))`: для `h=100` это `32 - ceil(log2(102)) = 32 - 7 = /25` (126 хостов — ближайшая
подходящая степень двойки сверху, `/26` с 62 хостами уже не хватит).

**Факты для карточек**
- base | Сколько хостов доступно в подсети /26 и как выглядит маска в десятичном виде? — 62 хоста, 255.255.255.192
- core | Сеть, broadcast и диапазон хостов для 10.0.1.130/26? — сеть 10.0.1.128, broadcast 10.0.1.191, хосты 129–190

**Вопрос 11. Как работает traceroute и при чём тут TTL?**

Чего ждёт интервьюер: понимание, что traceroute не использует отдельный протокол обнаружения
маршрута, а эксплуатирует побочный эффект TTL.

Заготовка ответа: "TTL уменьшается на 1 на каждом маршрутизаторе на пути пакета; при
обнулении пакет отбрасывается, а отправителю уходит ICMP Time Exceeded (тип 11). traceroute
последовательно шлёт пакеты с TTL 1, 2, 3... — пакет с TTL 1 умирает на первом
маршрутизаторе, тот присылает Time Exceeded со своим адресом; пакет с TTL 2 умирает на
втором, и так далее, пока пакет не дойдёт до получателя. Список хопов восстанавливается по
цепочке ICMP-ответов без специального протокола обнаружения маршрута."

Углубление: "Почему ping иногда не проходит, а обычное TCP-соединение на тот же хост
работает?" → ICMP может быть заблокирован файрволом отдельно от TCP-порта — это два разных
уровня фильтрации, `ping host` и `curl host` в таком случае дают разный результат.

**Факты для карточек**
- base | На сколько уменьшается TTL на каждом маршрутизаторе и какой ICMP-тип шлётся при обнулении? — на 1; ICMP Time Exceeded, тип 11
- core | С какого TTL traceroute начинает зондирование и почему именно так восстанавливает маршрут? — с TTL=1, наращивая на 1 — каждый пакет умирает на очередном хопе и раскрывает его адрес

**Вопрос 12. Три сегмента TCP-рукопожатия и зачем нужен TIME_WAIT?**

Чего ждёт интервьюер: точная последовательность флагов и механическая причина TIME_WAIT, а не
"так положено по стандарту".

Заготовка ответа: "SYN от клиента со своим ISN → SYN+ACK от сервера (Ack = ISN клиента + 1, и
собственный ISN сервера) → ACK от клиента, подтверждающий ISN сервера. Двух шагов
недостаточно, потому что соединение полнодуплексное: сервер не может быть уверен, что его
SYN-ACK дошёл, пока не получит финальный ACK. Закрытие — уже 4 сегмента (FIN, ACK, FIN, ACK)
из-за полузакрытия каждого направления по отдельности. Сторона, отправившая финальный ACK,
уходит в TIME_WAIT на 2×MSL — она должна поймать задержавшиеся в сети дубликаты старых
сегментов и быть готова повторно отправить последний ACK, если партнёр повторит FIN."

Углубление: "Сколько реально длится TIME_WAIT в Linux?" → 60 секунд, фиксированная константа
ядра `TCP_TIMEWAIT_LEN`, а не номинальные 4 минуты (2×2 мин) по RFC 793.

**Факты для карточек**
- base | Сколько сегментов в three-way handshake и в полном закрытии соединения? — 3 (SYN, SYN+ACK, ACK) и 4 (FIN, ACK, FIN, ACK)
- deep | Сколько секунд реально длится TIME_WAIT в Linux? — 60 секунд (константа TCP_TIMEWAIT_LEN), не совпадает с номинальными 4 минутами по RFC 793

Почему дальше: 12 вопросов закрывают C/C++, Linux и сети по отдельности; дальше — не техника,
а формат самого разговора: что спросить у работодателя и как рассказать про себя, чтобы не
потерять баллы на ровном месте.

## 4. Вопросы работодателю

Задавать под конец интервью, когда спросят "есть ли у вас вопросы" — не сам факт вопроса
важен, а конкретность.

1. На каком стандарте C++ пишут в проекте (C++11/14/17/20), какой компилятор и целевая
   архитектура (x86, ARM, embedded-таргет)?
2. Как устроено код-ревью: обязательно ли оно для джуна перед мерджем, кто ревьюит, сколько
   итераций в среднем проходит один PR?
3. Что гоняет CI на каждый коммит — юнит-тесты, статический анализ, санитайзеры? Обязательно
   ли покрытие тестами для мерджа?
4. Какие задачи обычно дают джуну в первый месяц — багфиксы, мелкие фичи, документация,
   разбор legacy-кода?
5. Есть ли доступ к реальному стенду/железу для отладки, или разработка сначала идёт на
   эмуляторе/симуляторе?
6. Кто ментор на испытательный срок и как часто идёт синхронизация — ежедневный созвон,
   раз в неделю, по запросу?
7. Что для команды считается успехом джуна через год — конкретные вехи или метрики, а не
   общие слова?
8. Какая доля времени уходит на поддержку и доработку существующего кода против новых задач
   с нуля?

**Факты для карточек**
- base | Сколько вопросов работодателю стоит подготовить заранее на такое интервью? — 8, каждый — конкретный, не риторический
- core | Когда обычно задают вопросы работодателю на техническом скрининге? — в конце интервью, по приглашению интервьюера

Почему дальше: вопросы работодателю закрывают техническую часть разговора; последний пункт —
не техника вообще, а то, как честно и без потери баллов рассказать про собственный опыт.

## 5. Легенда по опыту

Задача — не приукрашивать, а структурировать то, что уже сделано руками, так, чтобы
интервьюер за 60–90 секунд понял уровень, не тратя время на наводящие вопросы. Рабочий каркас
для таких ответов — STAR (Situation, Task, Action, Result): сначала контекст в одной фразе,
потом конкретное действие, потом измеримый результат.

**Что говорить как есть, потому что это правда и это ценно:**
- Практика с C/C++ и Linux не в вакууме, а руками: написанный код, работа в терминале,
  скрипты.
- Опыт сборки и CI на собственном проекте (например, сборка APK и настройка пайплайна) —
  конкретный пример того, что такое "довести до работающего результата", даже если стек не
  совпадает с C++/embedded напрямую: понимание пайплайна сборки, зависимостей, автоматизации
  переносится.
- Текущая подготовка по плану — не "готовился неделю перед собеседованием для галочки", а
  системный разбор конкретных тем с самопроверкой (карточки, мок-интервью) — это тоже сигнал
  об умении учиться быстро и целенаправленно.

**Как объяснять пробелы, не оправдываясь:**
- "Алгоритмы — тема, которую я целенаправленно добираю последние недели: понимаю формальные
  свойства структур (сложность, инварианты, границы применимости), но production-опыта
  оптимизации под high-load нет — это зона роста, а не то, что я скрываю."
- Если спросят про конкретный API, которого не касался — честно "не работал с этим напрямую,
  но по механизму ожидаю Y, потому что Z" — интервьюер оценивает способность рассуждать, а не
  только базу знаний.

**Чего не говорить:**
- Не заявлять претензию на роль лида или архитектурные решения, если такого опыта не было —
  на джуновском скрининге это резко расходится с реальным уровнём ответов на технические
  вопросы и подрывает доверие ко всему остальному сказанному.
- Не преувеличивать глубину embedded/kernel-опыта: тема ядра в этом плане закрыта на уровне
  "отвечать словами" (`D6_kernel`), а не "писал драйверы в проде" — если спросят "а сами
  писали?", честный ответ "нет, разбирал теоретически и на учебных примерах" безопаснее любой
  неправды, которая всплывёт на первом же уточняющем вопросе.

**Факты для карточек**
- base | Из каких 4 частей состоит структура STAR для ответа про опыт? — Situation, Task, Action, Result
- core | Как правильно называть пробел в алгоритмах на собеседовании — скрывать или называть прямо? — называть прямо: конкретная тема добирается сейчас, с указанием, что уже понятно (сложность, инварианты)

## Проверь себя

<details>
<summary>1. Почему для top-K наибольших элементов в потоковом режиме нужен именно min-heap размера k, а не max-heap?</summary>
Min-heap хранит k текущих кандидатов, и на вершине (O(1) доступ) всегда самый маленький из
них — именно с ним сравнивают каждый новый элемент: если новый больше минимума кучи, минимум
вытесняется, новый занимает его место. Max-heap размера k показывал бы на вершине самый
большой из текущих k кандидатов, что не даёт дешёвого способа проверить "стоит ли вытеснять
кого-то" — пришлось бы искать минимум отдельно, теряя весь выигрыш от кучи.
</details>

<details>
<summary>2. Процесс завершился с кодом 139. Что произошло и какой командой в коде это разбирают?</summary>
139 = 128 + 11, то есть процесс убит сигналом SIGSEGV — падение по памяти (например,
разыменование невалидного указателя). В коде это разбирается макросами WIFSIGNALED(status) и
WTERMSIG(status) над status, полученным из wait/waitpid, а не вычитанием 128 вручную.
</details>

<details>
<summary>3. Почему epoll_wait даёт O(1) на готовое событие, а select — O(n) на весь набор при каждом вызове?</summary>
select при каждом вызове проходит весь переданный набор дескрипторов целиком, чтобы понять,
какие из них готовы — работа пропорциональна общему числу отслеживаемых дескрипторов
независимо от того, сколько реально готовы. epoll разносит регистрацию (epoll_ctl, список
интереса на красно-чёрном дереве в ядре) и ожидание (epoll_wait): ядро само добавляет
дескриптор в список готовых асинхронно, когда его состояние меняется, и epoll_wait просто
отдаёт содержимое этого списка — работа пропорциональна числу реально готовых дескрипторов.
</details>

<details>
<summary>4. Для 10.0.1.130/26 назовите адрес сети и диапазон доступных хостов, объяснив расчёт.</summary>
/26 оставляет 6 бит под хосты (32-26=6), это 64 адреса всего, из них 62 доступны хостам
(минус адрес сети и broadcast). Маска — 255.255.255.192, последний октет сети получается
округлением 130 вниз до кратного 64: сеть 10.0.1.128, broadcast 10.0.1.191 (128+63), диапазон
хостов — 129..190.
</details>

<details>
<summary>5. Почему TCP-рукопожатие требует три сегмента, а не два?</summary>
Соединение TCP полнодуплексное — у каждого направления свой независимый ISN (начальный
порядковый номер), и обе стороны должны не только сообщить свой ISN, но и получить
подтверждение, что собеседник его получил. После SYN и SYN-ACK сервер ещё не знает, дошёл ли
его SYN-ACK до клиента — только финальный ACK клиента даёт это подтверждение и завершает
синхронизацию обоих направлений.
</details>

<details>
<summary>6. Чем зомби-процесс отличается от процесса-сироты и что физически занимает зомби?</summary>
Зомби — завершившийся процесс, чья запись (код возврата) ещё не забрана родителем через
wait/waitpid; он не занимает память, но занимает слот в таблице процессов. Сирота — процесс,
чей родитель умер раньше него; его усыновляет init/systemd (PID 1), и это состояние не
связано с зомби напрямую — сирота продолжает работать, зомби уже завершился и ждёт только
уборки записи.
</details>

## Материалы

- cppreference, `std::unordered_map` — https://en.cppreference.com/w/cpp/container/unordered_map
- cppreference, `std::move` — https://en.cppreference.com/w/cpp/utility/move
- man7.org, `epoll(7)` — https://man7.org/linux/man-pages/man7/epoll.7.html
- man7.org, `mmap(2)` — https://man7.org/linux/man-pages/man2/mmap.2.html
- man7.org, `wait(2)` — https://man7.org/linux/man-pages/man2/wait.2.html
- RFC 793, Transmission Control Protocol — https://datatracker.ietf.org/doc/html/rfc793