Сортировка и поиск

Кратко о теме

Сортировка на собеседовании почти никогда не про «напишите пузырёк». Спрашивают три вещи: понимаете ли вы, чем алгоритмы отличаются по сложности, памяти и устойчивости; знаете ли, что именно лежит под стандартной библиотекой вашего языка; умеете ли выбрать подход, когда данные не помещаются в память или приходят из БД. Базовая модель в голове: сравнительная сортировка не может быть быстрее Θ(n log n) в среднем и худшем случае (это доказывается через дерево решений: n! листьев требуют глубины не меньше log₂(n!) ≈ n log n), поэтому все «быстрые» алгоритмы — это разные компромиссы вокруг этой границы. Обойти её можно, только отказавшись от сравнений и начав использовать структуру самих ключей — так работают counting sort, radix sort и bucket sort.

В Go стандартная сортировка с версии 1.19 — это pdqsort (pattern-defeating quicksort): гибрид быстрой сортировки, сортировки вставками и пирамидальной сортировки, устойчивый к вырожденным входам. Она неустойчива (не сохраняет относительный порядок равных элементов) и работает in-place. Устойчивый вариант — sort.Stable / sort.SliceStable / slices.SortStableFunc — это блочная сортировка вставками плюс симметричное слияние без дополнительной памяти, за что платится множителем log: O(n log² n) в худшем случае. Дженерик-функции из пакета slices (Go 1.21+) предпочтительнее sort.Slice, потому что не гоняют перестановки через reflect.

Поиск — вторая половина темы, и на практике это выбор между тремя структурами. Хеш-таблица (map в Go) даёт O(1) в среднем, но не хранит порядок и не умеет диапазонные запросы. Отсортированный массив даёт O(log n) бинарным поиском (slices.BinarySearch, sort.Search), умеет диапазоны и «ближайший к x», но дорог на вставку. Сбалансированное дерево или B-дерево (индекс в БД) — компромисс: логарифм на всё, включая вставку, плюс упорядоченный обход, из-за чего ORDER BY в базе почти всегда пытается опереться на индекс, а не сортировать в памяти.

Отдельный класс задач — «данные больше памяти» и «слишком много результатов». Здесь работают внешняя сортировка слиянием (нарезать на порции, отсортировать каждую в RAM, слить k-путевым слиянием через кучу), top-k через кучу размера k вместо полной сортировки, и keyset-пагинация вместо OFFSET. Общий принцип один: не сортировать то, что можно не сортировать, и не читать то, что не понадобится.

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

Sorting algorithms? Practice. What algorithm does the sort function use? How does quicksort work?

Коротко. Начиная с Go 1.19 sort.Sort, sort.Slice и slices.Sort используют pdqsort — pattern-defeating quicksort: быстрая сортировка с медианным выбором опорного, переходом на сортировку вставками для коротких участков и на пирамидальную (heapsort) при слишком глубокой рекурсии. Сам quicksort работает так: выбираем опорный элемент (pivot), за один линейный проход переставляем элементы так, чтобы слева от него оказались не большие, справа — не меньшие, и рекурсивно сортируем обе части; в среднем O(n log n), в худшем O(n²), памяти O(log n) на стек.

Глубже. До Go 1.19 в sort был классический introsort: медиана из трёх (для больших массивов — «нинтер», медиана медиан девяти элементов), вставки при n ≤ 12, срыв в heapsort при глубине больше 2·⌊log₂ n⌋. Pdqsort (алгоритм Orson Peters, пришёл из Rust) добавил сверху эвристики против «плохих» паттернов: если разбиение получилось сильно несбалансированным, элементы частично перемешиваются, чтобы сломать вредный паттерн; если обнаружено много равных элементов — используется схема partition-equal, дающая O(n·k) на k различных значений; если участок почти отсортирован, partialInsertionSort дособирает его за линейное время и выходит. Итог: O(n log n) в худшем случае (за счёт heapsort-фолбэка), O(n) на уже отсортированных и обратно отсортированных данных, и никакой уязвимости к «quicksort killer» входам. Код лежит в сгенерированных файлах src/sort/zsortfunc.go и src/slices/zsortanyfunc.go (генератор — src/sort/gen_sort_variants.go).

Практический совет: используйте дженерики из slices, а не sort.Slice — последний перестраивает элементы через reflect.Swapper и заметно медленнее, а компаратор вызывается по индексам, а не по значениям.

package main

import (
  "cmp"
  "fmt"
  "slices"
)

type user struct {
  Name string
  Age  int
}

