Coding Interview Prep · Урок

Поиск пропусков в последовательности

Находите отсутствующие значения и начало и конец каждого пропуска.

«Поиск пропусков в последовательности» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Теперь ищем пропуски

До сих пор мы объединяли строки в острова. Зеркальный вопрос на собеседовании звучит так: какие значения отсутствуют? Интервьюеры могут сформулировать его как «найдите пропуски в этой последовательности ID», «какие номера счетов пропущены» или «в какие дни не было активности».

Пропуски — это пустые места между островами. Главное — обычно не нужно перечислять каждое пропущенное значение: достаточно вывести начало и конец каждого диапазона пропуска. Это гораздо компактнее и именно этого ожидают интервьюеры.

Пример набора данных с пропусками

Повторно используйте имеющиеся значения 1, 2, 3, 7, 8, 10 из таблицы seq(n). Нужно вывести следующие пропуски:

От 4 до 6 (после первого острова и перед 7)
От 9 до 9 (между 8 и 10)

Обратите внимание: пропуск описывается как диапазон: gap_start = последнее имеющееся значение + 1, gap_end = следующее имеющееся значение - 1. Именно эта компактная форма лежит в основе описанного ниже приёма.

CREATE TABLE seq (n INT);
INSERT INTO seq VALUES (1),(2),(3),(7),(8),(10);

Подход с LEAD для поиска пропусков

Проще всего находить пропуски, сравнивая каждую строку со следующей с помощью LEAD. Если следующее значение больше текущего более чем на 1, между ними есть пропуск.

Для каждой такой строки пропуск начинается с n + 1 и заканчивается на next_n - 1. Сначала посмотрите на исходный результат LEAD:

SELECT
  n,
  LEAD(n) OVER (ORDER BY n) AS next_n
FROM seq
ORDER BY n;

Вывод диапазонов пропусков

Оберните результат LEAD в CTE и оставьте только строки, в которых скачок к следующему значению превышает 1. Такие строки обозначают пропуски:

В результате получаются ровно пропуски 4–6 и 9–9. Выражение next_n - n - 1 также даёт количество пропущенных значений в каждом диапазоне — это частый дополнительный вопрос.

WITH stepped AS (
  SELECT n, LEAD(n) OVER (ORDER BY n) AS next_n
  FROM seq
)
SELECT
  n + 1            AS gap_start,
  next_n - 1       AS gap_end,
  next_n - n - 1   AS missing_count
FROM stepped
WHERE next_n - n > 1
ORDER BY gap_start;

Симметричный вариант с LAG

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

Оба варианта полностью эквивалентны; выбирайте тот, который естественнее звучит в контексте вопроса. Некоторые интервьюеры предпочитают LEAD, потому что пропуск описывается относительно предшествующей ему строки, как это обычно формулируют в речи.

WITH stepped AS (
  SELECT n, LAG(n) OVER (ORDER BY n) AS prev_n
  FROM seq
)
SELECT prev_n + 1 AS gap_start,
       n - 1       AS gap_end
FROM stepped
WHERE n - prev_n > 1
ORDER BY gap_start;

Вывод всех пропущенных значений

Иногда интервьюеру действительно нужен полный список пропущенных чисел, а не только диапазоны. Надёжный подход — сгенерировать полную ожидаемую последовательность и выполнить антисоединение с имеющимися данными. В PostgreSQL функцию generate_series можно использовать для построения полного диапазона:

Каждое целое число из ожидаемого диапазона, которого нет в seq, является пропущенным значением. Этот подход также обрабатывает пропуски у самых границ, если известны предполагаемые минимум и максимум.

SELECT g.n AS missing_value
FROM generate_series(
       (SELECT MIN(n) FROM seq),
       (SELECT MAX(n) FROM seq)
     ) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL
ORDER BY g.n;

Генерация последовательностей в разных диалектах

Не каждая СУБД поддерживает generate_series. Знайте альтернативы:

PostgreSQL: generate_series(1, 100).
SQL Server: рекурсивный CTE или таблица чисел.
MySQL 8: рекурсивный CTE, который считает до максимального значения.

