Код Middle ClickHouse и колоночные СУБД обновлено
Какие гранулы прочитает ClickHouse
Условие
Разреженный индекс хранит значение ключа в первой строке каждой гранулы: marks[i] для гранулы i, ключи отсортированы по неубыванию. Гранула i содержит ключи из диапазона [marks[i], marks[i+1]] (у последней сверху без ограничения). Напишите granules_for_range(marks, lo, hi): индексы гранул, которые могут содержать ключи из [lo, hi] включительно. Гранула i подходит, если marks[i] <= hi и (это последняя гранула или marks[i+1] >= lo).
Примеры
granules_for_range([0, 100, 200, 300], 150, 160) // [1]
granules_for_range([0, 100, 200, 300], 100, 100) // [0, 1]
granules_for_range([0, 100, 200, 300], 250, 1000) // [2, 3]
Как подойти
Подсказки: 2
- Идите по гранулам, пока
marks[i] <= hi. - Гранула не подходит, если следующая начинается раньше
lo.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.