How should I practice Smallest Batch Size Within a Step Limit?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Smallest Batch Size Within a Step Limit associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Smallest Batch Size Within a Step Limit

Microsoft● MediumINTERNONSITE INTERVIEW

Problem statement

Source note: This came from the easier of two Microsoft summer intern interviews. Each number in a list needs as many passes as the number divided by the batch size, rounded up, and the goal is a batch size that keeps the total within a limit called maxBatchCount. The candidate used binary search and slipped on one detail, the lower end of the search range.

The post describes the goal in two ways that do not agree: once as the fewest passes and once as the biggest batch size. A bigger batch never adds passes, so here you return the smallest batch size that fits. The post words the limit strictly, as a total below maxBatchCount. This version chooses to also allow a total equal to it, because the name reads as a maximum. The post gives no sizes at all. The limits here are a practice choice: up to 10^5 numbers from 1 to 10^9, and maxBatchCount from the list length up to 10^9, so an answer always exists.

The judged task matches the report at about 80%.

You are given an integer array sizes and an integer maxBatchCount.

You pick one positive integer batch size b. Each number x in sizes is processed b at a time, so it needs x / b steps, rounded up. For example, with b = 4 the number 5 needs 2 steps and the number 3 needs 1 step.

The total number of steps is the sum over all numbers in sizes. Return the smallest batch size b for which the total is at most maxBatchCount.

Such a batch size always exists: when b is the largest number in sizes, every number needs one step, and maxBatchCount is at least the number of elements.

Function

minBatchSize(sizes: int[], maxBatchCount: int) → int

Examples

Example 1

sizes = [1,3,5,5]maxBatchCount = 6return = 3

With batch size 2 the steps are 1, 2, 3, 3, which is 9 steps, more than 6. With batch size 3 the steps are 1, 1, 2, 2, which is exactly 6 steps, so it is allowed. Batch size 4 also gives 1, 1, 2, 2 = 6 steps, but 3 is smaller, so the answer is 3.

Example 2

sizes = [1,3,5,5]maxBatchCount = 4return = 5

Only 4 steps are allowed for 4 numbers, so every number must finish in one step. That needs a batch size of at least 5, the largest number. With batch size 4 the steps are 1, 1, 2, 2 = 6, which is too many. The answer is 5.

Example 3

sizes = [9,2,4]maxBatchCount = 15return = 1

With batch size 1 each number needs as many steps as its value: 9 + 2 + 4 = 15. That fits the limit of 15, so the answer is 1.

Constraints

1 <= sizes.length <= 10^5
1 <= sizes[i] <= 10^9
sizes.length <= maxBatchCount <= 10^9