Рекурсивный CTE — универсальный запасной вариант. Он создаёт ту же ожидаемую последовательность для последующего антисоединения.

WITH RECURSIVE nums AS (
  SELECT (SELECT MIN(n) FROM seq) AS n
  UNION ALL
  SELECT n + 1 FROM nums
  WHERE n + 1 <= (SELECT MAX(n) FROM seq)
)
SELECT nums.n AS missing_value
FROM nums
LEFT JOIN seq s ON s.n = nums.n
WHERE s.n IS NULL;

Пропуски в календарных датах

Для поиска пропущенных дат создайте полный календарь с шагом в один день и выполните антисоединение. Это стандартный запрос «в какие дни не было заказов»:

Объедините его с приёмом поиска диапазонов: примените LEAD к фактическим датам, чтобы выводить периоды пропущенных дат вместо отдельных дней, используя + INTERVAL '1 day' для границ.

SELECT d::date AS missing_day
FROM generate_series(
       DATE '2026-01-01', DATE '2026-01-31',
       INTERVAL '1 day') AS d
LEFT JOIN daily_logins l ON l.login_date = d::date
WHERE l.login_date IS NULL
ORDER BY missing_day;

Пропуски за пределами данных

Есть важная тонкость: LEAD/LAG находят только пропуски между имеющимися значениями. Если число пропущено до минимального или после максимального имеющегося значения, оконный подход не увидит его, поскольку соседней строки нет.

Если интервьюер задаёт полный ожидаемый диапазон (например, ID от 1 до 100), а ваши данные начинаются с 5, необходимо использовать антисоединение с генерируемым рядом в пределах объявленного диапазона, а не минимальным и максимальным значениями самих данных. Всегда уточняйте, заданы ли ожидаемые границы явно.

SELECT g.n AS missing_value
FROM generate_series(1, 100) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL;

Поиск пропусков по группам

Для поиска пропусков по каждому пользователю выполните разбиение LEAD/LAG по столбцу группы, чтобы пропуск никогда не определялся между потоками двух разных пользователей:

Диапазоны пропусков для каждого пользователя вычисляются независимо. Как и в случае с островами, если забыть выполнить разбиение, пользователи незаметно объединятся, а между несвязанными строками появятся фиктивные пропуски.

WITH stepped AS (
  SELECT user_id, n,
    LEAD(n) OVER (PARTITION BY user_id ORDER BY n) AS next_n
  FROM seq_per_user
)
SELECT user_id, n + 1 AS gap_start, next_n - 1 AS gap_end
FROM stepped
WHERE next_n - n > 1
ORDER BY user_id, gap_start;

Выбор подходящего метода поиска пропусков

Ориентир для собеседования:

Нужны компактные диапазоны и только внутренние пропуски? Используйте LEAD/LAG, отбирая строки, где шаг превышает 1.
Нужно каждое отдельное пропущенное значение или пропуски за границами данных? Используйте антисоединение с генерируемым рядом для полного объявленного диапазона.

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

Быстрая проверка

Разберитесь с тонкостью, связанной с границами диапазона.

Итоги: поиск пропусков

Основные правила поиска пропусков:

Выводите пропуски как диапазоны: gap_start = значение + 1, gap_end = следующее_значение - 1.
LEAD (или симметричный LAG) с фильтрацией по шагу больше 1 дёшево находит внутренние пропуски.
Антисоединение с генерируемым рядом перечисляет каждое пропущенное значение и находит пропуски у границ заданного диапазона.
Рекурсивные CTE создают последовательность там, где отсутствует generate_series.
Для поиска пропусков по пользователям выполняйте разбиение по столбцу группы.
Всегда уточняйте ожидаемые границы.

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

Часто задаваемые вопросы

Урок «Поиск пропусков в последовательности» бесплатный?

Да — полный текст урока «Поиск пропусков в последовательности» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Поиск пропусков в последовательности»?

Находите отсутствующие значения и начало и конец каждого пропуска. Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Поиск пропусков в последовательности»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

Распознавание задачи о пропусках и островах
Приём с разностью номеров строк
Поиск пропусков в последовательности
Острова при изменении даты и статуса

← Назад к Coding Interview Prep