Структуры данных: хеш-таблицы, деревья, кучи, очереди, LRU

Кратко о теме

Подтема выглядит разнородной — тут и B-деревья, и Kafka, и defer, — но на собеседовании она сводится к одной проверке: понимает ли кандидат, из чего собираются рабочие структуры и почему выбор структуры определяет сложность операций. Практически всё, что спрашивают, строится из четырёх кирпичей: непрерывный массив (быстрый доступ по индексу, плохие вставки в середину), связный список (дешёвая вставка/удаление по известному узлу, нет произвольного доступа, плохая кэш-локальность), хеш-таблица (амортизированное O(1) по ключу, нет порядка) и дерево (логарифмические операции плюс сохранённый порядок). Все «сложные» структуры — LRU-кеш, очередь с приоритетом, индекс в БД, роутер HTTP — это композиция этих кирпичей под конкретный набор операций.

Второй сквозной сюжет — очереди. Слово перегружено: очередь как абстрактный тип данных (FIFO, Enqueue/Dequeue), очередь как канал в Go (буферизованный канал — это кольцевой буфер под мьютексом плюс две очереди ожидающих горутин), и очередь как брокер сообщений (Kafka, RabbitMQ, NATS). На интервью эти три уровня постоянно смешивают, и хороший ответ начинается с уточнения, о каком уровне речь. Общее у них — развязка производителя и потребителя во времени: буфер сглаживает пики, даёт возможность ретраить и позволяет масштабировать потребителей независимо от производителей. Плата — потеря синхронного ответа, необходимость идемпотентности, дублирование при at-least-once и рост latency в хвостах.

Третий сюжет — хеширование. Хеш-функция отображает произвольные данные в число фиксированной длины; хеш — результат этого отображения. Она односторонняя и не инъективная: коллизии существуют по принципу Дирихле, восстановить вход из хеша нельзя (кроме перебора по малому пространству входов). В хеш-таблице большое хеш-значение сжимается до индекса массива — делением по модулю или, если размер таблицы степень двойки, битовой маской hash & (n-1). Дальше нужна стратегия разрешения коллизий: цепочки (chaining) или открытая адресация. Go до 1.23 использовал бакеты по 8 слотов с overflow-цепочками, а с Go 1.24 встроенная мапа переписана на Swiss Tables — открытую адресацию с группами по 8 слотов и control word.

Деревья на собеседовании нужны там, где нужен порядок и диапазонные запросы. Обычное несбалансированное BST вырождается в список при отсортированных вставках, поэтому в реальности живут сбалансированные варианты: AVL и красно-чёрные в памяти, B/B+-деревья на диске. Ключевое свойство B-дерева — высокий fan-out: узел размером со страницу диска (4–16 КБ) хранит сотни ключей, поэтому глубина индекса на миллиарды строк — 3–4 уровня, то есть 3–4 обращения к странице.

Вопросы и ответы

Как организовать архитектуру без очередей, если несколько сервисов должны реагировать на одно событие?

Коротко. Варианты три: синхронный fan-out (продюсер сам вызывает всех подписчиков по HTTP/gRPC), транзакционный outbox с воркером-рассыльщиком или CDC из журнала БД, и pull-модель, когда подписчики сами периодически опрашивают источник или читают его состояние. Убрав брокер, вы не убираете задачу доставки — вы берёте её ответственность на себя.

Глубже. Синхронный fan-out прост, но связывает продюсера со всеми потребителями: падение или тормоза одного подписчика бьют по времени ответа исходной операции, а частичный успех («двум доставили, третьему нет») приходится разруливать ретраями, что требует идемпотентности на стороне получателя. Транзакционный outbox — обычно лучший компромисс без брокера: событие пишется в таблицу outbox в той же транзакции, что и бизнес-изменение, а отдельный воркер читает таблицу и разносит события подписчикам с ретраями и exponential backoff; таблица становится тем самым журналом, гарантирующим at-least-once. CDC (Debezium, логическая репликация Postgres) — то же самое, но без явной таблицы: читается WAL. Pull-модель хороша, когда подписчикам важно текущее состояние, а не факт события: они периодически спрашивают GET /changes?since=cursor, и тогда потеря одного опроса не фатальна. Что бы вы ни выбрали, обязательны идемпотентные обработчики (дедупликация по event_id), версия/номер события для упорядочивания и явная политика «что делать, если подписчик недоступен час». Если после этого перечня остаётся нужда в буфере, ретраях и реплее — вы фактически написали брокер, и честнее взять готовый.

Что такое B-tree, как работает и где применяется? Чем отличается от других деревьев?

Коротко. B-дерево — сбалансированное поисковое дерево с высоким ветвлением: в узле хранится до m-1 отсортированных ключей и до m указателей на детей, все листья лежат на одной глубине. Размер узла подгоняют под страницу диска, поэтому дерево на миллиарды записей имеет высоту 3–4, и поиск стоит 3–4 чтения страницы. Это основная структура индексов в СУБД и файловых системах.

Глубже. Поиск идёт как в BST, только в узле выбирается не «влево/вправо», а нужный интервал между ключами (внутри страницы — бинарным поиском). Вставка спускается до листа, вставляет ключ и, если узел переполнился, расщепляет его пополам, а средний ключ поднимает в родителя; расщепление может каскадно дойти до корня — тогда дерево растёт вверх, что и держит все листья на одном уровне. Удаление симметрично: при недозаполнении узел заимствует ключ у соседа или сливается с ним. На практике почти везде используется не классическое B-дерево, а B+-дерево: во внутренних узлах только разделяющие ключи (значений нет — значит, ветвление ещё выше), все данные в листьях, а листья связаны в двусвязный список — это даёт дешёвый range scan и ORDER BY без сортировки. Так устроены кластерный индекс InnoDB и btree-индексы PostgreSQL. Отличия от других деревьев: от BST/AVL/RB — ветвление в сотни раз выше и оптимизация под блочный ввод-вывод, а не под сравнения в памяти; от trie — ключи сравниваются целиком, а не по символам, и структура не зависит от алфавита; от LSM-дерева — B-дерево обновляет страницы на месте и оптимизировано под чтение, а LSM пишет последовательно в SSTable-и и оптимизирован под запись ценой read/space amplification.

Что такое куча и где применяется?

Коротко. Куча (heap) — полное бинарное дерево с инвариантом «родитель не больше (min-heap) или не меньше (max-heap) детей», обычно хранимое в массиве без указателей: дети узла i лежат на 2i+1 и 2i+2. Даёт O(1) на просмотр экстремума, O(log n) на вставку и извлечение, O(n) на построение из готового массива. Применяется для очередей с приоритетом, heapsort, top-K, таймеров и алгоритмов на графах.

Глубже. Не путайте эту кучу с кучей-памятью (heap как область аллокации) — на собеседовании это разные вещи с одинаковым названием. Инвариант кучи слабее, чем у BST: он гарантирует только отношение «родитель–ребёнок», поэтому поиск произвольного элемента остаётся O(n), зато вставка дёшева. Восстановление инварианта — sift up после вставки в конец массива и sift down после переноса последнего элемента в корень. В Go куча есть в стандартной библиотеке как интерфейс container/heap: вы реализуете sort.Interface плюс Push/Pop, а пакет даёт heap.Init, heap.Push, heap.Pop, heap.Fix. Типовые применения: Dijkstra и A* (извлекать вершину с минимальной оценкой), слияние k отсортированных потоков, скользящий top-K (держим min-heap размера k — O(n log k) вместо полной сортировки), планировщик задач по дедлайну; сам рантайм Go хранит таймеры в структуре типа кучи, чтобы дешёвого находить ближайший к срабатыванию.

Что такое B-дерево?

Коротко. См. выше подробный ответ про B-tree: сбалансированное многопутевое поисковое дерево с узлом размером со страницу, все листья на одной глубине, высота ~log_m(n).

Глубже. Если вопрос задан коротко, отвечать стоит одним предложением определения и сразу одной причиной существования: «оно придумано под блочные устройства — стоимость операции измеряется не сравнениями, а числом прочитанных страниц, поэтому выгодно класть в один узел сотни ключей». Полезно назвать параметр: у B-дерева порядка m каждый узел, кроме корня, заполнен минимум наполовину — ⌈m/2⌉-1 … m-1 ключей; это инвариант, который поддерживают расщепления и слияния, и он же даёт гарантию по высоте.

Какие еще виды деревьев знаете?

Коротко. Балансируемые поисковые: AVL, красно-чёрное, treap, splay, 2-3 и B/B+/B*. Строковые: trie (префиксное), radix/Patricia, суффиксное дерево. Прикладные: куча, дерево отрезков, дерево Фенвика, дерево интервалов, k-d tree, quadtree/octree, R-tree, дерево Меркла, дерево разбора (AST).

Глубже. Полезно раскладывать по задаче, а не перечислять списком. Порядок и точечные операции в памяти — AVL (жёстче балансирует, быстрее поиск) против красно-чёрного (дешевле вставка/удаление, поэтому его берут в стандартных библиотеках вроде std::map и TreeMap). Порядок на диске — B+. Префиксы и автодополнение — trie и его сжатая версия radix tree (так устроены роутеры HTTP-фреймворков; в Go 1.22 обновлённый net/http.ServeMux тоже строит дерево по сегментам пути). Агрегаты на диапазоне — дерево отрезков и Фенвик. Пространственные запросы — R-tree и k-d tree (индексы PostGIS — R-tree поверх GiST). Проверка целостности набора данных — дерево Меркла (Git, блокчейны, антиэнтропия в Dynamo-подобных базах). В стандартной библиотеке Go готовых сбалансированных деревьев нет: есть container/heap, container/list, container/ring, а за B-деревом идут в github.com/google/btree.

