Count Requests Dropped by Multiple Time Windows

Question

The candidate is asked to write a function that counts the number of requests dropped over multiple time windows based on given timestamps.

Codemia · Accepted Answer

To solve the problem of counting dropped requests over multiple time windows, we need to define the input format clearly. We will receive a list of timestamps representing requests and a time window duration. Our goal is to determine how many requests fall outside of the allowed time window for each request.

We will use a sliding window technique to efficiently count the dropped requests. The idea is to maintain a window of valid timestamps, and for each timestamp, we will check how many requests fall outside this window. This will help us avoid a nested loop and reduce the time complexity.

Here is a Python implementation of the solution:

```python
def count_dropped_requests(timestamps, window):
    dropped_count = 0
    n = len(timestamps)
    start = 0

for end in range(n):
        while timestamps[end] - timestamps[start] > window:
            start += 1
        dropped_count += (end - start) - 1  # Count requests dropped in the window

return dropped_count
```
This function iterates through the timestamps while maintaining a valid window of requests.

The time complexity of this solution is O(n) because each timestamp is processed at most twice (once when expanding the end of the window and once when moving the start). The space complexity is O(1) since we are using a constant amount of extra space.

It's important to consider edge cases such as:
1. An empty list of timestamps should return 0.
2. All timestamps falling within the same time window should also return 0.
3. Timestamps that are all outside the window should return the total count of requests.

Count Requests Dropped by Multiple Time Windows

Oracle

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

Approach

Submit Your Answer

Oracle Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string