func main() {
  us := []user{{"bob", 30}, {"alice", 25}, {"bob", 20}}
  slices.SortFunc(us, func(a, b user) int {
    if c := cmp.Compare(a.Name, b.Name); c != 0 {
      return c
    }
    return cmp.Compare(a.Age, b.Age)
  })
  fmt.Println(us) // [{alice 25} {bob 20} {bob 30}]
}

В чем разница между устойчивой и неустойчивой сортировками?

Коротко. Устойчивая (stable) сортировка сохраняет относительный порядок элементов с равными ключами, неустойчивая — нет. Это важно при многоступенчатой сортировке: если сначала отсортировать по SKU, а потом устойчиво по имени пользователя, внутри одного имени сохранится порядок по SKU; с неустойчивой сортировкой такой трюк не работает.

Глубже. В Go неустойчивы sort.Sort, sort.Slice, slices.Sort, slices.SortFunc (pdqsort); устойчивы sort.Stable, sort.SliceStable, slices.SortStableFunc. Устойчивая версия реализована как сортировка вставками блоками по 20 элементов и последующее попарное слияние блоков алгоритмом symmerge (симметричное слияние с ротациями), поэтому она in-place, но стоит O(n log² n) сравнений и делает много перестановок — обычно в 2–3 раза медленнее обычной. Классические устойчивые алгоритмы: merge sort, insertion sort, counting/radix sort, Timsort. Классические неустойчивые: quicksort, heapsort, selection sort.

Когда устойчивость не нужна, а порядок всё равно должен быть детерминированным, добавьте tiebreaker в компаратор (например, сравнение по id) — это надёжнее, чем полагаться на устойчивость реализации. Отдельно: в базах данных ORDER BY не гарантирует устойчивости вообще, там всегда нужен полный набор ключей сортировки.

Как работает поиск элемента в мапе по ключу?

Коротко. map в Go — хеш-таблица. Ключ хешируется (с рандомизированным на старте процесса seed), младшие биты хеша выбирают бакет/группу, внутри группы сравниваются короткие «отпечатки» хеша, и только для совпавших отпечатков выполняется полное сравнение ключей. В среднем O(1), в патологическом случае (все ключи в один бакет) — O(n).

Глубже. До Go 1.23 включительно устройство было такое: hmap хранит массив бакетов размером 2^B, каждый бакет (bmap) держит 8 пар ключ/значение и массив tophash из 8 байт — старших битов хеша. Поиск: hash := alg.hash(key, seed), бакет hash & (2^B - 1), затем линейный проход по 8 слотам с быстрым отсевом по tophash, затем по цепочке overflow-бакетов. При коэффициенте загрузки выше 6.5 элементов на бакет мапа растёт вдвое, и переезд делается инкрементально: каждая операция записи эвакуирует один-два старых бакета, поэтому во время роста поиск смотрит и в старую, и в новую таблицу.

В Go 1.24 реализация мапы заменена на Swiss Tables (по мотивам Abseil): таблица состоит из групп по 8 слотов, к каждой группе прикреплено 64-битное control-слово — по байту на слот с 7-битным отпечатком хеша (h2) и маркерами пустого/удалённого слота. Проверка целой группы делается битовыми операциями над одним словом (SWAR), без цикла по слотам, что даёт меньше промахов кеша. Большие мапы разбиты на несколько независимых таблиц с директорией, чтобы рост оставался инкрементальным. Заметный практический эффект: ускорение поиска и итерации, снижение накладных расходов на память; семантика (в том числе рандомизированный порядок range) не изменилась.

Что стоит помнить: seed хеша случаен для каждой мапы, поэтому порядок обхода не воспроизводится и на него нельзя закладываться; ключом может быть только сравнимый тип, попытка использовать срез или мапу — ошибка компиляции, а интерфейс с несравнимым динамическим типом внутри даёт панику в рантайме; конкурентный доступ на чтение+запись ловится детектором и валит процесс с concurrent map writes. Если нужны диапазонные запросы или упорядоченность, мапа не подходит — берите отсортированный срез с slices.BinarySearch или дерево.

Алгоритмы сортировки.

Коротко. Сравнительные: insertion sort O(n²), но линейный на почти отсортированных данных и хорош на n ≤ 20; merge sort O(n log n) гарантированно, устойчив, требует O(n) памяти; quicksort O(n log n) в среднем и O(n²) в худшем, in-place, неустойчив; heapsort O(n log n) гарантированно, in-place, неустойчив, но с плохой локальностью; гибриды — introsort и pdqsort (Go, Rust), Timsort (Python, Java для объектов). Несравнительные: counting sort O(n + k), radix sort O(n·d), bucket sort O(n) в среднем на равномерных данных.

Глубже. Ключевая таблица, которую полезно держать в голове:

