0Pricing
Coding Interview Prep · Урок

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

Используйте арифметику дат и номера строк, чтобы находить непрерывные последовательности дней.

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

Условие задачи на собеседовании

Интервьюеры любят задачи о сериях, потому что они показывают, действительно ли Вы понимаете оконные функции и арифметику дат. Типичная формулировка: «Для заданной таблицы с датами входа пользователей найдите каждую непрерывную серию последовательных календарных дней».

Наивный подход — соединить таблицу с самой собой, сравнивая каждую строку со следующей, но на больших таблицах это приводит к резкому росту объёма вычислений, а выразить такое решение непросто. Профессиональный ответ использует метод разрывов и островов. В этом уроке Вы научитесь аккуратно находить последовательные дни с помощью номеров строк и вычитания дат.

Пример данных

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

  • user_id — кто входил в систему
  • login_date — значение DATE

Для пользователя 1 даты — 1, 2 и 3 января, затем разрыв, потом 6 и 7 января. Мы ожидаем две серии: серию длиной 3 дня и серию длиной 2 дня.

SELECT * FROM logins ORDER BY user_id, login_date;
-- user_id | login_date
--    1    | 2024-01-01
--    1    | 2024-01-02
--    1    | 2024-01-03
--    1    | 2024-01-06
--    1    | 2024-01-07

Основная идея

Вот приём, который открывает путь к решению любой задачи о последовательных днях. Если упорядочить строки по дате и присвоить каждой последовательный номер строки, то для любой серии последовательных дней разность между датой и номером строки остаётся постоянной.

Почему? И дата, и номер строки увеличиваются ровно на 1 с каждым последовательным днём, поэтому их разность не меняется. Когда появляется разрыв, дата перескакивает, а номер строки — нет, из-за чего постоянное значение нарушается и начинается новая группа.

Наглядный пример разности

Рассмотрим это вручную для пользователя 1. ROW_NUMBER выдаёт значения 1, 2, 3, 4, 5. Вычтем номер строки (как количество дней) из даты и проследим за результатом.

  • 1 января − 1 = 31 декабря
  • 2 января − 2 = 31 декабря
  • 3 января − 3 = 31 декабря
  • 6 января − 4 = 2 января
  • 7 января − 5 = 2 января

Первые три строки имеют общее значение 31 декабря, а последние две — 2 января. Это общее опорное значение и есть наш ключ группы.

Добавление ROW_NUMBER

Первый практический шаг — присвоить номер строки с разбиением по пользователю, чтобы серии никогда не пересекали границы пользователей, и с сортировкой по дате.

PARTITION BY user_id запускает счётчик заново для каждого пользователя, а ORDER BY login_date гарантирует, что последовательность соответствует календарю.

SELECT
  user_id,
  login_date,
  ROW_NUMBER() OVER (
    PARTITION BY user_id
    ORDER BY login_date
  ) AS rn
FROM logins;

Вычисление опорного значения группы

Теперь вычтите из login_date количество дней, указанное в rn. В PostgreSQL можно напрямую вычесть из даты целое число дней. Получившееся постоянное опорное значение определяет каждый остров.

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

WITH numbered AS (
  SELECT
    user_id,
    login_date,
    ROW_NUMBER() OVER (
      PARTITION BY user_id ORDER BY login_date
    ) AS rn
  FROM logins
)
SELECT
  user_id,
  login_date,
  login_date - rn AS grp
FROM numbered;

Группировка островов

Зная опорное значение, мы видим, что каждая последовательная серия имеет одно и то же значение grp. Сгруппируйте данные по user_id и grp, затем выполните агрегацию, чтобы получить начало, конец и длину каждой серии.

  • MIN(login_date) — первый день серии
  • MAX(login_date) — последний день серии
  • COUNT(*) — количество дней в серии
WITH numbered AS (
  SELECT user_id, login_date,
    ROW_NUMBER() OVER (
      PARTITION BY user_id ORDER BY login_date
    ) AS rn
  FROM logins
)
SELECT
  user_id,
  MIN(login_date) AS streak_start,
  MAX(login_date) AS streak_end,
  COUNT(*)        AS streak_len
FROM numbered
GROUP BY user_id, login_date - rn
ORDER BY user_id, streak_start;

Различия диалектов

Синтаксис арифметики дат различается. Упомяните это на собеседовании, чтобы показать широту знаний.

  • PostgreSQL: login_date - rn (вычитание целого количества дней из даты)
  • MySQL: DATE_SUB(login_date, INTERVAL rn DAY)
  • SQL Server: DATEADD(day, -rn, login_date)

Логика одинакова, меняются только названия функций. Универсальная мысленная модель такова: «сдвиньте каждую дату назад на её позицию, чтобы непрерывная серия свернулась в одно постоянное значение».

-- SQL Server version of the anchor
DATEADD(day, -1 * rn, login_date) AS grp

Почему не соединение таблицы с самой собой

Интервьюер может спросить, почему Вы не использовали соединение таблицы с самой собой, например l1.login_date = l2.login_date + 1. Назовите следующие причины:

  • Соединение таблицы с самой собой проверяет только соседство, а не всю серию — для построения полной серии всё равно нужна группировка.
  • Без хороших индексов оно может порождать множество строк и иметь сложность O(n²).
  • Метод с номерами строк выполняет один упорядоченный проход и гораздо лучше масштабируется.

Оконные функции — современный и ожидаемый ответ для таких задач.

Защита от дубликатов

Вся эта техника предполагает одну строку на пользователя в день. Если источник содержит несколько входов за один день, две строки с одной датой получат разные номера, что исказит опорное значение.

Защититесь, удалив дубликаты заранее: приведите временные метки к датам и примените DISTINCT либо используйте DENSE_RANK по дате вместо ROW_NUMBER, чтобы одинаковые даты получили один номер.

WITH days AS (
  SELECT DISTINCT user_id, login_ts::date AS login_date
  FROM raw_logins
)
SELECT * FROM days;

Полное решение

Если объединить все части, получится аккуратный готовый для собеседования ответ, который выводит каждую серию последовательных дней с её началом, концом и длиной.

Эта же схема — удалить дубликаты, пронумеровать, вычесть, сгруппировать — решает почти любую задачу о последовательностях, которую Вам предложат.

WITH days AS (
  SELECT DISTINCT user_id, login_ts::date AS login_date
  FROM raw_logins
),
numbered AS (
  SELECT user_id, login_date,
    ROW_NUMBER() OVER (
      PARTITION BY user_id ORDER BY login_date
    ) AS rn
  FROM days
)
SELECT user_id,
  MIN(login_date) AS streak_start,
  MAX(login_date) AS streak_end,
  COUNT(*)        AS streak_len
FROM numbered
GROUP BY user_id, login_date - rn
ORDER BY user_id, streak_start;

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

Проверьте, насколько хорошо Вы поняли основной приём.

Итоги

Вы освоили основную схему для последовательных дней:

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

Эта схема разрывов и островов масштабируется за один проход и превосходит соединения таблицы с самой собой. Далее Вы используете её для вычисления самой длинной серии для каждого пользователя.

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

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

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

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

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

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

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

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

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

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

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

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

  1. Поиск последовательных календарных дней
  2. Самая длинная серия для пользователя
  3. N последовательных строк, соответствующих условию
  4. Текущая активная серия на сегодня
← Назад к Coding Interview Prep