Frontend School

Buffered Priority Processor

DSA
hard

Buffered Priority Processor

Hard
Queue
Scheduling
Simulation
Data Structures

Overview

Snap's backend infrastructure handles a diverse array of user requests, ranging from real-time message delivery to background data processing. Efficiently managing these varied tasks on shared processing units is critical for maintaining system responsiveness and optimizing resource utilization. This problem simulates a core aspect of such a system: processing a stream of requests with distinct priorities and specific cooldown requirements on a single processing unit.

What you need to do / Task

Implement a function that simulates a single-core processor managing a stream of incoming requests. The processor must adhere to specific priority rules and a cooldown mechanism for high-priority tasks. Your function should return the order in which requests are completed and their respective finish times.

Input & output

Function Signature:

function processRequests(requests: Request[], cooldownPeriod: number): Result[];

Input:

  • requests: An array of Request objects, where each Request is a tuple [id: number, arrivalTime: number, processingTime: number, priority: 'NORMAL' | 'HIGH'].
    • id: A unique identifier for the request (positive integer).
    • arrivalTime: The time (non-negative integer) at which the request becomes available for processing.
    • processingTime: The duration (positive integer) required to process this request.
    • priority: The priority level, either 'NORMAL' or 'HIGH'.
  • cooldownPeriod: A non-negative integer representing the duration after a HIGH priority task finishes, during which another HIGH priority task cannot start. NORMAL priority tasks can still be processed during this cooldown.

Output:

  • Returns an array of Result tuples [id: number, finishTime: number]. Each tuple represents a completed request, ordered by its finishTime. If two requests finish at the same time, their relative order in the output should match their processing start order.

Clarifications

  • The requests array is guaranteed to be sorted by arrivalTime in ascending order. If two requests have the same arrivalTime, their relative order in the input array should be maintained (i.e., the one appearing first is considered to have 'arrived' first).
  • The processor can only handle one request at a time.
  • If the processor is free but no requests are available (either because they haven't arrived yet, or all HIGH priority tasks are in cooldown and no NORMAL tasks are pending), the processor remains idle until a task becomes available.
  • At any given time, if multiple tasks are ready to be processed:
    1. HIGH priority tasks are always preferred over NORMAL priority tasks, provided the HIGH priority cooldown is not active.
    2. Among tasks of the same priority, the one that arrived earliest (smallest arrivalTime) should be processed first. If arrivalTime is also the same, use the order from the input requests array (which implies using their id as a tie-breaker if ids are sequential).
  • The system starts at time 0.
  • All time values are discrete integers.

Examples

1

Example 1

Input:

requests = [[1, 0, 3, 'NORMAL'], [2, 1, 2, 'HIGH']], cooldownPeriod = 0

Output:

[[1, 3], [2, 5]]

Note:

Time 0: Request 1 (NORMAL) arrives. Processor starts R1. Time 1: Request 2 (HIGH) arrives. Time 3: Request 1 finishes. Processor free. R2 is available. Processor starts R2. Time 5: Request 2 finishes.

2

Example 2

Input:

requests = [[1, 0, 2, 'HIGH'], [2, 1, 1, 'NORMAL'], [3, 2, 3, 'HIGH']], cooldownPeriod = 2

Output:

[[1, 2], [2, 3], [3, 7]]

Note:

Time 0: Request 1 (HIGH) arrives. Processor starts R1. Time 1: Request 2 (NORMAL) arrives. Time 2: Request 1 finishes. Cooldown for HIGH starts (ends at 2+2=4). Processor free. R2 is available. Processor starts R2. Time 2: Request 3 (HIGH) arrives. Time 3: Request 2 finishes. Processor free. R3 is available but HIGH cooldown is active (ends at 4). No NORMAL tasks. Processor idles. Time 4: Cooldown ends. Processor free. R3 is available. Processor starts R3. Time 7: Request 3 finishes.

3

Example 3

Input:

requests = [[10, 0, 1, 'NORMAL'], [20, 0, 1, 'NORMAL'], [30, 2, 2, 'HIGH']], cooldownPeriod = 1

Output:

[[10, 1], [20, 2], [30, 4]]

Note:

Time 0: R10, R20 (both NORMAL) arrive. R10 processed first (earlier in input). Time 0-1: Process R10. Time 1: R10 finishes. Processor free. R20 available. Process R20. Time 1-2: Process R20. Time 2: R20 finishes. Processor free. R30 (HIGH) arrives. Cooldown for HIGH is not active. Process R30. Time 2-4: Process R30. Time 4: R30 finishes.

Constraints

Constraints & assumptions

  • 1 <= requests.length <= 10^5
  • 0 <= arrivalTime < 10^9
  • 1 <= processingTime <= 10^4
  • ids are unique positive integers.
  • priority is either 'NORMAL' or 'HIGH'.
  • 0 <= cooldownPeriod <= 10^4
  • The requests array is sorted by arrivalTime.
  • All times are non-negative integers.
  • The system starts at time 0.

Out of scope

  • Multi-core processing or parallel execution.
  • Preemptive scheduling (once a task starts, it runs to completion).
  • Dynamic changes to request priorities or cooldown periods.

What interviewers evaluate

  • Correctly modeling the processor state, including current time, processor availability, and cooldown status.
  • Efficiently managing incoming requests and distinguishing between HIGH and NORMAL priority queues.
  • Accurate implementation of the priority and cooldown logic to select the next task.
  • Handling edge cases such as an empty request list, zero cooldown, or periods of processor idleness.

Loading editor...