Syllabus Lesson 133 of 141 · Ten doors and the field kit
Ten doors and the field kit

Final 2: a window for every server

AI off This is a final exam, matched to the baseline exam you did in the first module: the same kind of problem, new data, the same difficulty. The tutor is switched off and there are no hints. Work alone. The course lines it up against your baseline in the next lesson.

An operations team needs a window when every server in a cluster is idle, to patch them together. Job history for each server sits in a separate archive that charges for every entry fetched, and the archives go back years.

A small example

from creative.budget import Tape
cals = [[(0, 30), (60, 30)], [(10, 30)], []]       # (start, minutes)
maintenance_window([Tape(c) for c in cals], 0, 15)   # -> 40  (idle from 40 to 60)
maintenance_window([Tape(c) for c in cals], 0, 20)   # -> 40  (40 + 20 = 60: touching is fine)
maintenance_window([Tape(c) for c in cals], 0, 25)   # -> 90
Your turn

Write maintenance_window(calendars, after, length). calendars is a list of Tapes, one per server. Each holds that server's jobs as (start, minutes) pairs, sorted by start; a job is busy from start up to but not including start + minutes, and one server's jobs never overlap (they may touch). Return the earliest minute t >= after such that no server is busy anywhere in [t, t + length). Every server is idle after its last job, so there is always an answer.
Budget: there are 50 servers with 2,000 jobs each (100,000 entries), and after is usually months into the data. One search may read at most 10,000 entries in total. len() of a Tape is free.

AI off: no tutor, hints or worked solution on this one. Your own thinking only.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus