Coding: Keep track of last N days of records for each user.

Question

Im solving an interesting problem wherein for each user, I would like to keep his last N days of activity. This can be applied to many a use-cases and one such simple one is:

For each user - user can come to gym some random day - I want to get the total number of times he hit the gym over the last 90 days.

This is a tricky one for me.

My thoughts: I thought of storing a vector where each entry would determine a day and then a boolean value might represent his visit. To count, just linear processing of that section in the array would suffice.

What is the best way?

Answer 1

Make for every client a Queue data structure containing elements with visit date. When client visits gym, just add current date

Q[ClientIdx].Add(Today)

When you need to get a track for him:

while (not Q[ClientIdx].Empty) and (Today - Q[ClientIdx].Peek > 90) 
    Q[ClientIdx].Remove  //dequeue too old records
VisitCount = Q.Count

You can use standard Queue implementations in many languages or simple own implementation based on array/list if standard one is not available.

Note that every record is added and removed once, so amortized complexity is O(1) per add/count operation