How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Apple during technical interviews.

Find Minimum Processing Rate | Apple Coding Question

Find Minimum Processing Rate

Company: Apple

Role: Machine Learning Engineer

Category: Coding & Algorithms

Interview Round: Technical Screen

You are given an array `piles`, where `piles[i]` is the number of items in the `i`-th pile, and an integer `h` representing the maximum number of hours available. Each hour, a worker chooses exactly one non-empty pile and processes up to `k` items from that pile. If the pile has fewer than `k` items remaining, the worker finishes the pile during that hour and does not use the remaining capacity on another pile. Return the minimum positive integer processing rate `k` such that all piles can be finished within `h` hours. Example: ```text Input: piles = [3, 6, 7, 11], h = 8 Output: 4 ``` Explanation: With `k = 4`, the required hours are `ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8`.

Quick Answer: This question evaluates algorithmic problem-solving skills, discrete mathematics involving integer division and ceiling operations, and complexity analysis for optimizing a processing rate under a time constraint.

You are given an array `piles`, where `piles[i]` is the number of items in the `i`-th pile, and an integer `h` representing the maximum number of hours available. Each hour, a worker chooses exactly one non-empty pile and processes up to `k` items from that pile. If the pile has fewer than `k` items remaining, the worker finishes that pile during the hour and cannot use the leftover capacity on another pile. Return the minimum positive integer processing rate `k` such that all piles can be finished within `h` hours.

Constraints

1 <= len(piles) <= 100000
1 <= piles[i] <= 1000000000
len(piles) <= h <= 1000000000

Examples

Input: ([3, 6, 7, 11], 8)

Expected Output: 4

Explanation: At rate 4, the total time is 1 + 2 + 2 + 3 = 8 hours, which fits exactly. Any smaller rate takes more than 8 hours.

Input: ([30, 11, 23, 4, 20], 5)

Expected Output: 30

Explanation: There are 5 piles and only 5 hours, so each pile must be finished in one hour. The rate must therefore be at least the largest pile size, 30.

Input: ([30, 11, 23, 4, 20], 6)

Expected Output: 23

Explanation: At rate 23, the hours needed are 2 + 1 + 1 + 1 + 1 = 6. At rate 22, the total becomes 7, which is too slow.

Input: ([1], 1)

Expected Output: 1

Explanation: With a single pile of size 1 and one hour available, the minimum valid rate is 1.

Input: ([5, 5, 5, 5], 8)

Expected Output: 3

Explanation: At rate 3, each pile takes 2 hours, for a total of 8. At rate 2, each pile takes 3 hours, totaling 12.

Input: ([1000000000], 2)

Expected Output: 500000000

Explanation: A single pile of 1,000,000,000 items must be finished in 2 hours, so the smallest rate is 500,000,000.

Hints

For a fixed rate `k`, you can compute the total hours needed by summing `ceil(pile / k)` for every pile.
If a rate `k` is fast enough, then any rate larger than `k` will also be fast enough. This monotonic property suggests binary search.

Quick Overview

This question evaluates algorithmic problem-solving skills, discrete mathematics involving integer division and ceiling operations, and complexity analysis for optimizing a processing rate under a time constraint.