Основы computer science для собеседования

A — Дейкстра с подсказкой направления: вершины выбираются по f = g + h, где g — пройденное расстояние, h — оценка остатка до цели.

Амортизированная сложность — средняя стоимость операции в длинной серии: редкие дорогие операции «размазываются» по многим дешёвым.

Массив — элементы подряд в памяти: доступ по индексу O(1), вставка в середину O(n); связный список — узлы со ссылками: вставка по известному месту O(1), доступ по индексу O(n).

Многопоточность — несколько потоков ОС, их переключает ядро. Асинхронность — одна (или немного) нить выполнения переключается между задачами сама, в точках ожидания (await).

CAS (compare-and-swap) — инструкция процессора «если в ячейке ещё A, запиши B» за один неделимый шаг. На ней строят атомарные счётчики и структуры без блокировок.

B-дерево — сбалансированное дерево с широкими узлами: в узле сотни ключей, узел = страница на диске (8–16 КБ). Высота 3–4 даже для миллиардов строк — значит, 3–4 чтения страницы.

BFS идёт по уровням через очередь и находит кратчайший путь по числу рёбер; DFS идёт вглубь до упора через стек или рекурсию.

О-большое описывает, как растёт время или память алгоритма с ростом входа n, отбрасывая константы и младшие слагаемые.

В двоичном дереве поиска для каждого узла слева — меньшие ключи, справа — большие; поиск идёт по одной ветке — O(высоты).

В отсортированном массиве сравниваем искомое с серединой и отбрасываем половину, где его быть не может: O(log n) шагов.

AND &, OR |, XOR ^, NOT ~, сдвиги << и >> работают с каждым битом отдельно и стоят один такт.