Алгоритм	Среднее	Худшее	Память	Устойчив	Когда применяют
Insertion	O(n²)	O(n²)	O(1)	да	n ≤ 20, почти отсортированные данные, «добивание» в гибридах
Merge	O(n log n)	O(n log n)	O(n)	да	нужна устойчивость и гарантия; внешняя сортировка; связные списки (там O(1) доп. памяти)
Quick	O(n log n)	O(n²)	O(log n)	нет	общий случай в памяти, отличная локальность
Heap	O(n log n)	O(n log n)	O(1)	нет	гарантия без лишней памяти, фолбэк в introsort/pdqsort, top-k
pdqsort	O(n log n)	O(n log n)	O(log n)	нет	стандарт в Go 1.19+ и Rust
Counting	O(n + k)	O(n + k)	O(k)	да	небольшой диапазон целых ключей (например, −10⁴…10⁴)
Radix (LSD)	O(n·d)	O(n·d)	O(n + k)	да	фиксированной длины ключи: int64, IP, строки одинаковой длины

Нижняя граница Θ(n log n) для сравнительных сортировок доказывается через дерево решений: у алгоритма n! возможных исходов, каждое сравнение даёт максимум один бит, значит нужно не меньше log₂(n!) = Θ(n log n) сравнений. Counting и radix её обходят, потому что читают биты ключа напрямую, а не сравнивают пары. Ещё две вещи, которые любят спрашивать: сортировка связного списка — это merge sort (нет произвольного доступа, зато слияние бесплатно по памяти), а сортировка на нескольких машинах — это sample sort / MapReduce-шаффл, то есть распределение по диапазонам с последующей локальной сортировкой.

Вывести уникальные комбинации пользователя и id товара для всех покупок, совершенных пользователями до того, как их забанили. Отсортировать сначала по имени пользователя, потом по SKU

Коротко. Соединить покупки с пользователями, отфильтровать по purchase.created_at < user.banned_at, снять дубликаты через DISTINCT (или GROUP BY) и отсортировать по двум ключам.

SELECT DISTINCT u.name AS user_name, p.sku
FROM purchases p
JOIN users u ON u.id = p.user_id
WHERE u.banned_at IS NOT NULL
  AND p.created_at < u.banned_at
ORDER BY u.name, p.sku;

Глубже. На собеседовании здесь ждут уточняющих вопросов, а не мгновенного SQL. Первое: нужны только забаненные пользователи или все (у незабаненных banned_at IS NULL, и условие p.created_at < u.banned_at их молча выкинет — если по смыслу нужны все покупки всех пользователей, пишите AND (u.banned_at IS NULL OR p.created_at < u.banned_at)). Второе: баны могут храниться отдельной таблицей bans(user_id, banned_at, unbanned_at) — тогда нужно решить, берём ли первый бан (min(banned_at)) или проверяем попадание покупки в неблокированный интервал; для «первого бана» удобно JOIN LATERAL/подзапрос с агрегатом. Третье: «уникальные комбинации» — по имени или по id пользователя? Тёзки склеятся, если группировать по имени; безопаснее DISTINCT u.id, u.name, p.sku, а в вывод отдавать имя.

Технические детали: при SELECT DISTINCT все выражения из ORDER BY обязаны присутствовать в списке выборки — иначе PostgreSQL выдаст ошибку for SELECT DISTINCT, ORDER BY expressions must appear in select list. Порядок строк по name зависит от collation базы (в C локали регистр учитывается, в en_US.UTF-8 — нет), это стоит проговорить. Для производительности полезен индекс purchases(user_id, created_at) INCLUDE (sku): он даёт index-only scan по нужному диапазону; сама же дедупликация выполнится как HashAggregate.

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

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

SELECT c.id, c.name AS city, count(u.id) AS users_cnt
FROM cities c
LEFT JOIN users u ON u.city_id = c.id
GROUP BY c.id, c.name
ORDER BY users_cnt ASC, c.name;

Глубже. Три момента, на которых валятся. Первый: LEFT JOIN плюс count(u.id), а не count(*) — иначе города без пользователей получат единицу вместо нуля, потому что count(*) считает строки, а count(expr) игнорирует NULL. Второй: в ORDER BY можно ссылаться на алиас из SELECT (PostgreSQL и MySQL это разрешают, поскольку ORDER BY логически выполняется последним), но в WHERE — нельзя; фильтр по агрегату идёт в HAVING. Третий: сортировка по не уникальному ключу недетерминирована — города с одинаковым количеством пользователей могут приходить в разном порядке между запусками, поэтому добавляют tiebreaker (c.name или c.id), особенно если сверху будет пагинация.