Работал ли с очередями kafka, rabbit, nats?

Коротко. Вопрос про личный опыт. Отвечайте конкретно: какой брокер, какая роль (продюсер/консьюмер/оба), какой профиль нагрузки, какие гарантии доставки настраивали и с какой проблемой столкнулись в проде.

Глубже. Интервьюер хочет услышать не «да, работал», а признаки реального опыта. Каркас ответа: (1) задача — «шина событий заказов, ~5k msg/s, 12 партиций»; (2) выбор — почему Kafka, а не RabbitMQ (нужен реплей и упорядочивание по ключу заказа) или наоборот (нужна маршрутизация по routing key и per-message TTL); (3) настройки, которые вы осознанно трогали — acks=all и min.insync.replicas, размер батча и linger.ms, стратегия коммита офсетов (после обработки, не автокоммитом), max.poll.interval.ms и как ловили ребаланс; (4) проблема и решение — дубли при ретрае решили идемпотентным upsert по event_id, отставание консьюмера ловили по consumer lag в Grafana, ядовитые сообщения уводили в DLQ; (5) чем библиотека — segmentio/kafka-go, confluentinc/confluent-kafka-go (cgo, librdkafka), IBM/sarama; для RabbitMQ — rabbitmq/amqp091-go; для NATS — nats-io/nats.go и JetStream. Типичные ошибки: говорить «Kafka — это очередь» без упоминания, что это распределённый лог с реплеем и retention; обещать exactly-once без объяснения, что это транзакции Kafka внутри её экосистемы плюс идемпотентность на приёмнике; путать consumer group с топиком.

Then an algorithm section follows. The task was to implement an LRU cache.

Коротко. Это фрагмент отчёта о собеседовании, а не вопрос: далее шла алгоритмическая секция с задачей «реализовать LRU-кеш». Готовое решение и разбор — ниже, в вопросах «Рассказать, как устроен LRU cache» и «Как вы реализуете LRU cache на Go?».

Глубже. Что от вас ждут в такой секции: Get и Put за O(1) в среднем, явное вытеснение по достижении ёмкости, корректное обновление порядка при повторном чтении и обсуждение потокобезопасности. Уточняющие вопросы, которые стоит задать вслух до кода: нужна ли конкурентная безопасность, нужен ли TTL, известна ли ёмкость заранее, можно ли пользоваться container/list.

Какие хеш-функции знаете?

Коротко. Некриптографические — FNV-1a, MurmurHash3, xxHash, CityHash/FarmHash, SipHash (ключевая, защищает от hash-flooding), CRC32 (строго говоря контрольная сумма). Криптографические — SHA-256/SHA-512, SHA-3/BLAKE2/BLAKE3, устаревшие MD5 и SHA-1. Для паролей — не «хеш-функции», а медленные KDF: bcrypt, scrypt, PBKDF2, Argon2id.

Глубже. Классы решают разные задачи, и подмена одного другим — типичная ошибка. Некриптографические оптимизированы под скорость и равномерность, их берут для хеш-таблиц, шардирования и дедупликации; они уязвимы к целенаправленному подбору коллизий, поэтому в хеш-таблицах, куда попадают пользовательские данные, применяют ключевые функции с секретным seed — так делает и Go, соля хеш случайным hash0. Криптографические дают стойкость к поиску прообраза и коллизий: SHA-256 и BLAKE — для подписей, контрольных сумм артефактов, Merkle-деревьев; MD5 и SHA-1 сломаны по коллизиям и в новых системах для безопасности неприменимы (для проверки случайных повреждений — ещё сойдут). Пароли требуют намеренно медленных функций с солью и настраиваемым фактором стоимости, иначе перебор на GPU обнуляет защиту. В Go: hash/fnv, hash/crc32, hash/maphash (та же хеш-функция, что у рантайм-мапы, с рандомным seed; в Go 1.24 добавлен maphash.Comparable), crypto/sha256, crypto/hmac, а bcrypt/argon2 — в golang.org/x/crypto. Отдельный класс, о котором приятно упомянуть, — консистентное хеширование (ring hash, rendezvous/HRW) для распределения ключей по узлам с минимальным переездом при изменении их числа.

Можно ли из результата хеш-функции восстановить исходные данные?

Коротко. Нет. Хеш — это отображение произвольно длинного входа в фиксированное число бит, оно необратимо и не инъективно: разным входам могут соответствовать одинаковые хеши. Восстановить можно только перебором, если пространство входов мало.

Глубже. Формально: из-за принципа Дирихле у любого хеша фиксированной длины бесконечно много прообразов, так что «восстановить исходные данные» не имеет смысла даже теоретически — можно лишь найти какой-то прообраз. Практически для криптографических функций поиск прообраза требует ~2^n операций и невыполним. Но это не значит «хеш безопасен всегда»: если множество входов маленькое и предсказуемое (номер телефона, email, короткий пароль, номер карты), перебор или радужные таблицы вскрывают его за минуты — поэтому пароли солят и прогоняют через медленный KDF, а «анонимизация персональных данных хешированием» без соли считается несостоятельной с точки зрения GDPR-практики. Ещё две частые путаницы: хеш — не шифрование (шифрование обратимо при наличии ключа), и хеш — не гарантия подлинности (для этого нужен HMAC или подпись, иначе злоумышленник пересчитает хеш вместе с данными).

Какой порядок на чтение и запись в очереди канала?

Коротко. FIFO на всех уровнях: буфер канала — кольцевой буфер, значения выходят в порядке отправки; заблокированные отправители и получатели стоят в очередях sendq/recvq и пробуждаются в порядке постановки. Гарантий справедливости между несколькими case в select нет — там выбор случайный среди готовых.

Глубже. Внутри runtime.hchan лежат: массив buf на cap элементов, индексы sendx/recvx, счётчик qcount, мьютекс и два waitq (двусвязные списки sudog). Отправка в непустую очередь получателей делает прямую передачу: значение копируется из стека отправителя в стек первого ожидающего получателя мимо буфера — так работает и небуферизованный канал, который вообще не очередь, а рандеву. Если получателей нет, а место в буфере есть, значение кладётся в buf[sendx]; если места нет — горутина паркуется в sendq. Симметрично при чтении из полного буферизованного канала: получатель забирает самый старый элемент из буфера, и туда же сразу дописывается значение первого ожидающего отправителя — так FIFO сохраняется и на границе. Важные следствия для собеседования: порядок доставки по одному каналу гарантирован, порядок между разными каналами — нет; при нескольких получателях кто именно получит элемент, определяется очередью ожидания, а не приоритетом; закрытый канал отдаёт остаток буфера, а потом бесконечно возвращает нулевое значение с ok == false.

От чего зависит количество очередей?

Коротко. От числа независимых потоков событий (разные типы сообщений и схемы), от требований к изоляции (разные SLA, retention, скорость потребителей, чтобы медленный не тормозил быстрого), от требуемого параллелизма потребления и от гарантий упорядочивания. В Kafka к этому добавляется отдельное решение про число партиций внутри топика.

Глубже. Разделяйте два вопроса. Сколько топиков/очередей — определяется доменом: одно бизнес-событие = один топик, если у него своя схема, свои потребители и свой срок хранения; смешивать разнородные события в одну очередь плохо, потому что нельзя независимо масштабировать и нельзя выборочно перечитать. Отдельные очереди заводят под ретраи и DLQ. Сколько партиций — определяется пропускной способностью и параллелизмом: число активных консьюмеров в группе не может превышать число партиций, значит партиций должно быть не меньше желаемого параллелизма, обычно с запасом (уменьшить их потом нельзя). Ограничители сверху: на брокере каждая партиция — это файлы, память под индексы и время на ребаланс; тысячи партиций на топик замедляют выборы лидеров и восстановление. Упорядочивание гарантируется только внутри партиции, поэтому ключ партиционирования выбирают по сущности, порядок событий которой важен (order_id, user_id) — и если таких сущностей мало, партиции перекосит. В RabbitMQ логика другая: масштабируются не партиции, а количество очередей и потребителей на очередь, а порядок теряется, как только на очередь сажают больше одного конкурирующего консьюмера с prefetch > 1.

Для чего нужны очереди?

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

Глубже. Разложим по функциям. Буферизация — продюсер пишет со скоростью пиков, консьюмер разгребает со своей скоростью; это защищает медленную БД от всплеска трафика (естественный backpressure). Устойчивость — если консьюмер упал, сообщения ждут в очереди, а не теряются; отсюда же ретраи и DLQ. Развязка по контрактам — продюсер не знает своих потребителей и не ломается, когда добавляется третий подписчик. Fan-out — одно событие обрабатывают несколько независимых сервисов. Асинхронность — HTTP-ответ отдаётся сразу, тяжёлая работа (отчёт, письмо, видео) идёт в фоне. Реплей — в Kafka лог хранится независимо от факта чтения, и новый сервис может перечитать историю с нуля. Обратная сторона, которую обязательно надо назвать: возрастает end-to-end latency и сложность отладки, доставка обычно at-least-once, то есть обработчики обязаны быть идемпотентными; глобального порядка нет; появляется новый компонент, который сам может стать точкой отказа, а очередь при отставании консьюмера превращается в источник неограниченного роста лага.

