Программа курса Урок 14 из 148 · Правила дуэли
Правила дуэли

Ваша первая дуэль: медленный диск

Почему это важно Первый ответ на "посчитайте вещи в диапазоне" - посмотреть на каждую вещь. Это нормально, пока данных не много и их чтение не стоит денег или времени. Здесь стоит.

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

Решите задачу, прежде чем что-либо искать. Когда пройдёте, увидите, что скорее всего написал бы ИИ-ассистент, и путь эксперта, рядом.

Данные

from creative.budget import Tape
tape = Tape([3, 7, 7, 12, 40])   # sorted timestamps, every read counted
queries = [(0, 8), (7, 13)]       # windows: start included, end excluded
# window_counts(tape, queries) -> [3, 3]
Твоя очередь

Напишите window_counts(tape, queries). tape - это Tape отсортированных целочисленных меток времени (повторы допускаются). queries - список пар (start, end). Верните список, где для каждого окна указано, сколько меток t удовлетворяют start <= t < end. Бюджет: при 100 000 событий и 1 000 окон можно прочитать с ленты не больше 60 000 значений. len(tape) бесплатен.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.