0Pricing
SQL Interview Prep · Урок

Распознавание задачи о пропусках и островах

Выявляйте шаблон в условии задачи и основную идею группировки.

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

Шаблон, который проверяют на собеседовании

Когда опытный собеседник просит Вас найти непрерывные последовательности чего-либо, перед Вами задача о разрывах и островах. Название связано с мысленной картиной: строки, относящиеся к одной группе, образуют остров, а разделяющие их разрывы — это промежутки.

  • Остров — это максимальная последовательность соседних строк, связанных некоторым правилом (последовательные целые числа, последовательные даты или повторяющийся статус).
  • Разрыв — это отсутствующий промежуток между двумя островами.

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

Формулировки задач, за которыми скрывается остров

Сложность в том, что собеседники редко говорят прямо «разрывы и острова». Они маскируют эту задачу. Учитесь распознавать формулировки вроде таких:

  • «Найдите каждый период, когда у пользователя была непрерывная подписка».
  • «Сколько последовательных дней сервер продолжал работать?»
  • «Какие диапазоны идентификаторов отсутствуют в этой таблице?»
  • «Объедините соседние строки с одинаковым статусом в одну строку».

Все эти задачи имеют одну структуру: сгруппировать соседние строки, а затем вывести начало, конец или отсутствие таких групп. Как только Вы сопоставите формулировку с островами, SQL почти напишется сам.

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

Весь приём можно выразить одним предложением: если каждой строке одного острова можно назначить одинаковый ключ группы, простая группировка GROUP BY свернёт каждый остров в одну итоговую строку.

Значит, настоящая работа в любой задаче о разрывах и островах — вычислить этот ключ группы. Разные варианты вычисляют его по-разному, но цель у них одна. Получив ключ, Вы легко выполняете последний шаг:

SELECT
  grp,
  MIN(value) AS island_start,
  MAX(value) AS island_end,
  COUNT(*)   AS island_length
FROM rows_with_group_key
GROUP BY grp
ORDER BY island_start;

Конкретный набор данных

Рассмотрим данные. Представьте таблицу logins, в которой хранятся номера дней, когда пользователь выполнял вход:

  • Присутствующие дни: 1, 2, 3, 7, 8, 10

На первый взгляд острова — это {1,2,3}, {7,8} и {10}. Разрывы — дни 4–6 и день 9. Ваша задача на собеседовании — заставить базу данных увидеть эти три острова без ручного указания на них. Держите этот небольшой набор данных в уме, пока мы рассматриваем каждый способ.

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

Почему наивные подходы не работают

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

  • Нужно обнаружить и начало, и конец каждого острова, а значит, выполнить два прохода или два соединения.
  • Граничные строки — самая первая и самая последняя — требуют особой обработки.
  • Без дополнительной логики такой подход не обобщается на задачу «выведите длину каждой последовательности».

Собеседники смотрят, начнёте ли Вы войну с самосоединениями или поймёте, что один проход с оконной функцией будет проще.

Модель обнаружения разрывов

Один из надёжных способов сформулировать задачу таков: новый остров начинается всякий раз, когда текущая строка не является соседней с предыдущей. Используйте LAG, чтобы обратиться к предыдущей строке и выполнить сравнение.

Если day_no - LAG(day_no) больше 1 (или равен NULL для первой строки), эта строка начинает новый остров. Пометьте такой случай значением 1, а остальные — значением 0. Посмотрите, как эти метки выглядят для нашего набора данных.

SELECT
  day_no,
  CASE
    WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1 THEN 0
    ELSE 1
  END AS is_new_island
FROM logins
ORDER BY day_no;

Преобразование меток в ключ группы

Метки из предыдущего шага для дней 1, 2, 3, 7, 8, 10 имеют вид 1, 0, 0, 1, 0, 1. Обратите внимание: накопительная сумма этих меток даёт число, постоянное внутри острова и увеличивающееся при начале каждого нового острова: 1, 1, 1, 2, 2, 3.

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