Какие бывают деревья?

Коротко. См. выше «Какие еще виды деревьев знаете?» — по назначению: поисковые (BST, AVL, RB, treap, B/B+), строковые (trie, radix, суффиксное), приоритетные (куча), для агрегатов на диапазонах (segment tree, Фенвик), пространственные (k-d, quadtree, R-tree), криптографические (Merkle) и синтаксические (AST).

Глубже. Отличие от предыдущего вопроса — здесь уместнее начать с классификации по структурным свойствам, а не по применению: по арности (бинарные и m-арные), по наличию порядка на ключах (поисковые и просто иерархии вроде AST или дерева файлов), по способу балансировки (по высоте — AVL, по цвету — RB, вероятностно — treap и skip-list как «почти дерево», амортизированно — splay), по тому, где лежат данные (во всех узлах или только в листьях, как в B+). Если интервьюер хочет одно название — назовите красно-чёрное и объясните, почему именно его выбирают в библиотеках: O(log n) в худшем случае и меньше поворотов на модификацию, чем в AVL.

Все открытые скобки закрыты скобками того же типа.

Коротко. Это одно из условий классической задачи «валидная скобочная последовательность» (LeetCode 20). Проверяется стеком: открывающие кладём, при закрывающей снимаем вершину и сверяем тип; строка валидна, если ни одна проверка не упала и стек в конце пуст.

Глубже. Пустой стек в конце — это ровно формализация условия «все открытые скобки закрыты». Сложность O(n) по времени и O(n) по памяти в худшем случае.

func isValid(s string) bool {
  pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
  stack := make([]byte, 0, len(s))
  for i := 0; i < len(s); i++ {
    c := s[i]
    switch c {
    case '(', '[', '{':
      stack = append(stack, c)
    case ')', ']', '}':
      if len(stack) == 0 || stack[len(stack)-1] != pairs[c] {
        return false
      }
      stack = stack[:len(stack)-1]
    }
  }
  return len(stack) == 0
}

Скобки должны закрываться в правильном порядке.

Коротко. Второе условие той же задачи: вложенность должна быть корректной, то есть ([)] невалидно, хотя количество скобок каждого типа совпадает. Именно порядок и обеспечивает стек — LIFO по своей природе соответствует вложенности.

Глубже. Если бы порядок был не важен, задача сводилась бы к трём счётчикам, и ([)] считалось бы валидным. Стек нужен ровно потому, что закрывающая скобка обязана соответствовать последней ещё не закрытой открывающей. Полезная модификация, которую любят задавать вдогонку: посчитать минимальное число вставок для валидации строки, или вернуть индекс первого места, где нарушен порядок — для этого в стек кладут не символ, а пару «символ, индекс».

Каждой закрывающей скобке соответствует открытая скобка того же типа.

Коротко. Третье условие: закрывающая при пустом стеке — сразу невалидно ()( — классический контрпример). В коде выше это ветка len(stack) == 0 → false.

Глубже. Три условия вместе (типы совпадают, порядок правильный, лишних закрывающих нет) полностью описывают язык Дика, и стековая проверка — минимальный распознаватель для него; конечным автоматом без памяти этот язык не распознать, что и есть содержательная причина, почему нужен именно стек. Если типов скобок ровно один, достаточно счётчика с проверкой «не ушёл в минус» — O(1) памяти; это хороший ответ на уточнение «а можно без стека?».

Каналы, которые ставят в очередь данные для отправки в другой поток.

Коротко. Это описание буферизованного канала, но с двумя неточностями: очередь есть только у буферизованного канала (небуферизованный — синхронное рандеву без хранения), и данные передаются между горутинами, а не потоками ОС — горутины мультиплексируются планировщиком на потоки.

Глубже. Канал — типизированная конкурентная очередь с встроенной синхронизацией: hchan содержит кольцевой буфер, мьютекс и очереди ожидающих горутин. Данные всегда копируются: отправка копирует значение в буфер или напрямую в стек получателя, поэтому передача больших структур по каналу стоит копирования (часто передают указатель, но тогда владение объектом надо соблюдать по договорённости — гонку компилятор не поймает). Небуферизованный канал даёт happens-before между отправкой и завершением приёма в обе стороны, то есть служит ещё и точкой синхронизации, а не только транспортом. Формулировка «для отправки в другой поток» также маскирует важное: канал не привязан ни к какому потоку, из него могут читать сколько угодно горутин, и каждое значение получит ровно одна из них.

Как устроена структура данных “хеш-таблица”?

Коротко. Массив из N ячеек (бакетов) плюс хеш-функция, которая переводит ключ в число, а число — в индекс ячейки. Коллизии разрешаются либо цепочками (в ячейке список/дерево элементов), либо открытой адресацией (ищем следующую свободную ячейку по правилу пробирования). При превышении коэффициента заполнения таблица увеличивается и элементы перераспределяются.

Глубже. Ключевая величина — load factor α = n/N. При цепочках средняя длина цепочки равна α, поиск — O(1+α); при открытой адресации число проб растёт как 1/(1-α), поэтому таблицу расширяют раньше (обычно при 0.7–0.9). Рост — самая дорогая операция: выделяется массив вдвое больше и все ключи перехешируются, что даёт амортизированное O(1), но одиночную паузу O(n); продвинутые реализации размазывают её (инкрементальный rehash в Redis, эвакуация по 1–2 бакета за операцию в старом Go, расщепление отдельных таблиц в Swiss Tables Go 1.24). Худший случай — O(n), когда все ключи попали в один бакет; защита — качественная хеш-функция и случайный seed (Go солит хеш при создании мапы, что даёт и рандомный порядок обхода, и защиту от hash-flooding). В Go до 1.23 бакет — это 8 слотов плюс массив tophash из старших байтов хешей для быстрой отбраковки и указатель на overflow-бакет; с Go 1.24 — группа из 8 слотов с 8-байтовым control word, где на слот приходится 7 бит хеша, и все 8 слотов сравниваются одной 64-битной операцией.

Рассказать, как устроен LRU cache

Коротко. Это композиция двух структур: хеш-таблица ключ → узел даёт поиск за O(1), а двусвязный список хранит порядок использования — свежие в голове, кандидаты на вытеснение в хвосте. Get находит узел через мапу и переносит его в голову, Put вставляет в голову и при переполнении удаляет хвост, попутно убирая ключ из мапы.

Глубже. Двусвязный список нужен именно потому, что узел надо удалить из середины за O(1), зная только сам узел — в односвязном пришлось бы искать предшественника. Мапа хранит указатель на узел, а узел — свой ключ, иначе при вытеснении хвоста нельзя будет удалить соответствующую запись из мапы (это самая частая ошибка на интервью). Альтернатива без списка — «часы» (CLOCK) или приближение LRU по счётчику обращений: дешевле по памяти, но неточно. Конкурентность: простой вариант — один sync.Mutex на весь кеш, потому что даже Get мутирует порядок и sync.RWMutex тут почти не помогает; для высоконагруженных кешей делают шардирование по хешу ключа (N независимых LRU под своими мьютексами) — так устроен, например, ristretto. TTL добавляют отдельным полем expiresAt в узле с ленивой проверкой при чтении. Стоит упомянуть, что чистый LRU плохо переживает сканирование (один проход по большому набору вымывает горячие данные), поэтому в проде часто берут LRU-K, SLRU или W-TinyLFU.

Есть набор урлов.

Коротко. Обрывок исходника, вопрос не восстанавливается.

Глубже. Фраза — начало условия задачи, продолжение не сохранилось. Если такое встретилось на реальном собеседовании, уточняйте, что требуется: дедупликация и нормализация URL (мапа/множество, net/url.Parse), подсчёт частот доменов (мапа + куча для top-K), краулинг с ограничением параллелизма (errgroup.SetLimit и множество посещённых), или проектирование сокращателя ссылок (хеш/счётчик в base62 + KV-хранилище).

Как устроена структура данных хэш-таблицы?

Коротко. См. выше «Как устроена структура данных “хеш-таблица”?» — массив бакетов, хеш-функция, стратегия разрешения коллизий, рост по load factor.

Глубже. Отличие в акцентах: если вопрос повторили, интервьюер, скорее всего, хочет услышать не общее определение, а конкретику по Go. Тогда: map[K]V — указатель на заголовок в куче, поэтому в функцию передаётся «по ссылке» в бытовом смысле; nil-мапа читается и итерируется, но паникует на записи; элемент мапы не адресуем (&m[k] — ошибка компиляции), потому что при росте данные переезжают; мапа не потокобезопасна, и рантайм с некоторой вероятностью ловит гонку и роняет процесс с fatal error: concurrent map writes; удаление и clear не возвращают память ОС.

Если хэш-функция возвращает огромное число, а массив хэш-таблицы имеет фиксированный размер (например, 100 ячеек), как именно это большое значение преобразуется в конкретный индекс массива?

