Разбор задачи про пересечение диапазонов дат с собеседования в телеком-компанию
Обнаружение пересечений в интервалах — довольно типичная задача, с которой приходится сталкиваться на практике. Зачастую это нужно для проверки данных на наличие ошибок.
Решение в лоб могло бы выглядеть следующим образом (см. рисунок 1). Я добавил поле id, чтобы разметить порядковый номер строки.
Но есть решение на основе оконки, которое покажет на порядок лучшие результаты с точки зрения производительности (см. рисунок 2). Оно базируется на том, что если в данных есть пересекающиеся интервалы, то существует как минимум два последовательных интервала I1 <= I2 (на основе порядка valid_from_dt, valid_to_dt, id), которые пересекаются.
Готовишься к собеседованиям?
В сборнике 190+ тестовых заданий для аналитиков: SQL, продуктовые кейсы, статистика, A/B и задачи на логику. Можно тренироваться по темам и разбирать реальные форматы собеседований.