Count requests dropped when incoming requests exceed available server threads
Company: J.P. Morgan
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A server receives a sequence of events, given as an integer array `events` and processed from left to right:
- A positive value `k` means `k` new threads become available.
- The value `-1` means a request arrives. If at least one thread is available, the request uses one thread, and that thread never becomes available again. If no thread is available, the request is dropped.
Return the total number of dropped requests.
### Function Signature
```python
def count_dropped_requests(events: list[int]) -> int:
```
### Rules
- The server starts with zero available threads.
- Threads are consumed permanently; finishing a request never returns its thread.
- Threads that become available later cannot serve a request that was already dropped.
- Every element of `events` is either `-1` or a positive integer.
### Constraints
- `1 <= len(events) <= 10^5`
- Each `events[i]` is `-1` or satisfies `1 <= events[i] <= 10^9`.
- The number of available threads can grow to about `10^14`, which exceeds `2^31 - 1`; Python integers handle this, but other languages need 64-bit integers.
- The answer is an integer between `0` and `len(events)`.
### Examples
**Example 1**
```text
Input: events = [1, -1, -1, 2, -1, -1, -1]
Output: 2
```
One thread arrives and serves the first request. The second request finds no thread and is dropped. Two threads arrive and serve the next two requests, and the last request is dropped.
**Example 2**
```text
Input: events = [-1, -1, 3, -1]
Output: 2
```
The first two requests arrive before any thread exists and are dropped. The last request uses one of the three threads.
**Example 3**
```text
Input: events = [5, -1, -1]
Output: 0
```
Both requests are served, and three threads remain unused.
Overview: Simulate a server that receives thread additions and incoming requests as an integer array, where each request permanently consumes one available thread or is dropped, and return how many requests are dropped. It tests careful single-pass array simulation, event ordering, and awareness of integer overflow.
Read the full J.P. Morgan Software Engineer interview experience this question came from
A server receives a sequence of events, given as an integer array `events`, and processes them from left to right:
- A positive value `k` means `k` new threads become available.
- The value `-1` means a request arrives. If at least one thread is available, the request uses one thread, and that thread never becomes available again. If no thread is available, the request is dropped.
Implement `count_dropped_requests(events)`, which returns the total number of dropped requests.
**Rules**
- The server starts with zero available threads.
- Threads are consumed permanently; finishing a request never returns its thread.
- Threads that become available later cannot serve a request that was already dropped.
- Every element of `events` is either `-1` or a positive integer.
**Constraints**
- `1 <= len(events) <= 10^5`
- Each `events[i]` is `-1` or satisfies `1 <= events[i] <= 10^9`.
- The number of available threads can grow to about `10^14`, which exceeds `2^31 - 1`. Python integers handle this; Java must hold it in a `long` and C++ in a `long long` (JavaScript numbers stay exact because it is below `2^53`). Each individual element and the returned count fit in a 32-bit `int`.
- The answer is an integer between `0` and `len(events)`.
**Example 1**
```text
Input: events = [1, -1, -1, 2, -1, -1, -1]
Output: 2
```
One thread arrives and serves the first request. The second request finds no thread and is dropped. Two threads arrive and serve the next two requests, and the last request is dropped.
**Example 2**
```text
Input: events = [-1, -1, 3, -1]
Output: 2
```
The first two requests arrive before any thread exists and are dropped. The last request uses one of the three threads.
Constraints
- 1 <= len(events) <= 10^5
- Each events[i] is -1 or satisfies 1 <= events[i] <= 10^9.
- The number of available threads can grow to about 10^14, which exceeds 2^31 - 1; Python integers handle this, but other languages need 64-bit integers (Java long, C++ long long).
- The answer is an integer between 0 and len(events).
Examples
Input: ([1, -1, -1, 2, -1, -1, -1],)
Expected Output: 2
Explanation: Source Example 1: one thread serves the first request, the second is dropped, two threads serve the next two, and the last is dropped.
Input: ([-1, -1, 3, -1],)
Expected Output: 2
Explanation: Source Example 2: two requests arrive before any thread and are dropped; the later grant of 3 serves only the last request.
Hints
- Process the events strictly in the given order: a request can only use threads that were granted before it arrived.
- Think about what the server must remember between events, and how that changes when a request is served versus dropped.
- The running number of available threads can exceed 2^31 - 1, so choose a numeric type wide enough to hold it.