Коротко. Сжатием диапазона: чаще всего index = hash % N, а если N — степень двойки, то эквивалентно и быстрее index = hash & (N-1) (взятие младших бит). Именно так делает Go: номер бакета — младшие B бит хеша, где число бакетов равно 2^B.

Глубже. Нюансы, которые отличают заученный ответ от понимания. Первое: маска берёт только младшие биты, поэтому если хеш-функция «плохая» и информация в ней сосредоточена в старших битах, всё схлопнется в несколько бакетов — отсюда либо требование к качеству хеша (лавинный эффект), либо перемешивание перед маскированием (в Java h ^ (h >>> 16)). Второе: при простом % с составным N (например, 100) кратные общим делителям ключи распределяются неравномерно, поэтому классические реализации с делением берут N простым — это компромисс между стоимостью деления и качеством. Третье: сама операция деления дорога, а & — один такт, поэтому степень двойки победила почти везде; альтернатива без деления — метод Lemire: (uint64(hash) * uint64(N)) >> 32 для 32-битного хеша. Четвёртое: в Go и других реализациях хеш uint64, так что проблемы со знаком нет, а вот в языках со знаковым хешем нужен abs или маска, иначе получите отрицательный индекс. Наконец, в Swiss Tables Go 1.24 биты хеша делятся на роли: старшие 57 бит (H1) выбирают группу, младшие 7 (H2) хранятся в control word как быстрый фильтр, а самые старшие ещё и индексируют directory таблиц.

Приложение обращается к стороннему сервису, который долго отвечает. Почему это происходит и что можно сделать? Если решаем через очереди, то почему очереди не всегда хорошее решение? Как понять, что сервис принял запрос и как убедиться, что ответ действительно содержит наши данные (синхронно или через Kafka/RabbitMQ)?

Коротко. Сначала измерить: медленно у них, у сети или у нас (пул соединений, DNS, TLS-хендшейк, отсутствие keep-alive). Защита — таймауты и context.WithTimeout, ретраи с backoff только для идемпотентных запросов, circuit breaker, ограничение параллелизма, кеш и деградация. Асинхронность через очередь убирает ожидание из HTTP-запроса, но не ускоряет внешний сервис и добавляет свою цену. Факт приёма подтверждается ack-ом на нужном уровне (HTTP 202 + request_id, acks=all в Kafka, publisher confirms в RabbitMQ), а соответствие ответа именно вашему запросу — корреляционным идентификатором и проверкой полей.

Глубже. Почему долго: чаще всего это не «их сервис тормозит», а комбинация — нет переиспользования соединений (каждый запрос делает TCP+TLS, потому что тело ответа не дочитывается и не закрывается, и соединение не возвращается в пул), маленький MaxIdleConnsPerHost при большом параллелизме, отсутствие таймаутов, из-за чего зависшие запросы держат горутины и пул, наконец троттлинг на их стороне или тяжёлый запрос по объёму данных. Что делать: выставить полный набор таймаутов (DialContext, TLSHandshakeTimeout, ResponseHeaderTimeout, общий http.Client.Timeout и/или дедлайн контекста), настроить транспорт, ввести bulkhead (отдельный ограниченный пул на этот интеграционный вызов, чтобы он не съел все ресурсы), circuit breaker, чтобы не долбить упавший сервис, и кеш/фолбэк на устаревшие данные. Почему очереди не панацея: они меняют контракт с синхронного на асинхронный, а значит клиенту нужен способ узнать результат (polling статуса, вебхук, WebSocket); задержка в хвостах растёт; появляется лаг, который надо мониторить; доставка at-least-once требует идемпотентности; отладка усложняется; и если внешний сервис — узкое место, очередь просто переносит очередь ожидания из памяти клиента в брокер, ничего не ускоряя, зато скрывая проблему до момента, когда лаг станет часами. Как убедиться, что запрос принят: синхронно — код 2xx (202 Accepted с Location/request_id для длительных операций) и явная проверка тела; в Kafka — только acks=all вместе с min.insync.replicas ≥ 2 даёт «записано и реплицировано», acks=1 теряет данные при падении лидера, acks=0 не гарантирует ничего; в RabbitMQ — publisher confirms плюс mandatory, иначе сообщение может тихо уйти в никуда при отсутствии биндинга. Как убедиться, что ответ — про вас: генерировать correlation_id/idempotency_key на клиенте, класть его в заголовок или в ключ сообщения, у RabbitMQ использовать reply_to + correlation_id, у Kafka — топик ответов и correlation_id в заголовках; на приёме сверять идентификатор, отбрасывать неизвестные и устаревшие ответы, валидировать схему и ключевые бизнес-поля (например, что order_id в ответе совпадает с запрошенным), а не доверять «пришло — значит наше».

С какими очередями работал?

Коротко. См. выше «Работал ли с очередями kafka, rabbit, nats?» — вопрос про личный опыт, отвечать конкретикой: брокер, нагрузка, гарантии, инцидент.

Глубже. Отличие в том, что здесь вопрос открытый и уместно показать понимание различий моделей: Kafka — распределённый лог с retention и реплеем, порядок в пределах партиции, консьюмер сам двигает офсет; RabbitMQ — брокер с маршрутизацией (exchange + routing key), сообщение удаляется после ack, есть per-message TTL, приоритеты и DLX; NATS Core — быстрый fire-and-forget pub/sub без хранения, NATS JetStream добавляет персистентность и стримы; SQS — управляемая очередь с visibility timeout и отдельным FIFO-режимом. Отдельно упомяните «очередь на базе БД» (таблица задач + SELECT ... FOR UPDATE SKIP LOCKED) — для небольших нагрузок это законное решение, и знание про SKIP LOCKED обычно ценится.

Если ты производишь навигацию по дереву, знаешь ли ты сколько у тебя элементов между левой и правой границей?

Коротко. В обычном BST — нет: чтобы посчитать элементы в диапазоне, придётся обойти его за O(k + log n). Чтобы узнать количество за O(log n) без обхода, дерево надо аугментировать — хранить в каждом узле размер поддерева; тогда это order-statistic tree и ответ равен rank(right) - rank(left).

Глубже. Размер поддерева обновляется при вставке и удалении по пути к корню и корректно пересчитывается при поворотах — это стандартная аугментация для AVL/RB. Функция rank(x) спускается от корня: уходя вправо, прибавляет size(left)+1. Тот же приём обобщается на любые аддитивные агрегаты (сумма, минимум), и на нём же основаны k-я порядковая статистика за O(log n). Если ключи целые и плотные, дешевле не дерево, а дерево Фенвика или дерево отрезков: префиксные суммы за O(log n) и намного лучше кэш-локальность. В B+-дереве количества «между границами» тоже нет — движок читает диапазон по связанным листьям, поэтому SELECT count(*) WHERE x BETWEEN a AND b в Postgres — это index range scan, линейный по числу найденных строк, а не мгновенная операция; отсюда же берутся приблизительные оценки планировщика из статистики.

Куда и в каком формате пишутся логи? Как организован их сбор и хранение?

Коротко. В контейнерном мире — структурированный JSON в stdout/stderr, по строке на событие; сбор — агентом на ноде (Fluent Bit, Vector, Promtail), который читает файлы CRI и отправляет в хранилище (Loki, Elasticsearch/OpenSearch, ClickHouse); хранение — с retention по классу логов и индексом по времени и меткам сервиса. В Go для этого с версии 1.21 есть log/slog со встроенным JSONHandler.

Глубже. Что должно быть в каждой записи: время в RFC3339 с UTC, уровень, сообщение, имя сервиса и версия, trace_id/span_id для связи с трейсами, идентификаторы запроса и пользователя (без ПДн и секретов), длительность операции. Приложение не должно ротировать файлы и знать про транспорт — за это отвечает платформа (12-factor); писать в файл имеет смысл только там, где нет агрегатора. Уровни: error только для того, что требует реакции, иначе алерты обесцениваются; отладку выносить под debug с динамическим переключением уровня. При больших объёмах включают сэмплирование повторяющихся сообщений и следят за стоимостью: логи в Elasticsearch с полнотекстовым индексом дороже, чем в Loki, где индексируются только метки. Полезно назвать разделение сигналов: логи — про факты и контекст, метрики — про агрегаты и алерты, трейсы — про причинно-следственную связь между сервисами; коррелируются они через trace_id (OpenTelemetry). И отдельный пункт для собеседования — чувствительные данные: пароли, токены, номера карт в логах недопустимы, для этого делают маскирование на уровне логгера.

logger := slog.New(slog.NewJSONHandler(os.Stdout, &slog.HandlerOptions{Level: slog.LevelInfo}))
logger.Info("order created", "order_id", 42, "user_id", 7, "took", time.Since(start))

Как бы вы реализовали простейший HTTP/GRPC-клиент к сервису? Какие ключевые моменты продумаете в первую очередь?

Коротко. Один переиспользуемый клиент на процесс (http.Client с настроенным Transport или один grpc.ClientConn), обязательный context с дедлайном в каждом методе, явные таймауты, ретраи с экспоненциальным backoff и джиттером только для идемпотентных операций, классификация ошибок (retryable/fatal), метрики и трассировка, типизированные ошибки в API клиента.

