Frontend School

Customer Service Queue with Timeouts

DSA
medium

Customer Service Queue with Timeouts

Medium
Queue
Data Structure Design
Time Complexity

Overview

Innovaccer plays a crucial role in enhancing healthcare operations by providing robust data platforms. A common challenge in managing healthcare services, such as patient support or provider query systems, is ensuring timely responses to incoming requests while adhering to strict service level agreements (SLAs). Requests that wait too long become stale and can negatively impact patient care or operational efficiency.

This problem challenges you to design a CustomerServiceQueue that simulates a simplified support system. The queue must prioritize requests on a first-in, first-out (FIFO) basis, but crucially, it must also automatically discard any requests that have exceeded their allotted timeoutDuration at the time of processing. This ensures that only actionable, non-stale requests are ever processed.

What you need to do / Task

Your task is to implement the CustomerServiceQueue class with the following methods:

  1. constructor(currentTime: number): Initializes the customer service queue with a starting currentTime.
  2. addRequest(requestId: number, arrivalTime: number, timeoutDuration: number): void: Adds a new customer service request to the queue. Each request has a unique requestId, an arrivalTime, and a timeoutDuration after which it becomes invalid.
  3. processNextValidRequest(currentTime: number): number | null: Attempts to process the next valid (non-timed-out) request from the queue. It should return the requestId of the processed request. If the queue is empty or all pending requests have timed out, it should return null.

Input & output

CustomerServiceQueue(currentTime: number)

  • currentTime: An integer representing the initial time when the queue system starts.

addRequest(requestId: number, arrivalTime: number, timeoutDuration: number): void

  • requestId: A unique positive integer identifying the request.
  • arrivalTime: An integer representing the time at which the request arrived in the system.
  • timeoutDuration: A non-negative integer representing the maximum time (in units) a request can wait before being considered timed out. A request r is timed out at current_time if r.arrivalTime + r.timeoutDuration <= current_time.
  • Returns: void

processNextValidRequest(currentTime: number): number | null

  • currentTime: An integer representing the current time when this method is called.
  • Returns: The requestId (integer) of the processed request, or null if no valid request could be processed.

Clarifications

  • The currentTime parameter passed to constructor and processNextValidRequest will always be non-decreasing.
  • Requests are processed strictly in FIFO order among those that have not timed out.
  • If timeoutDuration is 0, a request is considered timed out if currentTime is equal to or greater than its arrivalTime when processNextValidRequest is called.
  • When processNextValidRequest is called, you must first discard any requests at the front of the queue that have already timed out based on the provided currentTime, before attempting to process the next valid one.

Examples

1

Example 1

Input:

operations = ["CustomerServiceQueue","addRequest","addRequest","processNextValidRequest","addRequest","processNextValidRequest","processNextValidRequest"], params = [[0],[101,5,10],[102,7,5],[15],[103,12,3],[16],[20]]

Output:

[null,null,null,101,null,null,null]

Note:

  1. Initialize queue at time 0.
  2. Add request 101 (arrival 5, timeout 10). Valid until time 5+10=15.
  3. Add request 102 (arrival 7, timeout 5). Valid until time 7+5=12.
  4. Process at time 15: Request 101 (valid until 15) is processed. Request 102 (valid until 12) is timed out and discarded. Output: 101.
  5. Add request 103 (arrival 12, timeout 3). Valid until time 12+3=15.
  6. Process at time 16: Queue now has only request 103. It's timed out (valid until 15). Discarded. Output: null.
  7. Process at time 20: Queue is empty. Output: null.
2

Example 2

Input:

operations = ["CustomerServiceQueue","addRequest","addRequest","processNextValidRequest","processNextValidRequest","addRequest","processNextValidRequest"], params = [[100],[201,100,5],[202,102,0],[105],[105],[203,106,10],[110]]

Output:

[null,null,null,201,null,null,203]

Note:

  1. Initialize queue at time 100.
  2. Add request 201 (arrival 100, timeout 5). Valid until 100+5=105.
  3. Add request 202 (arrival 102, timeout 0). Valid until 102+0=102. Immediately timed out if processed at or after 102.
  4. Process at time 105: Request 201 (valid until 105) is processed. Request 202 (valid until 102) is timed out and discarded. Output: 201.
  5. Process at time 105: Queue is now empty. Output: null.
  6. Add request 203 (arrival 106, timeout 10). Valid until 106+10=116.
  7. Process at time 110: Request 203 (valid until 116) is processed. Output: 203.
3

Example 3

Input:

operations = ["CustomerServiceQueue","addRequest","addRequest","addRequest","processNextValidRequest","processNextValidRequest"], params = [[10],[301,10,2],[302,11,1],[303,12,0],[13],[13]]

Output:

[null,null,null,null,null,null]

Note:

  1. Initialize queue at time 10.
  2. Add request 301 (arrival 10, timeout 2). Valid until 10+2=12.
  3. Add request 302 (arrival 11, timeout 1). Valid until 11+1=12.
  4. Add request 303 (arrival 12, timeout 0). Valid until 12+0=12.
  5. Process at time 13:
    • Request 301 (valid until 12) is timed out. Discard.
    • Request 302 (valid until 12) is timed out. Discard.
    • Request 303 (valid until 12) is timed out. Discard.
    • Queue is now empty. Output: null.
  6. Process at time 13: Queue is still empty. Output: null.

Constraints

Constraints & assumptions

  • 1 <= requestId <= 10^9
  • 0 <= arrivalTime, timeoutDuration, currentTime <= 10^9
  • currentTime passed to processNextValidRequest will always be >= the currentTime used in the constructor and any arrivalTime of added requests.
  • The number of calls to addRequest and processNextValidRequest will not exceed 10^5.
  • requestIds are unique.

Out of scope

  • Complex priority schemes (e.g., based on request type or severity).
  • Support for multiple service agents processing requests concurrently.
  • Persistent storage for requests beyond the class instance's lifetime.

What interviewers evaluate

  • Correctness of Logic: Accurately implements FIFO processing while respecting timeout conditions.
  • Edge Case Handling: Properly handles scenarios like an empty queue, all requests being timed out, or immediate timeouts.
  • Efficiency: Uses appropriate data structures and algorithms to ensure addRequest and processNextValidRequest operate efficiently, ideally in O(1) amortized time for addRequest and O(k) where k is the number of timed-out requests discarded for processNextValidRequest.
  • Code Quality: Demonstrates clean, readable, and well-structured code with appropriate variable names.

Loading editor...