поменять сортировку так, чтоб строки с количеством не равным null остались в прежнем порядке, а строки с количеством равным null переместились в начало таблицы;

Коротко. В PostgreSQL достаточно явно задать размещение NULL: ORDER BY users_cnt ASC NULLS FIRST — по умолчанию для ASC действует NULLS LAST. В MySQL модификатора нет, там пишут дополнительный ключ-предикат: ORDER BY (users_cnt IS NOT NULL), users_cnt ASC.

Глубже. Логика в MySQL-варианте такая: булево выражение приводится к 0/1, у NULL-строк users_cnt IS NOT NULL = 0, значит при возрастании они уходят вперёд; остальные строки дальше упорядочиваются по самому users_cnt, то есть их взаимный порядок не меняется. Тот же приём работает в любой СУБД без NULLS FIRST/LAST, включая SQLite (хотя SQLite 3.30+ уже поддерживает NULLS FIRST). В MySQL по умолчанию, кстати, NULL при ASC и так идут первыми, а «проблема» возникает при DESC — там нужен ORDER BY (users_cnt IS NOT NULL), users_cnt DESC.

Важная оговорка про «остались в прежнем порядке»: сортировка в SQL не устойчива, и никакого «прежнего порядка» у набора строк не существует — он определяется только предыдущим ORDER BY. Поэтому корректная формулировка ответа: сохраняем те же ключи сортировки, что были, и добавляем к ним первым ключом признак NULL. Ещё нюанс для PostgreSQL: обычный B-tree индекс построен как ASC NULLS LAST, поэтому запрос с NULLS FIRST не сможет его использовать для упорядочивания и добавит явную сортировку; если это горячий путь, создают индекс с той же спецификацией — CREATE INDEX ... ON t (users_cnt ASC NULLS FIRST).

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

Коротко. Каркас хорошего ответа: назвать конкретный кейс (лента/поиск/выгрузка), сказать, что от OFFSET-пагинации отказались в пользу keyset-пагинации по индексу, что порядок сортировки всегда содержит уникальный tiebreaker, что глубина выдачи ограничена жёстким лимитом, а тяжёлые сортировки по неиндексируемым полям вынесены в специализированное хранилище (поисковый индекс или предпосчитанный рейтинг). Хорошо добавить цифру: было столько-то мс на 1000-й странице, стало столько-то.

Глубже. Технически стоит разложить на четыре приёма. Первый — keyset (cursor) pagination: вместо ORDER BY created_at DESC LIMIT 20 OFFSET 20000 пишем WHERE (created_at, id) < ($1, $2) ORDER BY created_at DESC, id DESC LIMIT 20, где $1,$2 — курсор с последней строки предыдущей страницы. OFFSET заставляет БД материализовать и выбросить N строк, то есть стоимость растёт линейно с глубиной; keyset делает один спуск по индексу и читает ровно 20 строк. Курсор кодируют в непрозрачную строку (base64 от кортежа ключей) — чтобы клиент не завязывался на формат, и обязательно включают в него все ключи сортировки, иначе на равных значениях страницы поедут.

Второй — top-k вместо полной сортировки: если нужно 100 лучших из миллиона, в приложении это куча размера k за O(n log k) (container/heap), а в PostgreSQL — план Limit над Sort с top-N heapsort, который не сортирует весь набор целиком (видно в EXPLAIN ANALYZE как Sort Method: top-N heapsort). Третий — согласование индекса с сортировкой: индекс (status, created_at DESC, id DESC) позволяет читать уже упорядоченные строки и убирает шаг Sort вместе с риском ухода во внешнюю сортировку на диск (work_mem исчерпан → Sort Method: external merge Disk: ...). Четвёртый — вынос: полнотекстовый поиск и фасеты в Elasticsearch/OpenSearch, рейтинги и лидерборды в Redis Sorted Set (ZRANGEBYSCORE — O(log n + k)), большие выгрузки — в асинхронную задачу с курсором и стримингом в файл, а не в синхронный HTTP-ответ.

Отдельно упомяните ограничения, которые вы поставили в API: максимальный limit (например, 100), максимальная глубина обычной пагинации, обязательный курсор для глубокой, и то, что общее число результатов отдаётся приблизительно (count по статистике или «более 1000»), потому что точный COUNT(*) по большому фильтру сам по себе стоит полного скана.

Как объединить два отсортированных односвязных списка в отсортированный один?

Коротко. Идти двумя указателями по обоим спискам, каждый раз отцепляя меньшую голову и подвешивая её к хвосту результата; когда один список кончился, прицепить остаток второго. O(n + m) по времени и O(1) по дополнительной памяти — узлы переиспользуются, ничего не аллоцируется.