Глубже. Для HTTP: не использовать http.DefaultClient (у него нет таймаута), настроить Transport.MaxIdleConnsPerHost под ожидаемый параллелизм, всегда дочитывать и закрывать тело (io.Copy(io.Discard, resp.Body) перед Close), иначе соединение не вернётся в пул; отделять ошибки транспорта от 4xx/5xx; уважать Retry-After и не ретраить POST без ключа идемпотентности; ограничивать размер ответа (http.MaxBytesReader или io.LimitReader); передавать context в http.NewRequestWithContext. Для gRPC: grpc.NewClient (в новых версиях вместо устаревшего grpc.Dial) создаётся один раз и потокобезопасен, внутри — пул HTTP/2 соединений с балансировкой; дедлайн задаётся контекстом и распространяется на сервер; настраиваются keepalive-параметры, максимальный размер сообщения, TLS-креды; ретраи можно описать декларативно в service config, а сквозные вещи (логирование, метрики, авторизация) вешать интерцепторами. Общее для обоих: circuit breaker и лимит параллелизма, чтобы деградация внешнего сервиса не утащила ваш; конфигурация таймаутов снаружи, а не константами в коде; интерфейс клиента в терминах домена (GetUser(ctx, id) (User, error)), чтобы его можно было замокать в тестах, и тесты против httptest.Server или bufconn для gRPC.

Что такое хеш и чем отличается от хеш-функции?

Коротко. Хеш-функция — это алгоритм (отображение), а хеш — результат её применения к конкретным данным, число фиксированной длины (дайджест). Разница как между «функцией» и «значением функции».

Глубже. На практике словом «хеш» называют ещё и саму структуру (в Perl/Ruby «хеш» = ассоциативный массив), и хеш-сумму файла — стоит уточнить контекст, если вопрос звучит двусмысленно. Полезно добавить свойства, которые отличают хорошую хеш-функцию: детерминированность (одни и те же данные → один и тот же хеш в пределах запуска и семейства), равномерность распределения, лавинный эффект (изменение одного бита входа меняет примерно половину бит выхода), скорость для некриптографических и стойкость к прообразу/коллизиям для криптографических. Отдельно — что хеш не является уникальным идентификатором данных в математическом смысле: он лишь настолько «уникален», насколько мала вероятность коллизии для вашего объёма (парадокс дней рождения: для 64-битного хеша коллизия становится вероятной уже на масштабе миллиардов значений).

Назови все структуры данных, которые ты знаешь/

Коротко. Линейные: массив, динамический массив (срез), связный список (одно- и двусвязный), стек, очередь, дека, кольцевой буфер. Ассоциативные: хеш-таблица, множество, упорядоченная мапа на дереве. Иерархические: деревья (BST, AVL, RB, B+, trie, куча), графы. Вероятностные и специальные: Bloom filter, HyperLogLog, count-min sketch, skip-list, union-find, LSM-дерево, суффиксный массив.

Глубже. Перечисление само по себе слабый ответ — сильный кандидат сразу привязывает структуру к операциям и стоимости. Например: массив — O(1) доступ по индексу, O(n) вставка в середину, идеальная кэш-локальность; связный список — O(1) вставка/удаление при известном узле, O(n) поиск, плохой для кеша процессора, поэтому на практике проигрывает срезу даже там, где «по асимптотике» должен выигрывать; хеш-таблица — O(1) в среднем, нет порядка, худший случай O(n); сбалансированное дерево — O(log n) и есть порядок с диапазонными запросами; куча — O(1) минимум, O(log n) вставка/извлечение; union-find — почти O(1) амортизированно на объединение и проверку связности; Bloom filter — константная память и односторонняя ошибка (может сказать «есть», когда нет, но никогда наоборот), нужен как дешёвый фильтр перед дорогим обращением к диску (так делают LSM-хранилища).

Как найти середину односвязного списка?

Коротко. Два указателя: slow двигается на шаг, fast — на два; когда fast дошёл до конца, slow стоит в середине. Один проход, O(n) времени и O(1) памяти.

Глубже. Вариант с подсчётом длины за первый проход и повторным проходом на n/2 тоже корректен и иногда даже быстрее по константе, но интервьюер обычно ждёт именно «зайца и черепаху», потому что тот же приём решает поиск цикла (алгоритм Флойда) и k-й элемент с конца. Внимание к чётности: с условием цикла fast != nil && fast.Next != nil при чётной длине возвращается второй из двух средних (для 1→2→3→4 вернётся 3); если нужен первый, условие меняется на fast.Next != nil && fast.Next.Next != nil. Уточните это вслух — на собеседовании ценится, когда кандидат сам называет граничный случай.

type Node struct {
  Val  int
  Next *Node
}

func middle(head *Node) *Node {
  slow, fast := head, head
  for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
  }
  return slow // при чётной длине — второй из двух средних
}

указать как еще можно реализовать эту очередь (на основе каких объектов);

Коротко. FIFO-очередь можно построить на срезе (амортизированный O(1) с головным индексом), на кольцевом буфере фиксированного размера, на связном списке (container/list или свои узлы), на двух стеках (амортизированное O(1) на операцию), на канале (если нужна конкурентность и блокировка) и на куче — если очередь с приоритетом.

Глубже. Разбор компромиссов и есть содержание ответа. Срез: q = append(q, v) и v, q = q[0], q[1:] — просто, но при таком сдвиге головы нижележащий массив не освобождается и растёт бесконечно, поэтому нужен либо периодический copy в начало, либо кольцевой буфер. Кольцевой буфер: два индекса по модулю ёмкости, отличная кэш-локальность, но нужен явный рост при переполнении; в стандартной библиотеке есть container/ring, но это кольцевой список, а не буфер. Связный список: O(1) без реаллокаций и без амортизации, но аллокация на каждый элемент и указатели гуляют по памяти. Два стека (in и out): элегантный трюк для собеседований — перекладываем из in в out, только когда out пуст; амортизированно O(1), каждый элемент перекладывается ровно раз. Канал: единственный вариант «из коробки» потокобезопасный и с блокировкой на пустой/полной очереди, но фиксированной ёмкости, без просмотра содержимого и без удаления из середины. Для конкурентной очереди без блокировок — Michael–Scott queue на CAS (в Go придётся писать руками через sync/atomic), а в рантайме подобная структура уже есть внутри sync.Pool (poolChain).

Данный код будет работать в сервисе, читающим входные сообщения из очереди сообщений (Kafka или подобное), и записывающем результат также в очередь. Если Process возвращает Null - то в очередь ничего не пишется.

Коротко. Это условие задачи на код-ревью/реализацию: консьюмер читает сообщение, вызывает Process, и при nil-результате просто пропускает публикацию. Ключевые моменты, которые проверяются, — порядок «обработать → опубликовать → закоммитить офсет», идемпотентность, обработка ошибок отдельно от «пустого результата» и что делать с ядовитыми сообщениями.

Глубже. Правильный порядок операций: обработали, успешно опубликовали результат (с подтверждением от брокера), и только потом коммитим офсет. Автокоммит по таймеру ломает это: при падении между коммитом и публикацией сообщение теряется. Обратный порядок даёт at-least-once — то есть возможны дубли, поэтому потребитель вашего выходного топика должен быть идемпотентен, а ключ сообщения стоит выводить детерминированно из входного (key = input.ID), чтобы дубль перезаписал сам себя при компакции. nil от Process обязательно надо отличать от ошибки: «результата нет, это нормально» — пропускаем и коммитим; «обработать не удалось» — ретраим с backoff, а после N попыток отправляем в retry-топик или DLQ вместе с причиной, иначе один битый месседж заблокирует партицию навсегда. Ещё вещи, за которые дают баллы: не делать panic на плохом payload, а логировать с offset/partition; уважать context при shutdown (дообработать текущее сообщение, закоммитить, закрыть продюсер с flush); следить, чтобы обработка не превышала max.poll.interval.ms, иначе будет вечный ребаланс; учитывать, что порядок гарантирован только внутри партиции, поэтому параллелить обработку можно по партициям или по ключу, но не как попало.

Как устроен контекст внутри? (связный список с мьютексом)

Коротко. context.Context — интерфейс, а конкретные реализации образуют дерево, связанное указателями на родителя. valueCtx — это именно связный список: каждый WithValue добавляет один узел с парой ключ/значение, и Value() идёт вверх по цепочке за O(глубины). cancelCtx содержит мьютекс, канал done, ошибку и множество детей, чтобы отмена родителя рекурсивно отменила потомков.