CDN — сеть серверов по всему миру (или стране), которые кэшируют копии ваших файлов и отдают их пользователю с ближайшего узла. Сайт грузится быстрее (меньше расстояние и…

Ядро останавливает один поток, сохраняет его регистры и состояние и загружает другой. Прямая цена — единицы микросекунд, но главное — остывшие кэши процессора.

CSRF — чужой сайт заставляет браузер жертвы отправить запрос на ваш сайт; браузер сам приложит cookie, и запрос выполнится от имени пользователя. CORS — правила, когда скрипт с…

Взаимная блокировка — потоки ждут друг друга по кругу: первый держит A и ждёт B, второй держит B и ждёт A. Никто не продвинется.

dig example.ru — A-запись (IPv4) и оставшийся TTL; dig example.ru AAAA, MX, TXT, CNAME, NS — другие типы; dig +short — только ответ. dig @8.8.8.8 example.ru — спросить конкретный…

Дейкстра находит кратчайшие пути от одной вершины во взвешенном графе с неотрицательными весами: каждый раз берёт ближайшую ещё не обработанную вершину и ослабляет рёбра из неё.

Резолверы держат запись до истечения TTL, поэтому переключение не мгновенное. План: заранее (за время не меньше текущего TTL) понизить TTL до минут → поднять новый сервер и…

DNS — распределённая иерархическая база «имя → адрес». Рекурсивный резолвер спрашивает по цепочке: корневые серверы → серверы зоны .ru → авторитетный сервер домена.

Динамическое программирование — решать задачу через ответы на перекрывающиеся подзадачи, считая каждую один раз и сохраняя в таблицу.

Файловый дескриптор — небольшое целое число, по которому процесс обращается к открытому ресурсу: файлу, сокету, каналу, устройству.

double хранит число как двоичную дробь: знак, порядок и 52 бита мантиссы. 0.1 в двоичной системе бесконечна, как 1/3 в десятичной, — хранится приближение.

Два основных способа: матрица смежности (таблица V×V) и список смежности (для каждой вершины — список соседей).

Хеш-таблица — массив «корзин»: хеш-функция превращает ключ в номер корзины, поэтому поиск, вставка и удаление в среднем — O(1).

Кодирование (Base64, URL-кодирование) — смена формата, обратимо без секрета. Шифрование — обратимо только с ключом. Хеширование — необратимый отпечаток фиксированной длины.

Двоичная куча — дерево, где родитель не больше потомков (min-heap): минимум всегда в корне, вставка и извлечение — O(log n).

HTTP/1.1 — текст, один запрос за раз в соединении. HTTP/2 — бинарные кадры, много потоков в одном TCP-соединении. HTTP/3 — то же поверх QUIC (UDP), без общей блокировки при потере…

Результат не влезает в разрядность — в Java, Go, C# он молча заворачивается по модулю 2ⁿ: MAX_VALUE + 1 = MIN_VALUE.

Уровни изоляции — компромисс между параллельностью и корректностью: чем ниже уровень, тем больше аномалий пропускается.

Наносекунды — процессор и кэши, ~100 нс — оперативная память, десятки–сотни микросекунд — SSD и сеть внутри дата-центра, миллисекунды — диск HDD и другой город, ~100 мс — другой…

LSM-дерево превращает случайные записи в последовательные: запись идёт в журнал и в память (memtable), при заполнении memtable сбрасывается на диск отсортированным неизменяемым…

Компилятор, JIT и процессор переупорядочивают и кэшируют операции с памятью — для одного потока результат тот же, для другого нет. Без синхронизации запись может стать видна…

Делим массив пополам, рекурсивно сортируем половины и сливаем их, каждый раз беря меньший из двух первых элементов.

Деньги — в целых минимальных единицах (копейках) или в десятичном типе: BigDecimal, Decimal, NUMERIC в базе. Не в double.

Мьютекс — замок на одного: в критической секции один поток, отпустить может только владелец. Семафор — счётчик разрешений: одновременно до N потоков.

Многоверсионность: изменение строки создаёт новую версию, а старая остаётся. Каждая транзакция читает снимок — версии, подтверждённые до её начала (или до начала запроса).

Пессимистическая — сначала блокируем строку (SELECT ... FOR UPDATE), потом меняем; остальные ждут. Оптимистическая — не блокируем, а при записи проверяем версию: UPDATE ... WHERE…

Планировщик выдаёт потокам, готовым к работе, кванты времени на ядрах и вытесняет их по таймеру — так один поток не захватит процессор.

Сеть устроена слоями: каждый решает свою задачу и пользуется нижним. OSI — учебная модель из 7 уровней, на практике работает TCP/IP из 4.

ОС кэширует содержимое файлов в свободной памяти — page cache. Повторное чтение берётся из памяти, а запись сначала попадает в кэш и на диск уходит позже.

Не хранить пароль вовсе — только результат медленной функции с солью: argon2id, bcrypt или scrypt. При входе считаем то же самое и сравниваем.

Процесс — запущенная программа со своим адресным пространством и ресурсами. Поток — ход выполнения внутри процесса; потоки делят память процесса.

Производители кладут задачи в ограниченную блокирующую очередь, потребители забирают. Полная очередь останавливает производителя, пустая — потребителя.

Выбираем опорный элемент, разбиваем массив: меньшие — влево, большие — вправо, опорный встаёт на своё место; затем рекурсивно сортируем части.

Гонка — результат зависит от того, в каком порядке потоки выполнили свои шаги. Классика: count++ — это три шага (прочитать, прибавить, записать), и два потока теряют обновления.

Рекурсия — функция вызывает саму себя для меньшей задачи и останавливается на базовом случае; мемоизация — кэш уже посчитанных результатов.

Строковое: строка лежит целиком подряд — быстро прочитать или изменить одну запись (OLTP). Колоночное: каждая колонка лежит отдельно — быстро посчитать агрегат по нескольким…

SIGTERM — вежливая просьба завершиться: процесс может её перехватить и закончить работу. SIGKILL — убийство ядром, перехватить нельзя.

Сравнениями — нельзя: любой алгоритм, который только сравнивает элементы, в худшем случае делает Ω(n log n) сравнений. Без сравнений — можно при ограничениях на ключи.

Простые — пузырьком, вставками, выбором — O(n²); эффективные — слиянием, быстрая, пирамидальная — O(n log n). Отличаются худшим случаем, памятью и устойчивостью.

Инъекция — данные пользователя попадают в текст запроса и меняют его смысл: ' OR '1'='1 превращает проверку пароля в «всегда истина».

Устойчивая сортировка сохраняет исходный порядок элементов с равными ключами.

Стек — последним пришёл, первым ушёл (LIFO); очередь — первым пришёл, первым ушёл (FIFO). Основные операции — O(1).

Стек — память для вызовов функций: локальные переменные и адрес возврата, выделяется и освобождается автоматически при входе и выходе. Куча — память для данных, чьё время жизни не…

Статический сайт — готовые HTML, CSS, JS и картинки, которые отдаются как файлы. Его кладут на статический хостинг (GitHub Pages, облачное объектное хранилище, Netlify и аналоги)…

Симметричное — один общий ключ шифрует и расшифровывает (AES): быстро, но ключ надо как-то передать. Асимметричное — пара ключей: открытый знают все, закрытый — только владелец…

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

Установка — SYN → SYN-ACK → ACK: стороны обмениваются начальными номерами последовательности. Один оборот (RTT) до первых данных.

Каждый байт пронумерован, получатель подтверждает принятое (ACK), неподтверждённое отправляется повторно — по таймауту или по трём повторным ACK.

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

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

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

TLS даёт шифрование, целостность и подлинность сервера. В рукопожатии стороны согласуют общий ключ (обмен Диффи — Хеллмана), сервер доказывает владение сертификатом, дальше данные…

Почти везде — дополнительный код (two's complement): старший бит отрицательный, его вес −2ⁿ⁻¹.

Unicode — таблица: каждому символу номер (кодовую точку), U+0416 — «Ж». UTF-8 — способ записать эти номера байтами.

Каждый процесс видит своё виртуальное адресное пространство; процессор с ОС переводят виртуальные адреса в физические страницами (обычно по 4 КБ).

Сначала запись в журнал, потом в данные. Перед изменением страниц база дописывает в конец журнала, что собирается изменить, и делает fsync. После сбоя журнал проигрывается заново…

DNS находит IP → TCP-рукопожатие → TLS-рукопожатие → HTTP-запрос → сервер (балансировщик, приложение, база) → ответ → браузер разбирает HTML, догружает ресурсы и рисует страницу.

XSS — злоумышленник заставляет сайт выполнить его JavaScript в браузере другого пользователя: скрипт работает с правами сайта — читает данные страницы, отправляет запросы от имени…