Глубже. Приём, который делает код коротким и без спецслучаев, — фиктивная голова (dummy node): не нужно отдельно обрабатывать «первый вставляемый элемент». Сравнение через <=, а не <, сохраняет устойчивость: при равных значениях элемент из первого списка идёт раньше. Рекурсивный вариант короче, но даёт O(n + m) кадров стека — на длинных списках это плохо, и на собеседовании лучше сразу писать итеративный. Обобщение на k списков: куча размера k (container/heap) даёт O(N log k), либо попарное слияние «турниром» с той же асимптотикой; именно на этом стоит merge sort для списков — рекурсивно делим список пополам «черепахой и зайцем» и сливаем, получая O(n log n) времени при O(1) дополнительной памяти.

package main

type ListNode struct {
  Val  int
  Next *ListNode
}

func mergeTwoLists(a, b *ListNode) *ListNode {
  dummy := &ListNode{}
  tail := dummy
  for a != nil && b != nil {
    if a.Val <= b.Val {
      tail.Next, a = a, a.Next
    } else {
      tail.Next, b = b, b.Next
    }
    tail = tail.Next
  }
  if a != nil {
    tail.Next = a
  } else {
    tail.Next = b
  }
  return dummy.Next
}

Обратите внимание на tail.Next, a = a, a.Next: правая часть в Go вычисляется целиком до присваиваний, поэтому a.Next берётся ещё от старого a — записать это в две строки в обратном порядке было бы ошибкой.

Логическая задача: Есть сервер у него есть многоядерный поцессор 128mb оперативы и hdd 16tb. На нем лежит файл на 1tb построчно хранит числа int64. Задача - отсортировать.

Коротко. Внешняя сортировка слиянием в два этапа: читаем файл кусками, которые влезают в память (порядка 50–80 МБ полезных данных), сортируем каждый кусок в RAM и пишем на диск как отсортированный «ран»; затем сливаем раны k-путевым слиянием через кучу, буферизуя чтение каждого рана. Одного прохода слияния с фан-ином порядка сотни может не хватить, поэтому слияние делается в несколько уровней. Места на диске хватает: нужно ~2 ТБ при 16 ТБ, а узкое место — последовательный I/O, поэтому всё оптимизируется под большие последовательные чтения/записи и минимум seek’ов.

Глубже. Считаем. Текстовая строка с int64 — до 20 цифр плюс перевод строки, то есть 1 ТБ текста это примерно 5·10¹⁰ чисел. Первый выигрыш — сразу конвертировать в бинарный формат по 8 байт: файл сжимается примерно до 400 ГБ, а парсинг из текста уходит из внутреннего цикла слияния. Из 128 МБ RAM реально доступно меньше (рантайм Go, GC, буферы), поэтому берём порцию ~64 МБ = 8·10⁶ значений int64; получается порядка 6000 ранов при бинарном промежуточном формате. Слияние 6000 файлов одновременно нереалистично: на каждый нужен буфер (иначе HDD будет молотить головкой), а 6000 × 64 КБ = 384 МБ — не влезает. Значит фан-ин выбирается из бюджета памяти: например, 128 ранов по 256 КБ буфера ≈ 32 МБ, и тогда 6000 ранов сливаются за два уровня (6000 → 47 → 1). Каждый проход читает и пишет весь объём: при типичных 150 МБ/с у HDD один проход по 400 ГБ туда-обратно — примерно полтора часа, всего порядка 4–6 часов. Это и есть ответ на «почему нельзя просто сделать один merge»: считаем память под буферы, а не количество файловых дескрипторов.

Многоядерность используется на первой фазе: чтение с диска последовательное и однопоточное, а сортировка порций раздаётся горутинам (конвейер reader → N сортировщиков → writer через каналы) — сортировка 8 млн int64 занимает около секунды на ядро, и без параллелизма CPU стал бы вторым узким местом. На фазе слияния CPU почти не важен, там правит I/O; помогает только куча вместо линейного минимума (O(log k) на элемент) и крупные буферы через bufio.

Альтернатива слиянию — распределяющая сортировка (bucket/MSD radix): за один проход раскладываем числа по, скажем, 8192 файлам-корзинам по старшим битам ключа (со сдвигом знакового бита, чтобы отрицательные шли раньше положительных), затем каждую корзину (~50 МБ) сортируем в памяти и просто конкатенируем — фазы слияния нет вообще, всего два прохода по данным. Минус: 8192 открытых файлов с буферами и чувствительность к перекосу распределения (если данные не равномерны, корзина может не влезть в память — тогда её рекурсивно делят дальше). На SSD этот вариант почти всегда быстрее, на HDD выбор зависит от того, насколько дорого обходится случайная запись в тысячи файлов.

