[taeric]

I'd assume a linked list was used to be able to drop a lot in a single shot. In particular, seems safe to assume the queue is sorted by time. Such that as soon as you see a time that is outside the window, you can drop all of the rest in one shot.

The page wasn't loading for me, so I can't see the proposal. Just don't let a linear scan scare you, for small n.

[sk5t]

There are various approaches that might or might not improve the runtime outlook (maybe a priority queue, maybe a list that supports fast random access for binary or exponential search, etc.) but wouldn't the only "fast" path to drop a bunch of entries hinge on moving the head reference and pushing the work onto the GC? One might start to think about something like a ring at the point where this would start to matter.

Asserting small n seems like a way to wash out of coding interviews that are focused on identifying and avoiding costly naive solutions. Interviewers are like as not to say "okay, now the rate limit is 5,000/sec/customer/operation, and there are 100,000 customers."

[taeric]

I'm assuming a mutable linked list where you can just set the rest from any point to null.

Though, I confess I don't see benefits of linked list for this, all told.

Sounds like the intent is to scan forward until you hit the limit of calls, or see you have hit the boundary. In which case you set the current next point to the current call? Is what you are describing.