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 difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Find minimum processing rate | DoorDash Coding Question

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find minimum processing rate states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Find minimum processing rate

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

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 (total hours). Find the minimum integer rate R such that processing R items per hour lets you finish all piles within H hours. Assume you process one pile at a time and round up hours per pile. Describe the algorithm, prove correctness, and give time/space complexity.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find minimum processing rate states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given an integer array `piles` where `piles[i]` is the number of items in the i-th pile, and an integer `H` representing the total hours available. A worker processes items at a fixed integer rate `R` items per hour. Each hour the worker picks a single pile and processes up to `R` items from it. If a pile has fewer than `R` items remaining, the worker finishes that pile this hour and does NOT move on to another pile in the same hour (one pile per hour). Equivalently, a pile of size `p` takes `ceil(p / R)` hours. Return the minimum integer rate `R` such that all piles can be finished within `H` hours. It is guaranteed that `H >= piles.length`, so an answer always exists. Example: - piles = [3, 6, 7, 11], H = 8 -> 4. At R=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 <= 8. R=3 needs 1+2+3+4 = 10 > 8. This is the classic 'Koko Eating Bananas' binary-search-on-the-answer problem.

Constraints

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

Examples

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

Expected Output: 4

Explanation: At R=4: 1+2+2+3 = 8 hours <= 8. At R=3: 1+2+3+4 = 10 > 8, so 4 is the minimum.

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

Expected Output: 30

Explanation: H equals the number of piles (5), so each pile must be cleared in exactly one hour. The rate must be at least the largest pile, 30.

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

Expected Output: 23

Explanation: With one extra hour the rate can drop to 23: ceil(30/23)+ceil(11/23)+ceil(23/23)+ceil(4/23)+ceil(20/23) = 2+1+1+1+1 = 6 <= 6, and 22 would need 7 hours.

Input: ([1], 1)

Expected Output: 1

Explanation: Single pile of 1 item in 1 hour needs rate 1.

Input: ([1000000000], 2)

Expected Output: 500000000

Explanation: One huge pile must be split across 2 hours: ceil(1e9 / 5e8) = 2. Rate 499999999 would need 3 hours.

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

Expected Output: 5

Explanation: Four equal piles in exactly four hours forces clearing each in one hour, so rate = 5.

Input: ([312884470], 312884469)

Expected Output: 2

Explanation: A near-boundary big pile with one fewer hour than items: at R=2 it takes ceil(312884470/2)=156442235 <= 312884469 hours, and R=1 takes 312884470 > 312884469. So the minimum rate is 2.

Hints

The answer R lies in the range [1, max(piles)]: rate 1 always finishes (it just may take too many hours), and any rate above max(piles) gives the same hour count as max(piles) since each pile already takes 1 hour.
Define f(R) = sum(ceil(p / R) for p in piles), the total hours at rate R. f is monotonically non-increasing in R: a faster rate never needs more hours. This monotonicity is exactly what makes binary search correct.
Binary search for the smallest R with f(R) <= H. Compute ceil(p / R) without floating point as (p + R - 1) // R to avoid precision bugs at large values.
Edge case: when H equals the number of piles, every pile must finish in exactly one hour, forcing R = max(piles).

Quick Overview