Frontend School

Minimize Max Processor Time

DSA
hard

Minimize Max Processor Time

Hard
Binary Search
Arrays
Greedy

Overview

Phonepe is enhancing its real-time payment settlement infrastructure to handle peak loads more efficiently. A critical component involves processing large batches of pending transactions. Each transaction has a specific, immutable processing duration. To optimize throughput and minimize latency, these transactions must be distributed among a fixed number of parallel processing units. The goal is to find the most efficient distribution such that the maximum time any single processing unit is busy is minimized. This problem directly impacts system performance and user experience during high-volume periods.

What you need to do / Task

You are tasked with implementing a function that determines the minimum possible value for the maximum processing time any single unit will experience.

  1. Implement the minMaxProcessorTime function.
  2. The function should take an array of transaction durations and the number of available processing units as input.
  3. It must return the minimum possible value for the maximum processing time across all units.

Input & output

Function Signature: function minMaxProcessorTime(transactionDurations: number[], numProcessors: number): number

  • transactionDurations: An array of positive integers, where transactionDurations[i] represents the time required to process the i-th transaction.
  • numProcessors: A positive integer representing the number of parallel processing units available.

Return Value:

  • A single integer representing the minimum possible value of the maximum processing time experienced by any single processing unit.

Clarifications

  • Single Processor: If numProcessors is 1, all transactions must be processed by that single unit, so the minimum maximum time is the sum of all transaction durations.
  • All Processors Utilized: If numProcessors is equal to transactionDurations.length, each transaction can be assigned to its own processor. In this scenario, the minimum maximum time will be the duration of the longest single transaction.

Examples

1

Example 1

Input:

transactionDurations = [10, 20, 30, 40], numProcessors = 2

Output:

60

Note:

With 2 processors, we can split tasks as [10, 20, 30] (total 60) and [40] (total 40). The maximum time for any processor is 60. It's impossible to achieve a maximum time less than 60.

2

Example 2

Input:

transactionDurations = [1, 2, 3, 4, 5, 6, 7, 8, 9], numProcessors = 3

Output:

17

Note:

Tasks can be distributed as: P1: [1, 2, 3, 4, 5] (sum=15), P2: [6, 7] (sum=13), P3: [8, 9] (sum=17). The maximum time is 17. Any distribution resulting in a max time less than 17 would require more than 3 processors.

3

Example 3

Input:

transactionDurations = [100, 20, 50], numProcessors = 3

Output:

100

Note:

Since there are 3 processors and 3 transactions, each transaction can be assigned to its own processor. The maximum time will be the duration of the longest transaction, which is 100.

Constraints

Constraints & assumptions

  • 1 <= transactionDurations.length <= 10^5
  • 1 <= transactionDurations[i] <= 10^9
  • 1 <= numProcessors <= transactionDurations.length
  • The sum of transactionDurations will not exceed 10^{14}.
  • All transactionDurations[i] are integers.

What interviewers evaluate

  • Correctness and Optimality: The solution correctly identifies the minimum possible maximum processing time, handles edge cases, and uses an optimal algorithm (e.g., binary search) for the given constraints.
  • Algorithm Design: Demonstrates a clear understanding of binary search on the answer and the ability to formulate an efficient check function (the canProcess helper).
  • Code Quality: Writes clean, readable, and well-structured code with appropriate variable names and comments where necessary.
  • Problem-Solving Approach: Ability to break down the problem, identify the core algorithmic pattern, and arrive at a solution within the time budget.

Loading editor...