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.

Hints

  1. 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.
  2. 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.
  3. 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.
  4. Edge case: when H equals the number of piles, every pile must finish in exactly one hour, forcing R = max(piles).

Loading coding console...