The problem
A signal box receives pings at increasing times. Write a class RecentPings(window). Its method ping(t) records a ping at time t, then returns how many pings so far arrived between t - window and t, both ends included.
r = RecentPings(3000)
r.ping(1) # 1
r.ping(100) # 2
r.ping(3001) # 3: times 1 … 3001 hold all three
r.ping(3002) # 3: times 2 … 3002; 1 is too old
Limits
- Each call’s
tis bigger than the one before. - Up to 300,000 calls; each one should take O(1) time on average.
Builds on STAQ-3 Queues and deque.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
6 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Small | Not run | |
| 2 | Edge of the window | Not run | |
| 3 | Long gap | Not run | |
| 4 | Window 0 | Not run | |
| 5 | Two objects | Not run | |
| 6 | 300,000 pings | Not run |