Дополнительные соображения, которые ценят: сортировку надо делать устойчивой к перезапуску (раны на диске — естественные чекпоинты), результат писать в отдельный файл и переименовывать атомарно, а если задача на самом деле «посчитать уникальные/частоты», а не «отсортировать», то дубликаты схлопываются прямо в процессе слияния и объём падает. Наконец, если бы диапазон значений был узким (как в соседних задачах, −10⁴…10⁴), сортировка выродилась бы в counting sort: массив счётчиков за один проход, без записи промежуточных данных вообще.

package main

import (
  "container/heap"
)

// item — текущий элемент из рана с номером run.
type item struct {
  val int64
  run int
}

type minHeap []item

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i].val < h[j].val }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)         { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() any {
  old := *h
  n := len(old)
  it := old[n-1]
  *h = old[:n-1]
  return it
}

var _ heap.Interface = (*minHeap)(nil)

Элемент a ближе к x, чем b, если |a - x| <|b - x|;

Коротко. Это фрагмент условия классической задачи «найти k ближайших к x элементов в отсортированном массиве» (LeetCode 658 Find K Closest Elements). Здесь задаётся метрика близости — модуль разности; отвечать надо не на строку, а на задачу целиком: ответ ищется бинарным поиском по левой границе окна длины k за O(log(n − k) + k), а не сортировкой всего массива по |a − x| за O(n log n).

Глубже. Ключевое наблюдение: поскольку массив отсортирован, ответ — это всегда непрерывный отрезок из k подряд идущих элементов. Значит достаточно найти его левую границу lo ∈ [0, n−k]. Бинарный поиск идёт по предикату «окно надо сдвинуть вправо»: сравниваем крайних кандидатов arr[mid] (левый край окна) и arr[mid+k] (первый элемент за окном) — если x − arr[mid] > arr[mid+k] − x, левый край дальше от x, чем ближайший элемент справа, и окно сдвигается. Сравнение написано без модулей намеренно: обе разности берутся в таком виде, что предикат монотонен по mid, и это же автоматически даёт нужное правило разрыва ничьей.

func findClosestElements(arr []int, k, x int) []int {
  lo, hi := 0, len(arr)-k
  for lo < hi {
    mid := lo + (hi-lo)/2
    if x-arr[mid] > arr[mid+k]-x {
      lo = mid + 1
    } else {
      hi = mid
    }
  }
  return arr[lo : lo+k]
}

Альтернатива без бинарного поиска — два указателя от найденной позиции x (через sort.SearchInts) и расширение окна в ту сторону, где сосед ближе: O(k) после O(log n) на поиск позиции, что при малом k эквивалентно по скорости и проще для устного объяснения. Вариант «положить всё в кучу по |a − x|» тоже даёт ответ, но за O(n log k) и полностью игнорирует отсортированность — на собеседовании это считается недоработкой.

Если расстояния равны, ближе тот, что меньше (a <b).

Коротко. Продолжение того же условия: правило разрыва ничьей. При равных расстояниях предпочтение отдаётся меньшему элементу, то есть окно смещается влево. В приведённом выше коде это уже учтено строгим > в условии — при равенстве x − arr[mid] == arr[mid+k] − x ветка сдвига не срабатывает, и hi = mid, то есть выбирается более левое окно.

Глубже. Если писать компаратор явно (например, для варианта с кучей или с сортировкой), правило выражается так:

import "cmp"

func closer(a, b, x int) int {
  da, db := abs(a-x), abs(b-x)
  if c := cmp.Compare(da, db); c != 0 {
    return c
  }
  return cmp.Compare(a, b) // при равном расстоянии меньший считается ближе
}

func abs(v int) int {
  if v < 0 {
    return -v
  }
  return v
}

Типичная ошибка — забыть про tiebreaker и получить нестабильный ответ: slices.SortFunc неустойчива, поэтому при равных расстояниях порядок элементов не определён и тесты будут падать через раз. Второй нюанс: результат по условию задачи обычно требуется вернуть в возрастающем порядке, поэтому после отбора k элементов по метрике их нужно ещё раз отсортировать по значению — в оконном решении это бесплатно, потому что срез уже упорядочен.

Значения элементов: от -10 000 до 10 000

Коротко. Ограничение на диапазон значений из того же условия. Практический смысл: разности помещаются в int без риска переполнения (максимум |a − x| = 20 000), а при необходимости можно вообще отказаться от сравнительной сортировки и применить counting sort по массиву из 20 001 ячейки за O(n + k).

Глубже. Такие строки в условии — подсказка о допустимом алгоритме, и на собеседовании их надо читать именно так. Малый диапазон значений означает: (1) можно считать частоты в срезе cnt := make([]int, 20001) со сдвигом индекса v + 10000, получив сортировку за линейное время и фиксированные 160 КБ памяти; (2) можно строить префиксные суммы и отвечать на запросы «сколько элементов в диапазоне» за O(1); (3) арифметика безопасна — переполнения int32 не будет даже при возведении разностей в квадрат (4·10⁸ < 2³¹). Обратная сторона: counting sort не имеет смысла, если массив уже отсортирован (а по соседнему пункту условия это так) — тогда правильный ответ по-прежнему бинарный поиск, а ограничение диапазона просто снимает вопросы про переполнение.

Массив всегда отсортирован по возрастанию

Коротко. Ещё одно ограничение из условия, и самое важное: раз массив отсортирован, работает бинарный поиск и метод двух указателей, а любое решение, начинающееся с сортировки, автоматически неоптимально. Для задачи о k ближайших это даёт O(log(n − k) + k) вместо O(n log n).

Глубже. «Отсортирован по возрастанию» стоит уточнить у интервьюера в одной детали: строго возрастает или неубывает (возможны дубликаты). Для бинарного поиска окна это не важно, но для задач вида «найти первое вхождение» разница принципиальна — нужен нижний/верхний границы поиск. В Go для этого есть готовое: slices.BinarySearch(s, v) возвращает индекс первого элемента, не меньшего v, и флаг точного совпадения; slices.BinarySearchFunc — то же с компаратором; sort.Search(n, f) — общий поиск точки перехода предиката из false в true, который и надо использовать, когда предикат нетривиален. Классические грабли: не поддерживать инвариант «ответ всегда в [lo, hi]», писать mid := (lo + hi) / 2 (в Go при int на 64 битах переполнение практически недостижимо, но привычка lo + (hi-lo)/2 правильная и обязательна в C/Java), и делать hi = mid - 1 там, где предикат уже проверен на mid, — теряется корректный ответ.

Последовательность может содержать отрицательные числа;

Коротко. Тоже ограничение из условия. Смысл — нельзя использовать беззнаковые типы и нельзя индексировать массив счётчиков напрямую значением: нужен сдвиг v + 10000. На саму логику бинарного поиска отрицательные значения не влияют, потому что порядок и разности определены одинаково для всего диапазона.

Глубже. Где отрицательные числа реально ломают код: индексация (cnt[v] при v < 0 — паника), радикс-сортировка по битам (у знаковых чисел старший бит у отрицательных равен 1, поэтому перед побитовой сортировкой ключ преобразуют как uint64(v) ^ (1 << 63), чтобы порядок совпал со знаковым), и наивное «сравнение по квадратам расстояний» при больших значениях. Ещё одна классика — abs для минимального значения знакового типа: -math.MinInt64 не представим, и if v < 0 { return -v } вернёт то же отрицательное число. В рамках диапазона −10⁴…10⁴ это неактуально, но проговорить стоит: именно такие граничные случаи и проверяют.

Для Задачи 2 длина строки может достигать 5*10⁴, поэтому требуется решение эффективнее O(n²). Классический подход - метод скользящего окна (two pointers) или предвычисление следующих позиций символов;

Коротко. Ограничение n ≤ 5·10⁴ означает, что квадратичный перебор всех подстрок (2.5·10⁹ операций) не пройдёт по времени, нужен линейный. Для задачи «сколько подстрок содержат все три символа a, b, c» линейное решение даёт либо скользящее окно с двумя указателями, либо приём «запоминаем последнюю позицию каждого символа»: для каждого правого конца i число подходящих левых границ равно min(last[a], last[b], last[c]) + 1.

Глубже. Вариант с последними позициями компактнее и не требует явного сжатия окна: идём слева направо, обновляем last[s[i]-'a'] = i, и если все три позиции уже встречались, то любая левая граница l ≤ min(last) даёт подстроку s[l..i], содержащую все три символа, — их ровно min(last)+1. Суммарно O(n) времени и O(1) памяти. Вариант two pointers эквивалентен: держим счётчики символов в окне, двигаем правый указатель, а когда окно стало «полным», сдвигаем левый максимально вправо, сохраняя полноту, и прибавляем left + 1 к ответу.

func numberOfSubstrings(s string) int {
  last := [3]int{-1, -1, -1}
  res := 0
  for i := 0; i < len(s); i++ {
    last[s[i]-'a'] = i
    res += min(last[0], min(last[1], last[2])) + 1
  }
  return res
}

Здесь min — встроенная функция, доступная с Go 1.21. При отсутствии какого-то символа соответствующий last равен −1, минимум тоже −1, и вклад −1 + 1 = 0 — отдельная проверка «все три встретились» не нужна. Работа идёт по байтам, что корректно, поскольку алфавит ограничен ASCII-символами a, b, c; для произвольного Unicode нужно было бы идти по рунам.

В исходной формулировке Задачи 2 для "aa" был указан некорректный ответ 2 . Правильный ответ - 0 .

Коротко. Это замечание об ошибке в условии: строка "aa" не содержит символов b и c, поэтому ни одна её подстрока не содержит все три символа, и правильный ответ — 0. Приведённый выше алгоритм даёт именно 0, так как last[1] и last[2] остаются равными −1 на всех шагах.

Глубже. Полезный вывод, который стоит озвучить на собеседовании: тестами первого порядка для такой задачи должны быть вырожденные случаи — пустая строка (0), строка без одного из символов (0), минимальная валидная строка "abc" (1), строка из повторов "abcabc" (10). Если условие противоречит примеру, правильная реакция — не подгонять код под пример, а зафиксировать противоречие вслух и уточнить у интервьюера, какая интерпретация имеется в виду («содержит все три» против «содержит хотя бы один» или «подстроки из различных символов»). Способность заметить и корректно отработать ошибку в постановке ценится не меньше, чем сам алгоритм.

LeetCode 1358. Number of Substrings Containing All Three Characters

Коротко. Ссылка на первоисточник «Задачи 2»: дана строка из символов a, b, c; нужно посчитать количество подстрок, содержащих хотя бы по одному вхождению каждого из трёх символов. Ограничение — 3 ≤ n ≤ 5·10⁴. Решение — линейное, приведено выше.

Глубже. Полезно знать семейство соседних задач, которые собираются из того же приёма скользящего окна: LeetCode 3 (самая длинная подстрока без повторов), 76 (минимальное окно, покрывающее шаблон), 209 (минимальный подмассив с суммой ≥ target), 340 (подстрока не более чем с k различными символами), 992 (подмассивы ровно с k различными — считается как «не более k» минус «не более k−1»). Общий шаблон: правый указатель расширяет окно и обновляет структуру счётчиков, левый сжимает окно, пока выполняется/нарушается условие, а к ответу прибавляется количество валидных левых границ. Отличается только предикат и то, что именно прибавляется — длина окна, left + 1 или n - right. Если на собеседовании удаётся назвать этот шаблон и свести к нему конкретную задачу, обсуждение обычно на этом и заканчивается.

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

• Называть sort.Slice устойчивой сортировкой. Устойчивы только sort.Stable, sort.SliceStable и slices.SortStableFunc; всё остальное — pdqsort, порядок равных элементов не определён.
• Утверждать, что quicksort всегда O(n log n), либо наоборот — что стандартная сортировка в Go уязвима к O(n²). В Go есть фолбэк в heapsort по глубине рекурсии, поэтому худший случай стандартной сортировки — O(n log n).
• Говорить «поиск в мапе всегда O(1)» без оговорок. Это среднее при хорошем распределении хеша; худший случай — линейный, а порядок обхода range рандомизирован и на него нельзя закладываться.
• Сортировать весь массив, когда нужны только k лучших или когда массив уже отсортирован. Top-k — это куча за O(n log k), поиск в отсортированном — бинарный за O(log n).
• В SQL полагаться на «прежний порядок» строк. Порядок без ORDER BY не определён, сортировка не устойчива, а LIMIT без полного набора ключей сортировки даёт неповторяемую выдачу между запусками.
• Использовать OFFSET для глубокой пагинации: стоимость растёт линейно с глубиной, а вставки между запросами приводят к пропуску и дублированию строк. Нужен keyset-курсор.
• В задаче на внешнюю сортировку выбирать фан-ин слияния по числу файлов, а не по бюджету памяти на буферы, и забывать про bufio — на HDD это разница в порядок по времени.
• Забывать про tiebreaker в компараторе (и в ORDER BY), из-за чего результат становится недетерминированным при равных ключах.

Что почитать

• pkg.go.dev/slices и pkg.go.dev/sort — актуальный API сортировки и бинарного поиска, пометки об устойчивости и сложности.
• Go 1.19 release notes, раздел sort — переход на pdqsort; исходники src/sort/gen_sort_variants.go и сгенерированные zsort*.go.
• Pattern-defeating Quicksort, Orson Peters — оригинальная статья про алгоритм, который сейчас стоит в Go и Rust.
• Go 1.24 release notes про новую реализацию map и Swiss Tables design doc — как устроен поиск по ключу после перехода на Swiss Tables.
• PostgreSQL: ORDER BY и NULLS FIRST/LAST и Use The Index, Luke — пагинация — про сортировку и ограничение выдачи в БД.