Katkat
Back

Count requests dropped when incoming requests exceed available server threads

J.P. MorganSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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

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

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

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

Input: events = [5, -1, -1]
Output: 0

Both requests are served, and three threads remain unused.