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.

Hints

  1. If a rate k works, any rate larger than k also works — so the feasibility is monotonic and you can binary search on k.
  2. For a given rate k, the hours needed for one vault of size p is ceil(p / k); sum these across all vaults.
  3. 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).
  4. 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.

Hints

  1. Maintain the set of all sums reachable by some subset, starting from {0} (the empty subset).
  2. For each new number x, every previously reachable sum s yields a new reachable sum s + x — union these into the set.
  3. You can return early the moment `target` appears in the reachable set.
  4. 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.

Loading coding console...