База, которая не устаревает вместе с языками и фреймворками: как растёт сложность, как устроены хеш-таблица и куча, почему быстрая сортировка иногда медленная и как ищут путь на карте. Алгоритмы можно пройти по шагам и на своих данных.
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 ~, сдвиги << и >> работают с каждым битом отдельно и стоят один такт.
Ядро останавливает один поток, сохраняет его регистры и состояние и загружает другой. Прямая цена — единицы микросекунд, но главное — остывшие кэши процессора.
CSRF — чужой сайт заставляет браузер жертвы отправить запрос на ваш сайт; браузер сам приложит cookie, и запрос выполнится от имени пользователя. CORS — правила, когда скрипт с…
Взаимная блокировка — потоки ждут друг друга по кругу: первый держит A и ждёт B, второй держит B и ждёт A. Никто не продвинется.
Дейкстра находит кратчайшие пути от одной вершины во взвешенном графе с неотрицательными весами: каждый раз берёт ближайшую ещё не обработанную вершину и ослабляет рёбра из неё.
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).
Стек — память для вызовов функций: локальные переменные и адрес возврата, выделяется и освобождается автоматически при входе и выходе. Куча — память для данных, чьё время жизни не…
Симметричное — один общий ключ шифрует и расшифровывает (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 в браузере другого пользователя: скрипт работает с правами сайта — читает данные страницы, отправляет запросы от имени…
sotto слышит вопрос и сразу показывает короткий ответ. Оставьте контакт — пришлём доступ и промокод.
sotto