Design RecentCounter class. ping(t) adds a request at time t and returns the number of requests in the past 3000ms [t-3000, t].
Use a Queue. Add t to queue. Remove elements older than t-3000. Return queue size.
- Queue
q. - ping(t): q.offer(t); while q.front < t-3000: q.poll().
- Return q.size().
- Time Complexity: O(1) amortized
- Space Complexity: O(W) where W is window size