A blog dashboard shows a live "views in the last 5 minutes" number. Web servers report views in batches: one report can carry many views that all happened in the same second.
Build ViewCounter():
record(t: int, count: int) -> None:countviews happened at integer secondt.total(t: int) -> int: how many views happened in the 300 seconds ending att, that is, at timestimewitht - 300 < time <= t. A view exactly 300 seconds old no longer counts.
Across all calls t never decreases, and several reports can share a second.
v = ViewCounter()
v.record(1, 5)
v.record(1, 2)
v.record(100, 10)
v.total(100) # 17
v.total(300) # 17 (the views at 1 are 299 seconds old)
v.total(301) # 10 (the views at 1 are now 300 seconds old: gone)
v.total(400) # 0
v.record(1000, 3)
v.total(1000) # 3
1 <= count <= 1,000,000;0 <= t <= 10^9. Totals can exceed 2^31.- Up to 300,000 calls. Storing one entry per view is far too slow and large here, and so is rescanning the whole history on each
total. Aim for O(1) amortized per call, with memory that doesn't grow with the number of reports.
Show hint
Only 300 distinct seconds can ever matter at once. Keep one small record per second rather than per view, and keep the current sum up to date as old seconds fall out.