Tabulating call count by division(s) of time would be less obviously problematic.
Even if n elements are scanned in the the worst case, the expected time it takes to perform such a scan is O(1). This is because we perform a scan on each insertion and O(n) elements are deleted in a scan of length n. That means the number of elements scanned is proportional to the number of elements inserted.
> Tabulating call count by division(s) of time would be less obviously problematic.
Tabulating call count by division(s) of time doesn't quite work. If a 9 calls are made at the last second of one division of time and 9 more calls are made in the first second of the next division of time, you will hit 18 calls in a two second interval which is over the limit of 10 calls for any one minute interval.
And the number of elements inserted is in the worst case N, hence the proposed solution has a worst case complexity of O(N)?
Worst case yes, but the question is concerned with the average case.
Do that for rate limiting and it'll be super easy to DoS you - just show how fundamentally you can't brute force your way out of algorithmic questions despite the article suggestion (or how interviews are fundamentally flawed, but this is another debate ;)
From the article:
> The function should have expected O(1) performance.
> Do that for rate limiting and it'll be super easy to DoS you
How so? The rate limiter has the same performance as, for example, a hash table. Operations are usually O(1), but are periodically O(n). It's not like every service that uses a hash-table is DoS-able.
If you have an implementation that is O(N) in worst case it's (theoretically) DoSable since an attacker would always hit that case - so the expected complexity in case of an attack is O(N).
A trivial solution in O(60)=O(1) for worst case is to store the number of call everything second in a fixed size array and loop over it. With some arithmetic you can even avoid looping over it.
initialize : double credit = N
At every request :
penalty = (elapsedTime / window_size) - (1/N)
gain = N* (elapsedTime / window_size)
credit = min( credit + gain - (penalty<0) , N)
if( credit < 0 ) throw exception
gain = N * (elapsedTime / window_size);
credit = min(credit + gain, N);
if (credit >= 1) {
credit--;
log(...);
} else {
return; /* not enough credits */
}
But I'm not really sure of the value it adds over simply taking a cost of 1 as you suggest. When time beween requests are spreaded more than window_size/N they don't cost credit. This mean you have a smaller number of "hot" clients (clients who are not full credit) to monitor.
The second idea that often occurs in problems with sliding windows is the telescoping sum which is hiding implicitly in the sum of elapsed Times.
- putting 500 timestamps into a queue
- inspecting 500 queue entries and removing each
- putting 500 new timestamps into a queueThe 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.
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."
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.