Глубже. Формулировка вопроса неточна в одной детали, и это стоит поправить вслух: у cancelCtx дети хранятся в children map[canceler]struct{}, а не в списке; связный список — это цепочка родителей (и, в частности, цепочка valueCtx). Структура: backgroundCtx/todoCtx поверх emptyCtx — синглтоны, у которых Done() возвращает nil, а Err() — nil; cancelCtx{Context; mu sync.Mutex; done atomic.Value (chan struct{}); children map[canceler]struct{}; err error} — канал создаётся лениво при первом Done(); timerCtx встраивает cancelCtx и добавляет timer *time.Timer и deadline; withoutCancelCtx (Go 1.21) обрывает распространение отмены, сохраняя значения. WithCancel вызывает propagateCancel, который ищет ближайшего отменяемого предка и регистрируется у него; если предок — чужая пользовательская реализация Context, рантайм не может встроиться в его children и запускает отдельную горутину, следящую за его Done() — это одна из причин не писать свои реализации интерфейса без нужды. cancel() закрывает done, ставит err (context.Canceled или DeadlineExceeded), рекурсивно отменяет детей и отцепляется от родителя, чтобы не течь. Практические следствия: Value линеен по глубине и не предназначен для передачи параметров функций (только для request-scoped данных вроде trace_id); ключи должны быть неэкспортируемого типа, чтобы не было коллизий между пакетами; вызывать cancel нужно всегда (defer cancel()), иначе узел останется в children родителя и таймер не освободится. Свежие добавления: WithCancelCause/Cause (Go 1.20), WithoutCancel, AfterFunc, WithDeadlineCause (Go 1.21).

Как бы реализовал LRU cache?

Коротко. См. выше «Рассказать, как устроен LRU cache»: map[K]*list.Element для поиска за O(1) плюс двусвязный список для порядка, вытеснение с хвоста при превышении ёмкости.

Глубже. Отличие этой формулировки в том, что ждут план реализации, а не описание. Проговорите по шагам: определить интерфейс (Get(key) (V, bool), Put(key, value), опционально Remove, Len, коллбэк onEvict), выбрать хранилище порядка (container/list или свои узлы, если хочется избежать interface{}-боксинга и лишней аллокации), решить про конкурентность (мьютекс на кеш или шардирование), решить про ёмкость (по числу элементов или по суммарному «весу» в байтах), покрыть тестами граничные случаи — ёмкость 0 или 1, повторный Put того же ключа, Get отсутствующего, порядок вытеснения после серии обращений. Если разрешают библиотеки, честно назовите github.com/hashicorp/golang-lru/v2 — он дженериковый и умеет 2Q/ARC.

В какой очередности выполняется defer ?

Коротко. LIFO — последний отложенный вызов выполняется первым. Аргументы defer вычисляются в момент постановки, а не в момент вызова; отложенные функции выполняются при выходе из функции, в том числе при панике.

Глубже. Отложенные вызовы кладутся в стек, привязанный к фрейму функции (_defer-записи); с Go 1.14 работает open-coded defer — компилятор в простых случаях вообще не создаёт запись, а вставляет вызовы в эпилог по битовой маске, из-за чего накладные расходы стали почти нулевыми (~1 нс), и старый совет «не ставьте defer в цикле ради производительности» сегодня относится в первую очередь не к скорости, а к тому, что defer в цикле копится до конца функции, а не итерации, и ресурсы не освобождаются вовремя. Классическое следствие LIFO — порядок освобождения ресурсов, обратный порядку захвата, что и требуется для вложенных блокировок и открытых файлов. Отдельно про defer и именованные результаты: только именованный результат можно изменить в отложенной функции (func f() (err error) { defer func(){ if r := recover(); r != nil { err = ... } }(); ... }) — это стандартный приём восстановления после паники. И про вычисление аргументов: defer fmt.Println(i) напечатает значение i на момент постановки, а defer func(){ fmt.Println(i) }() — на момент выполнения.

func demo() {
  for i := 0; i < 3; i++ {
    defer fmt.Println("defer", i)
  }
  fmt.Println("body")
}
// body
// defer 2
// defer 1
// defer 0

Что такое хеширование?

Коротко. Хеширование — процесс преобразования данных произвольного размера в значение фиксированной длины с помощью хеш-функции. Применяется для быстрого поиска (хеш-таблицы), проверки целостности (контрольные суммы), распределения нагрузки (шардирование, консистентное хеширование) и криптографии (подписи, хранение паролей).

Глубже. У процесса три свойства, которые надо назвать: детерминированность, фиксированная длина результата и необратимость. Из фиксированной длины неизбежно следует существование коллизий, поэтому любая система, использующая хеширование, обязана иметь план на коллизию: в хеш-таблице — цепочки или пробирование, в дедупликации файлов — сверка содержимого при совпадении хеша (или заведомо стойкая функция, где вероятность коллизии пренебрежима), в криптографии — выбор функции, для которой поиск коллизии вычислительно невозможен. Смежные термины, которые полезно развести: соль (уникальное значение на запись, защищает от радужных таблиц), перец (общий секрет), HMAC (хеш с ключом для аутентификации сообщений), консистентное хеширование (минимизация переезда ключей при изменении числа узлов), локально-чувствительное хеширование (LSH — наоборот, похожие входы дают похожие хеши, применяется для поиска дубликатов и ближайших соседей).

Типы маршрутов. Система должна поддерживать разные типы маршрутов с различной логикой планирования и исполнения: Магистральная перевозка: Доставка между двумя крупными узлами (городами). Пример: склад → распределительный центр. Первая миля: Несколько точек погрузки → одна точка разгрузки (сбор товаров у поставщиков). Последняя миля: Одна точка погрузки → несколько точек разгрузки (доставка клиентам). Смешанный тип (курьерское/такси-подобное): Несколько точек погрузки и разгрузки, возможна гибкая маршрутизация на лету.

Коротко. Это задача на проектирование. Общая модель одна: маршрут — упорядоченный список остановок (Stop{type: pickup|dropoff, location, timeWindow, cargo}) плюс рейсы между ними; типы маршрутов отличаются не структурой данных, а стратегией планирования, поэтому в коде это одна модель Route и разные реализации интерфейса Planner (стратегия), выбираемые по типу маршрута.

Глубже. Модель данных: Route{ID, Type, VehicleID, Stops []Stop, Status, PlannedAt, Version}, где Stop хранит геоточку, временное окно, объём/вес груза и ссылки на заказы; исполнение — конечный автомат (planned → assigned → in_progress → completed | cancelled) с событиями от водителя, а изменения фиксируются как события, чтобы поддержать перепланирование и аудит. Алгоритмическая часть по типам: магистраль — это кратчайший путь на графе дорог (Dijkstra/A* с кучей, на практике — внешний routing engine типа OSRM/Valhalla, плюс расписание и загрузка транспорта); первая миля (много pickup → один dropoff) и последняя миля (один pickup → много dropoff) — это варианты VRP, обычно решаемые эвристиками (Clarke-Wright savings для начального решения, затем локальный поиск 2-opt/Or-opt, или готовый OR-Tools) с ограничениями по вместимости (CVRP) и временным окнам (VRPTW); смешанный тип — pickup and delivery problem с ограничением предшествования (pickup всегда раньше своего dropoff) и динамическим перепланированием: это уже онлайн-задача, где нужен матчинг новых заказов к активным маршрутам с оценкой «стоимости вставки» и лимитом на ухудшение уже обещанных ETA. Структуры данных, которые тут реально нужны: граф дорог (списки смежности + приоритетная очередь), матрица расстояний/времён с кешем (её вычисление — самая дорогая часть, кешируется по паре геохешей), пространственный индекс для поиска ближайших исполнителей (R-tree, geohash, H3), очередь событий для перепланирования. Что важно проговорить архитектурно: единый интерфейс Planner.Plan(ctx, demand) (Route, error) и Executor со своим набором правил валидации на тип; изоляция долгой оптимизации от онлайн-API (планирование — асинхронная задача через очередь, API отдаёт 202 и route_id); идемпотентность перепланирования по версии маршрута (оптимистическая блокировка), иначе два одновременных пересчёта затрут друг друга; и разделение «плана» и «факта» — по факту водитель поедет иначе, и система должна уметь сравнивать.

Что такое lock-frее структуры данных, и есть ли в Go такие?

Коротко. Lock-free — структуры, где прогресс системы гарантирован без блокировок: потоки синхронизируются атомарными операциями (CAS), и остановка одного потока не блокирует остальных. В Go нет готовых lock-free контейнеров в публичном API, но есть весь инструментарий (sync/atomic, включая типизированные atomic.Int64, atomic.Pointer[T] с Go 1.19), а внутри рантайма и стандартной библиотеки lock-free-техники используются — например, в sync.Pool и в fast path у sync.Map.

Глубже. Терминология, которую стоит различать: wait-free (каждый поток завершает операцию за конечное число шагов), lock-free (хотя бы один поток прогрессирует — обычная цель), obstruction-free (прогресс при отсутствии конкуренции). Строятся такие структуры на CompareAndSwap в цикле: читаем состояние, вычисляем новое, пытаемся заменить, при неудаче повторяем. Классика — стек Трайбера и очередь Michael–Scott. Главная сложность в языках с ручным управлением памятью — безопасное освобождение (проблема ABA и «когда можно удалить узел, который кто-то читает»), для чего нужны hazard pointers или epoch-based reclamation; в Go это во многом снимается сборщиком мусора: пока на узел есть ссылка, память не переиспользуется, поэтому классическое ABA по адресу маловероятно, хотя логическое ABA по значению остаётся. Что есть в Go: sync/atomic (CompareAndSwap, Add, Swap, Load, Store, atomic.Value), sync.Once с атомарным fast path, sync.Map, у которой чтение из read-only части идёт без мьютекса, sync.Pool с per-P локальными структурами и lock-free poolChain, а также сам планировщик с work-stealing на атомарных операциях. Чего нет: каналы не lock-free — внутри hchan обычный мьютекс. Практический совет, который хорошо звучит на интервью: lock-free почти всегда сложнее и не всегда быстрее — под низкой конкуренцией sync.Mutex в Go дёшев (fast path — тот же CAS), выигрыш появляется на высокой конкуренции и коротких критических секциях, а корректность CAS-алгоритма без формальной проверки и гоночных тестов (-race, стресс) доказать тяжело.