WITH flagged AS (
  SELECT
    day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new_island
  FROM logins
)
SELECT
  day_no,
  SUM(is_new_island) OVER (ORDER BY day_no) AS grp
FROM flagged;

Завершение разобранного примера

Теперь добавьте итоговую группировку GROUP BY поверх ключа группы. Каждое уникальное значение grp представляет один остров; выведем его границы и размер:

Результат в точности совпадает с тремя островами, которые мы увидели визуально: 1–3 (длина 3), 7–8 (длина 2) и 10–10 (длина 1). Эта схема из трёх слоёв — метка, накопительная сумма, группа — лежит в основе почти каждого решения задачи о разрывах и островах, которое Вы напишете.

WITH flagged AS (
  SELECT day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new
  FROM logins
),
keyed AS (
  SELECT day_no,
    SUM(is_new) OVER (ORDER BY day_no) AS grp
  FROM flagged
)
SELECT grp, MIN(day_no) AS start_day,
       MAX(day_no) AS end_day, COUNT(*) AS len
FROM keyed GROUP BY grp ORDER BY start_day;

Смежность зависит от предметной области

Между задачами меняется только определение соседства. Распознать правильное правило соседства — значит наполовину распознать саму задачу:

  • Целые числа: значения соседние, если разность равна ровно 1.
  • Календарные дни: значения соседние, если одна дата является следующим днём (date = prev + INTERVAL '1 day').
  • Периоды статуса: значения соседние, если статус не изменился по сравнению с предыдущей строкой.

Основа одна и та же, меняется только сравнение внутри CASE. На собеседовании следует вслух уточнить, какое правило соседства применимо.

Уточняющие вопросы

Прежде чем писать строку SQL, наберите дополнительные баллы, уточнив область задачи. Полезные уточнения для задач о разрывах и островах:

  • «Следует рассматривать данные для каждого пользователя отдельно или глобально?» (От этого зависит, добавите ли Вы PARTITION BY user_id.)
  • «Могут ли в один день встречаться повторяющиеся значения и прерывают ли они последовательность или продолжают её?»
  • «Нужно найти острова, разрывы или и то и другое?»
  • «Гарантированно ли последовательность отсортирована или мне нужно отсортировать её самостоятельно?»

Такие вопросы показывают, что Вы уже решали этот тип задач и понимаете его граничные случаи.

Острова для каждой группы с PARTITION BY

В реальных данных с собеседований почти всегда есть группы, например входы для каждого пользователя. Исправление механическое: добавьте PARTITION BY user_id в каждую оконную функцию, чтобы острова никогда не объединяли разных пользователей.

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

SELECT
  user_id, day_no,
  CASE WHEN day_no - LAG(day_no)
         OVER (PARTITION BY user_id ORDER BY day_no) = 1
       THEN 0 ELSE 1 END AS is_new
FROM logins;

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

Проверьте, как Вы распознаёте шаблоны.

Итоги: распознаём структуру

Теперь Вы можете распознать задачу о разрывах и островах по замаскированной формулировке и назвать подходящую стратегию:

  • Ключевые слова: последовательный, непрерывный, непрерывный без разрывов, серия, пропущенные диапазоны, объединить соседние строки.
  • Основная идея: назначить каждой строке одной последовательности одинаковый ключ группы, а затем выполнить GROUP BY по этому ключу.
  • Схема: пометить новые острова с помощью LAG, превратить метки в ключ с помощью накопительной суммы, а затем выполнить агрегацию.
  • Соседство зависит от предметной области: это могут быть целые числа, даты или неизменный статус.
  • Добавляйте PARTITION BY для анализа по группам и уточняйте область задачи до написания кода.

Далее мы разберём самый изящный способ построения ключа — приём с разностью номера строки.

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

Урок «Распознавание задачи о пропусках и островах» бесплатный?

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

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

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

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

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

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

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

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

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

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

  1. Распознавание задачи о пропусках и островах
  2. Приём с разностью номеров строк
  3. Поиск пропусков в последовательности
  4. Острова при изменении даты и статуса
← Назад к SQL Interview Prep