Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
An alerting job fires every minute and asks the same question of a sorted event log: how many events landed in the last window? The log is already sorted by time and holds millions of rows, so scanning it end to end on every tick is the cost the team wants to remove. Windows are half-open, so back-to-back windows never count the same event twice.
Write count_in_range(timestamps, start, end). It takes a list of integer epoch-second timestamps sorted ascending (duplicates allowed), and two integers start and end describing the range [start, end). It returns the number of timestamps inside that range, as an integer.
Function to write
count_in_range(timestamps: list[int], start: int, end: int) -> intThe number of timestamps t with start <= t < end, as an integer.
How to approach it
Both edges are the same question, where the first timestamp at or after a value sits. Answer it once with a binary search and subtract.
Sample cases
+ 3 held back until you submit
a burst of events inside the window
The event at 1005 sits on start and is counted; the one at 1030 sits on end and is not.
Input
Argument 1
[
1000,
1005,
1010,
1010,
1020,
1030,
1045
]Argument 2
1005Argument 3
1030Returns
4duplicates on both boundaries
Both copies of 1200 are in and all three copies of 1260 are out, so the answer is 2.
Input
Argument 1
[
1200,
1200,
1260,
1260,
1260,
1300
]Argument 2
1200Argument 3
1260Returns
2an empty log
No events at all returns 0 rather than raising on an index into an empty list.
Input
Argument 1
[] (empty list)
Argument 2
1000Argument 3
2000Returns
0a window that runs backwards
start is after end, so the range holds nothing and the answer is 0.
Input
Argument 1
[
100,
200,
300
]Argument 2
300Argument 3
200Returns
0Constraints
timestamps is a list of integers sorted ascending. The same timestamp may appear several times in a row.t counts when start <= t < end. An event exactly at start is counted; an event exactly at end is not.start >= end the range is empty, so return 0.timestamps list returns 0.start and end do not have to be values that appear in the list.Worked example
Take [1000, 1005, 1010, 1010, 1020, 1030, 1045] with start 1005 and end 1030. A lower bound finds the first index whose value is at least the target.
Lower bound of 1005: low 0, high 7. Middle 3 holds 1010, which is not below 1005, so high becomes 3. Middle 1 holds 1005, not below 1005, so high becomes 1. Middle 0 holds 1000, below 1005, so low becomes 1. low meets high at index 1.
Lower bound of 1030: low 0, high 7. Middle 3 holds 1010, below 1030, so low becomes 4. Middle 5 holds 1030, not below, so high becomes 5. Middle 4 holds 1020, below, so low becomes 5. low meets high at index 5.
The answer is 5 - 1 = 4: the events at 1005, 1010, 1010 and 1020.
The trap is the boundary. Writing start <= t <= end counts the event at 1030 and returns 5, and in the case [1200, 1200, 1260, 1260, 1260, 1300] with range [1200, 1260) it returns 5 instead of 2, because all three copies of 1260 slip in.
What this tests
Binary search, specifically the lower bound: the first index whose value is at least a target. Python's bisect.bisect_left is the library version, but interviewers usually ask you to write it yourself, because keeping low < high and high = middle straight is the skill. This is LeetCode 'Search Insert Position' used twice. The target is O(log n) time and O(1) space. The linear scan passes the samples and costs a full pass per query at interview scale. Data engineers meet this when counting events in a window, slicing a sorted log file by time, or pruning sorted Parquet row groups by min and max. This exact question is not named in the data engineering interview reports we could find, but it is the lower-bound routine underneath 'Find First and Last Position', which is.
count_in_range(timestamps: list[int], start: int, end: int) -> intSubmit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.