Comment by malisper | Hacker News Reader

Comment by malisper | Hacker News Reader

Parent Full thread

> The solution described in the article is likely to be extremely wasteful in both time and memory, by allocating a queue entry for each call, and then O(n) scanning and dropping stale entries on each successive call.

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.

> That means the number of elements scanned is proportional to the number of elements inserted.

And the number of elements inserted is in the worst case N, hence the proposed solution has a worst case complexity of O(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.

It's not specified in the article?

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 ;)

> It's not specified in the article?

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.

Geniusly curious: does "expected" in English necessarily means average? My understanding was that expected is dependent of the application domain, so it can mean best or worst or average.

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.

"Expected value" or "expectation" is a precise mathematical term in probability theory that corresponds to "average-case", always.

Reply on news.ycombinator.com