Как вы реализуете LRU cache на Go?

Коротко. map[K]*list.Element плюс container/list: Get делает MoveToFront, Put — PushFront и при переполнении удаляет Back(), попутно убирая ключ из мапы. Обе операции — O(1).

Глубже. Ниже минимальная дженериковая реализация. Заметьте два места, где обычно ошибаются: в узле хранится сам ключ (без него не удалить запись из мапы при вытеснении), и при повторном Put существующего ключа нужно обновить значение и переместить узел, а не вставлять дубликат. Для потокобезопасности достаточно обернуть оба метода одним sync.Mutex — RWMutex бесполезен, потому что Get тоже мутирует список.

package lru

import "container/list"

type entry[K comparable, V any] struct {
  key   K
  value V
}

type Cache[K comparable, V any] struct {
  capacity int
  ll       *list.List
  items    map[K]*list.Element
}

func New[K comparable, V any](capacity int) *Cache[K, V] {
  if capacity <= 0 {
    panic("lru: capacity must be positive")
  }
  return &Cache[K, V]{
    capacity: capacity,
    ll:       list.New(),
    items:    make(map[K]*list.Element, capacity),
  }
}

func (c *Cache[K, V]) Get(key K) (V, bool) {
  if el, ok := c.items[key]; ok {
    c.ll.MoveToFront(el)
    return el.Value.(*entry[K, V]).value, true
  }
  var zero V
  return zero, false
}

func (c *Cache[K, V]) Put(key K, value V) {
  if el, ok := c.items[key]; ok {
    el.Value.(*entry[K, V]).value = value
    c.ll.MoveToFront(el)
    return
  }
  el := c.ll.PushFront(&entry[K, V]{key: key, value: value})
  c.items[key] = el
  if c.ll.Len() > c.capacity {
    if oldest := c.ll.Back(); oldest != nil {
      c.ll.Remove(oldest)
      delete(c.items, oldest.Value.(*entry[K, V]).key)
    }
  }
}

func (c *Cache[K, V]) Len() int { return c.ll.Len() }

дерево где в каждом узле буква, нужно вернуть 2 вершины у которых в листьях одинаковый набор уникальных букв;

Коротко. Одним DFS считаем для каждой вершины множество уникальных букв её листьев (для латиницы — 26-битная маска), складываем маски в map[маска][]вершина и возвращаем любую пару из группы с двумя и более элементами. Время O(n) при масках или O(n·A) при множествах, где A — размер алфавита.

Глубже. Маска вершины = побитовое ИЛИ масок детей; у листа — бит его собственной буквы. Важная деталь условия, которую надо уточнить у интервьюера: учитываются буквы листьев поддерева, а не всех узлов — во внутренних узлах буквы есть, но в набор они не входят (иначе формула та же, только лист инициализируется своей буквой, а внутренний узел добавляет свою). Если алфавит произвольный (юникод), вместо маски берут отсортированную строку уникальных символов или её хеш — тогда стоит помнить о коллизиях и при совпадении хешей сверять множества. Если нужно вернуть все такие пары, а не одну, ответ — все пары внутри каждой группы, и их может быть O(n²), поэтому обычно просят именно две вершины или количество групп.

type TreeNode struct {
  Letter   byte // 'a'..'z'
  Children []*TreeNode
}

// возвращает две вершины с одинаковым набором букв в листьях, либо nil, nil
func findSamePair(root *TreeNode) (*TreeNode, *TreeNode) {
  groups := make(map[uint32]*TreeNode)
  var a, b *TreeNode

  var dfs func(n *TreeNode) uint32
  dfs = func(n *TreeNode) uint32 {
    if n == nil {
      return 0
    }
    var mask uint32
    if len(n.Children) == 0 {
      mask = 1 << uint(n.Letter-'a')
    } else {
      for _, ch := range n.Children {
        mask |= dfs(ch)
      }
    }
    if a == nil {
      if prev, ok := groups[mask]; ok {
        a, b = prev, n
      } else {
        groups[mask] = n
      }
    }
    return mask
  }
  dfs(root)
  return a, b
}

Префикс длины 1: {1} и {5} → общих чисел нет → 0 ;

Коротко. Это разбор примера к задаче «prefix common array»: на каждом шаге i берём префиксы обоих массивов длины i+1 и считаем размер пересечения их множеств значений. На первом шаге множества {1} и {5} не пересекаются, ответ 0.

Глубже. Ключ к эффективному решению — считать пересечение инкрементально, а не пересчитывать множества заново: поддерживаем два множества и счётчик common, и при добавлении нового элемента в одно множество увеличиваем счётчик, если он уже присутствует в другом. Это O(n) вместо наивного O(n²).

Префикс длины 2: {1, 1} (уникальные {1} ) и {5, 1} (уникальные {5, 1} ) → общее число 1 → 1 ;

Коротко. Второй шаг того же примера: в первом массиве добавилась повторная 1 (множество не изменилось), во втором появилась 1, которая уже есть в первом множестве, — значит common увеличивается на 1, ответ 1.

Глубже. Обратите внимание: пример содержит дубликаты ({1, 1}), то есть это обобщение канонической LeetCode-задачи, где оба массива — перестановки 1..n. Из-за дубликатов нельзя считать «сколько раз значение встретилось всего» — нужно именно множество уникальных, поэтому счётчик инкрементируется только при первом появлении значения в своём массиве.

Префикс длины 3: {1, 1, 5} (уникальные {1, 5} ) и {5, 1, 7} (уникальные {5, 1, 7} ) → общие {1, 5} → 2 ;

Коротко. Третий шаг: в первом множестве появилась 5, которая уже есть во втором, — common становится 2. Итоговый ответ для примера — [0, 1, 2].

Глубже. Реализация обобщённого варианта (с дубликатами) на двух множествах и счётчике:

func prefixCommon(a, b []int) []int {
  n := len(a)
  inA := make(map[int]struct{}, n)
  inB := make(map[int]struct{}, n)
  res := make([]int, n)
  common := 0
  for i := 0; i < n; i++ {
    if _, ok := inA[a[i]]; !ok {
      inA[a[i]] = struct{}{}
      if _, ok := inB[a[i]]; ok {
        common++
      }
    }
    if _, ok := inB[b[i]]; !ok {
      inB[b[i]] = struct{}{}
      if _, ok := inA[b[i]]; ok {
        common++
      }
    }
    res[i] = common
  }
  return res
}

Сложность O(n) по времени и памяти. Проверка на примере: prefixCommon([]int{1,1,5}, []int{5,1,7}) вернёт [0 1 2].

LeetCode 2657. Find the Prefix Common Array of Two Arrays

Коротко. Каноническая версия задачи: a и b — перестановки чисел 1..n, надо для каждого префикса вернуть количество общих чисел. Решение — два битовых множества и popcount их пересечения на каждом шаге; O(n) времени, O(1) дополнительной памяти при n ≤ 64.

Глубже. Раз это перестановки, дубликатов нет, и можно обойтись счётчиком встреч: элемент становится «общим» ровно в тот момент, когда встретился второй раз суммарно по обоим массивам. Оба решения ниже эквивалентны; битовое короче и демонстрирует знание math/bits. Ограничение задачи n ≤ 50 позволяет уложить множество в один uint64; для больших n берут []uint64 или счётчики.

import "math/bits"

func findThePrefixCommonArray(a, b []int) []int {
  var maskA, maskB uint64
  res := make([]int, len(a))
  for i := range a {
    maskA |= 1 << uint(a[i])
    maskB |= 1 << uint(b[i])
    res[i] = bits.OnesCount64(maskA & maskB)
  }
  return res
}

// вариант со счётчиками, работает при любом n
func findThePrefixCommonArrayCount(a, b []int) []int {
  n := len(a)
  seen := make([]int8, n+1)
  res := make([]int, n)
  common := 0
  for i := 0; i < n; i++ {
    if seen[a[i]]++; seen[a[i]] == 2 {
      common++
    }
    if seen[b[i]]++; seen[b[i]] == 2 {
      common++
    }
    res[i] = common
  }
  return res
}

Какие существуют структуры данных в Go?

Коротко. Встроенные в язык: массив, срез, строка, map, канал, структура, указатель, функция, интерфейс. В стандартной библиотеке: container/list (двусвязный список), container/heap (куча/приоритетная очередь), container/ring (кольцевой список), sync.Map, sync.Pool, bytes.Buffer, strings.Builder, big.Int как битовое множество, плюс пакеты-утилиты slices и maps (Go 1.21+).

