A greenhouse controller only has room for the last capacity temperature readings. When the log is full, a new reading overwrites the oldest one instead of waiting or being rejected. The controller constantly asks for the average of what it has stored, so that must be instant.
Implement ReadingLog(capacity) (single-threaded, no locks needed):
- Store readings in
self.buf, a list of lengthcapacitycreated once in__init__. Track the position of the oldest reading and the count yourself, wrapping with% capacity. Nodeque,pop(0), slicing off the front, or growing the list. record(x): store the integer readingx. If the log is full, the oldest reading is dropped.__len__(): how many readings are stored (at mostcapacity).recent(k) -> list[int]: the lastmin(k, len)readings, oldest first.k >= 0.mean() -> float | None: the average of the stored readings, orNoneif there are none. It must be O(1): keep a running total, adding the new reading and subtracting the one that gets overwritten.
log = ReadingLog(3)
log.mean() # None
log.record(20); log.record(22); log.record(27)
log.mean() # 23.0
log.record(19) # full: overwrites 20
log.recent(5) # [22, 27, 19]
log.recent(2) # [27, 19]
log.mean() # 22.666... (68 / 3)
len(log) # 3
Constraints: 1 <= capacity <= 10^5, readings are integers in [-10^6, 10^6], up to 3·10^5 calls. The tests call mean() after every record() on a large log, so summing the buffer each time is too slow.
Show hint
When full, the slot to write is buf[head] (the oldest): subtract it from the total, overwrite it, and advance head. When not full, write at buf[(head + size) % capacity] and grow size. The i-th oldest reading lives at buf[(head + i) % capacity].