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 Uber.

What role is this question designed for?

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

Find minimal rate k and subset sum | Uber Coding Question

Quick Overview

This question evaluates algorithmic problem-solving skills, specifically search/optimization techniques for finding a minimal feasible rate and combinatorial reasoning for subset-sum problems, drawing on concepts such as binary-search-on-answer and dynamic programming.

Find minimal rate k and subset sum

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question LeetCode 875. Koko Eating Bananas — Given vault sizes [3, 6, 7, 11] and time h = 8 hours, find the minimum integer rate k (vault units per hour) so the robber finishes within h hours. Given integer set {2, 5, 3, 11} and target 10, decide if any subset sums to the target (subset-sum / N-sum). https://leetcode.com/problems/koko-eating-bananas/description/

Quick Answer: This question evaluates algorithmic problem-solving skills, specifically search/optimization techniques for finding a minimal feasible rate and combinatorial reasoning for subset-sum problems, drawing on concepts such as binary-search-on-answer and dynamic programming.

Minimum Eating Rate (Koko Eating Bananas)

Given an array `piles` where `piles[i]` is the size of the i-th vault (number of banana/units inside) and an integer `h` representing the number of hours available, find the minimum integer eating rate `k` (units per hour) so that all vaults are emptied within `h` hours. Each hour the robber picks one vault and removes up to `k` units from it. If the vault has fewer than `k` units remaining, the rest of that hour is wasted (the robber does not move on to another vault in the same hour). Return the smallest integer `k` such that the total hours needed is at most `h`. This is LeetCode 875 (Koko Eating Bananas) reframed: the answer is found by binary search over the candidate rate, since the total hours required is monotonically non-increasing in `k`. Example: piles = [3, 6, 7, 11], h = 8 -> 4 (at k=4 the hours are ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 <= 8).

Constraints

1 <= len(piles) <= 10^4
len(piles) <= h <= 10^9
1 <= piles[i] <= 10^9
The answer is guaranteed to be a positive integer in [1, max(piles)].

Examples

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

Expected Output: 4

Explanation: At k=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 hours <= 8. k=3 would need 9 hours, so 4 is minimal.

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

Expected Output: 30

Explanation: With only 5 hours and 5 vaults, each vault must be finished in exactly one hour, so k must be at least the largest vault, 30.

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

Expected Output: 23

Explanation: With 6 hours there is one extra hour of slack; k=23 lets the 30-vault take 2 hours while every other vault takes 1, totaling 6 hours.

Input: ([1], 1)

Expected Output: 1

Explanation: A single vault of size 1 in 1 hour needs rate 1.

Input: ([1000000000], 2)

Expected Output: 500000000

Explanation: One vault of a billion units in 2 hours needs rate ceil(1e9/2) = 500000000.

Input: ([312884470], 968709470)

Expected Output: 1

Explanation: Far more hours than units, so the minimum rate of 1 suffices (boundary on the low side).

Hints

If a rate k works, any rate larger than k also works — so the feasibility is monotonic and you can binary search on k.
For a given rate k, the hours needed for one vault of size p is ceil(p / k); sum these across all vaults.
Search k in [1, max(piles)]: the lower bound is 1 (always need at least 1 unit/hour), the upper bound is max(piles) (eating the biggest vault in one hour).
Use the 'find the leftmost feasible value' binary-search template: move hi = mid when feasible, lo = mid + 1 otherwise.

Subset Sum (does any subset reach the target?)

Given an array `nums` of integers and an integer `target`, decide whether any subset of `nums` sums exactly to `target`. Return `True` if such a subset exists, otherwise `False`. The empty subset is allowed and sums to 0, so `target = 0` is always reachable. This is the classic subset-sum / N-sum decision problem. Example: nums = [2, 5, 3, 11], target = 10 -> True (the subset {2, 3, 5} sums to 10). For target = 4 with the same set -> False (no subset of {2, 5, 3, 11} sums to 4).

Constraints

0 <= len(nums) <= 10^3 (algorithm scales with the range of reachable sums)
nums[i] may be any integer; with only non-negative values a 1-D boolean DP over [0, target] is the standard pseudo-polynomial approach
target may be any integer
The empty subset sums to 0, so target = 0 always returns True.

Examples

Input: ([2, 5, 3, 11], 10)

Expected Output: True

Explanation: The subset {2, 3, 5} sums to 10.

Input: ([2, 5, 3, 11], 4)

Expected Output: False

Explanation: No subset of {2, 5, 3, 11} sums to 4.

Input: ([2, 5, 3, 11], 0)

Expected Output: True

Explanation: The empty subset sums to 0, so target 0 is always reachable.

Input: ([], 0)

Expected Output: True

Explanation: Empty input, target 0 — the empty subset works (boundary).

Input: ([], 7)

Expected Output: False

Explanation: Empty input cannot reach any nonzero target.

Input: ([7], 7)

Expected Output: True

Explanation: Single element equal to the target.

Input: ([1, 2, 3], 6)

Expected Output: True

Explanation: The full set {1, 2, 3} sums to 6.

Input: ([4, 8, 15], 12)

Expected Output: True

Explanation: The subset {4, 8} sums to 12.

Hints

Maintain the set of all sums reachable by some subset, starting from {0} (the empty subset).
For each new number x, every previously reachable sum s yields a new reachable sum s + x — union these into the set.
You can return early the moment `target` appears in the reachable set.
If all values are non-negative and target is bounded, an equivalent O(n * target) boolean DP `dp[s] = True if some subset sums to s` is the textbook pseudo-polynomial solution.

Quick Overview