Разбор задачи про пересечение диапазонов дат с собеседования в телеком-компанию
Обнаружение пересечений в интервалах — довольно типичная задача, с которой приходится сталкиваться на практике. Зачастую это нужно для проверки данных на наличие ошибок.
Решение в лоб могло бы выглядеть следующим образом (см. рисунок 1). Я добавил поле id, чтобы разметить порядковый номер строки.
Но есть решение на основе оконки, которое покажет на порядок лучшие результаты с точки зрения производительности (см. рисунок 2). Оно базируется на том, что если в данных есть пересекающиеся интервалы, то существует как минимум два последовательных интервала I1 <= I2 (на основе порядка valid_from_dt, valid_to_dt, id), которые пересекаются.
Хотите больше подобных разборов? Тогда поддержите этот пост🐳 .)
#задачиссобеседований
Обнаружение пересечений в интервалах — довольно типичная задача, с которой приходится сталкиваться на практике. Зачастую это нужно для проверки данных на наличие ошибок.
Решение в лоб могло бы выглядеть следующим образом (см. рисунок 1). Я добавил поле id, чтобы разметить порядковый номер строки.
Но есть решение на основе оконки, которое покажет на порядок лучшие результаты с точки зрения производительности (см. рисунок 2). Оно базируется на том, что если в данных есть пересекающиеся интервалы, то существует как минимум два последовательных интервала I1 <= I2 (на основе порядка valid_from_dt, valid_to_dt, id), которые пересекаются.
Хотите больше подобных разборов? Тогда поддержите этот пост
#задачиссобеседований