Глубже. Стоит показать, что вы знаете внутренности встроенных типов, а не только имена. Срез — заголовок из трёх слов (ptr, len, cap), передаётся по значению, но указывает на общий массив, поэтому append может как переиспользовать массив, так и выделить новый (правило роста менялось: с Go 1.18 порог плавно снижается с двукратного, а не резко на 1024). Строка — ptr, len, иммутабельна, конверсия в []byte копирует (кроме оптимизируемых компилятором случаев). map — хеш-таблица, с Go 1.24 на Swiss Tables. Канал — hchan с кольцевым буфером, мьютексом и очередями ожидания. Интерфейс — пара (type, data), nil-интерфейс не равен интерфейсу с nil-значением внутри (классическая ловушка с возвратом *MyError). Отдельно: в Go нет встроенного set — его делают как map[T]struct{}; нет сбалансированных деревьев и нет очереди/стека как отдельных типов, их пишут на срезах. Дженерики (Go 1.18+) позволили наконец писать типобезопасные контейнеры, а slices/maps покрыли типовые операции (slices.Sort, slices.BinarySearch, maps.Keys — с Go 1.23 возвращает итератор).

В чем недостаток обычного бинарного дерева?

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

Глубже. Отсортированные вставки — не экзотика, а типичный случай (id по возрастанию, временные метки), поэтому проблема практическая, а не теоретическая. Лечится балансировкой: AVL держит разницу высот поддеревьев не больше 1 (быстрее поиск, больше поворотов при модификации), красно-чёрное даёт более слабую гарантию высоты ≤ 2log(n+1), но дешевле обновления, treap балансируется вероятностно случайными приоритетами, splay — амортизированно, перемещая обращённый элемент в корень. Второй недостаток — накладные расходы памяти: два указателя (и, возможно, цвет/высота) на каждый ключ, а данные разбросаны по куче, из-за чего каждый спуск по дереву стоит промах кеша; поэтому на дисках используют B-деревья (один узел = одна страница = сотни ключей), а в памяти при статичных данных часто выигрывает обычный отсортированный массив с бинарным поиском. Третий, менее очевидный, — операции с диапазонами и порядковыми статистиками требуют аугментации (см. вопрос про количество элементов между границами).

Что такое очередь с приоритетами? Какими структурами данных можно реализовать очередь с приоритетом? Каким способом лучше?

Коротко. Это очередь, из которой извлекается не самый ранний, а самый приоритетный элемент. Реализовать можно бинарной кучей, сортированным массивом или списком, сбалансированным деревом, skip-list, а для узкого диапазона приоритетов — bucket queue. По умолчанию лучше бинарная куча: O(log n) на вставку и извлечение, O(1) на просмотр, всё в одном массиве без указателей.

Глубже. Сравнение по стоимости: неотсортированный массив — O(1) вставка, O(n) извлечение; отсортированный массив — O(n) вставка, O(1) извлечение; бинарная куча — O(log n)/O(log n), лучший баланс и минимальные константы; биномиальная и фибоначчиева кучи — O(1) амортизированно на decrease-key, что теоретически ускоряет Dijkstra, но на практике константы и промахи кеша съедают выигрыш; сбалансированное дерево — те же O(log n), но даёт ещё и порядок/итерацию, нужно, если требуется удалять произвольные элементы; bucket queue или calendar queue — O(1), если приоритетов мало и они целые (планировщики ОС). Отдельные требования, которые меняют выбор: нужна ли стабильность (при равных приоритетах — FIFO; добавляют счётчик вставки как вторичный ключ), нужно ли менять приоритет уже добавленного элемента (тогда нужен индекс элемент → позиция и heap.Fix), нужна ли потокобезопасность (куча + мьютекс, либо канал как «очередь без приоритетов» не подойдёт — в каналах приоритетов нет). В Go — container/heap:

package pq

import "container/heap"

type Item struct {
  Value    string
  Priority int
  index    int
}

type PQ []*Item

func (pq PQ) Len() int           { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].Priority < pq[j].Priority } // min-heap
func (pq PQ) Swap(i, j int) {
  pq[i], pq[j] = pq[j], pq[i]
  pq[i].index, pq[j].index = i, j
}

func (pq *PQ) Push(x any) {
  it := x.(*Item)
  it.index = len(*pq)
  *pq = append(*pq, it)
}

func (pq *PQ) Pop() any {
  old := *pq
  n := len(old)
  it := old[n-1]
  old[n-1] = nil
  *pq = old[:n-1]
  return it
}

func Demo() *Item {
  pq := &PQ{}
  heap.Init(pq)
  heap.Push(pq, &Item{Value: "b", Priority: 2})
  heap.Push(pq, &Item{Value: "a", Priority: 1})
  return heap.Pop(pq).(*Item) // {a, 1}
}

Напишите код для слияния двух каналов в третий канал. Слияние должно быть поочередным;

Коротко. Читаем строго по очереди — сначала из a, потом из b, — и как только один канал закрылся, заменяем его переменную на nil (чтение из nil-канала блокируется вечно, поэтому в select такая ветка выключается) и дочитываем оставшийся. Выходной канал закрывает единственная пишущая горутина через defer close(out).

Глубже. Ключевое отличие «поочерёдного» слияния от обычного fan-in: обычный fan-in делают двумя горутинами и sync.WaitGroup, и порядок там произвольный; здесь же нужна строгая альтернация, значит писать должна одна горутина, поочерёдно вычитывающая источники. Цена строгости — если один канал молчит, слияние стоит, даже когда во втором данные готовы: это принципиальное свойство требования, и его стоит проговорить вслух. Обязательно обрабатываем ok при чтении: без этого закрытый канал будет бесконечно отдавать нулевые значения. Ниже вариант с явным чтением (строгая очерёдность) и вариант на select (справедливое, но не строго поочерёдное слияние) — на собеседовании полезно показать оба и объяснить разницу.

// строго поочерёдно: a, b, a, b, ...; после закрытия одного — дочитывает второй
func mergeAlternate(a, b <-chan int) <-chan int {
  out := make(chan int)
  go func() {
    defer close(out)
    for a != nil || b != nil {
      if a != nil {
        if v, ok := <-a; ok {
          out <- v
        } else {
          a = nil
        }
      }
      if b != nil {
        if v, ok := <-b; ok {
          out <- v
        } else {
          b = nil
        }
      }
    }
  }()
  return out
}

// обычный fan-in: порядок произвольный, зато нет взаимного ожидания
func merge(a, b <-chan int) <-chan int {
  out := make(chan int)
  go func() {
    defer close(out)
    for a != nil || b != nil {
      select {
      case v, ok := <-a:
        if !ok {
          a = nil
          continue
        }
        out <- v
      case v, ok := <-b:
        if !ok {
          b = nil
          continue
        }
        out <- v
      }
    }
  }()
  return out
}

Частые ошибки на собесе

• Говорят, что хеш-таблица даёт O(1) всегда, и не могут назвать худший случай O(n), load factor и стоимость рехеша; не знают, что Go солит хеш случайным seed и что с Go 1.24 мапа построена на Swiss Tables.
• Путают хеширование с шифрованием и уверяют, что «хеш можно расшифровать при наличии ключа»; или наоборот, считают, что хеш от короткого пароля восстановить нельзя — забывая про перебор и радужные таблицы.
• Реализуют LRU на односвязном списке или без хранения ключа в узле — и не могут удалить запись из мапы при вытеснении, теряя обещанное O(1).
• Считают, что для LRU достаточно sync.RWMutex, не замечая, что Get мутирует порядок и потому тоже требует эксклюзивной блокировки.
• Называют B-дерево «просто сбалансированным деревом» и не объясняют главного: узел равен странице диска, поэтому метрика — количество чтений страниц, а не сравнений; заодно не различают B-tree и B+-tree с связанными листьями.
• Утверждают, что в обычном BST можно за O(log n) узнать число элементов в диапазоне — без аугментации размерами поддеревьев это неверно.
• Обещают exactly-once в Kafka «из коробки», не оговаривая, что на практике это at-least-once плюс идемпотентный потребитель, и коммитят офсет до публикации результата.
• Считают канал lock-free структурой: внутри hchan обычный мьютекс. И называют небуферизованный канал очередью, хотя это синхронное рандеву без буфера.
• Говорят, что select при нескольких готовых каналах выбирает первый по порядку или самый старый — выбор псевдослучайный.
• Забывают, что аргументы defer вычисляются в момент постановки, и что отложенные вызовы в цикле выполнятся только при выходе из функции, а не итерации.

Что почитать

• Спецификация Go: типы map, срезы, каналы и порядок вычисления — https://go.dev/ref/spec
• Исходники новой реализации мапы (Swiss Tables) с подробным вступительным комментарием — https://go.dev/src/internal/runtime/maps/map.go
• Исходники каналов (hchan, sendq/recvq, прямая передача) — https://go.dev/src/runtime/chan.go
• Исходники context (valueCtx, cancelCtx, propagateCancel) — https://go.dev/src/context/context.go
• Документация container/heap с готовым примером очереди с приоритетом — https://pkg.go.dev/container/heap
• Documentation Kafka: гарантии доставки, acks, партиции и consumer group — https://kafka.apache.org/documentation/
• Мартин Клеппман, «Designing Data-Intensive Applications», главы 3 (B-tree и LSM) и 11 (потоки событий)
• Кормен и др., «Алгоритмы: построение и анализ», главы про хеш-таблицы, кучи, красно-чёрные и B-деревья
• Пакет log/slog — структурированное логирование в стандартной библиотеке — https://pkg.go.dev/log/slog

---

Список исходных вопросов с привязкой к компаниям: ../questions/data-structures.md