Fixed-Window Packet Rate Limit

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Fixed-Window Packet Rate Limit. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Given a non-decreasing array of integer timestamps timestamps and an integer window_size, return an array where each element is the number of events that occurred within the inclusive time window [timestamps[i] - window_size + 1, timestamps[i]]. Implement an efficient algorithm that processes the timestamps in one pass.

Constraints

1 <= len(timestamps) <= 10^5
0 <= timestamps[i] <= 10^9
timestamps is sorted in non-decreasing order
1 <= window_size <= 10^9

Function Signature

def count_events_in_window(timestamps, window_size):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output