educative.io

More efficient sliding window algorithm?

Courses
,
#1

Would it be more efficient to use just basic array?

“kristie”: [149836252, 149836586, 149836987]

We know that we allow 3 requests per minute.

  1. New request comes in. We calculate the current time minus time in the element with index = [array.length – 3]
  2. If it is less than a minute, we insert the time in the array, if more, deny the request
  3. To clean up space we delete all array elements with index = array.length - 4

In this case we do not need any fancy data structures.

#2

Hi Viacheslav,

Thank you for reaching out to us and giving your feedback. We’ll get back to you soon!

If you have any further concerns/questions/comments, please let us know.

Best regards,
Educative Team

#3

I feel it is hard to keep the array sorted in the multi-threading case.

2 Likes
#4

agree

#5

Yes，but you need to consider about race condition which just like the author mentioned in article

#6

Why don’t we use queue?

1 Like
#7

@Neil I wondered about the same thing but questioned why a REDIS SORTED SET was in use instead of a REDIS LIST. The sliding window algorithm provided here is based on the leaky bucket API rate limiting algorithm which makes use of a queue.

With a vanilla FIFO queue, in a distributed system without locks, you will not be able to guarantee that the front of the queue is the oldest timestamp because they could be added by different hosts in the network. Since you always need to kick out the oldest timestamp when the queue is full, it is essential to manage a sorted structure as opposed to a simple FIFO queue. Hope this makes sense.