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.

Solve minimum rate and subset sum | Uber Coding Question

Solve minimum rate and subset sum

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

1) Minimum rate to finish vaults within a deadline: You are given an array vaults of positive integers representing the amount in each vault along a row. Each hour, the robber can work on exactly one vault and steal up to k units from that vault during that hour; excess capacity cannot be transferred to other vaults. The time to finish a vault of size v at rate k is ceil(v/k) hours. Given vaults = [3, 6, 7, 11] and h = 8, compute the minimum integer rate k such that all vaults can be emptied within h hours. Describe an efficient algorithm and analyze its time and space complexity. 2) Subset equals target sum: Given the integer set {2, 5, 3, 11} and a target sum 10, determine whether some (or all) of the integers can be selected so that their sum equals the target. Return true/false and outline your approach and complexity.

Quick Answer: This question evaluates algorithmic problem-solving skills by combining resource-rate scheduling for finishing workloads within a deadline and combinatorial subset-sum decision-making, while requiring formal time and space complexity analysis.

Minimum Rate to Empty All Vaults

You are given an array `vaults` of positive integers representing the amount of money in each vault along a row, and an integer `h` (the number of hours available). Each hour, the robber can work on exactly one vault and steal up to `k` units from that vault during that hour; excess capacity within an hour cannot be transferred to another vault. The time to fully empty a vault of size `v` at rate `k` is `ceil(v / k)` hours. Return the minimum integer rate `k` such that all vaults can be emptied within `h` hours. Example: vaults = [3, 6, 7, 11], h = 8 -> answer is 4 (at k=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 <= 8). This is the classic 'Koko Eating Bananas' pattern: the hours-needed function is monotonically non-increasing in k, so binary search the smallest feasible rate.

Constraints

1 <= vaults.length <= 10^5
1 <= vaults[i] <= 10^9
vaults.length <= h <= 10^9 (h is at least the number of vaults, so a feasible rate always exists)

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 <= 8. At k=3 it would be 1+2+3+4 = 10 > 8, so 4 is minimal.

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

Expected Output: 30

Explanation: With only 5 hours for 5 vaults, each vault must finish in exactly 1 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 of slack, k=23 gives ceil(30/23)+1+1+1+1 = 2+1+1+1+1 = 6 <= 6; k=22 needs ceil(30/22)+ceil(23/22)+... = 2+2+1+1+1 = 7 > 6.

Input: ([312884470], 968709470)

Expected Output: 1

Explanation: A single vault with far more hours than units: rate 1 empties it in 312884470 hours, well within the deadline.

Input: ([1], 1)

Expected Output: 1

Explanation: Smallest case: one vault of size 1 in one hour needs rate 1.

Input: ([1000000000], 2)

Expected Output: 500000000

Explanation: One billion units in 2 hours: ceil(1e9/5e8) = 2 hours; rate 499999999 would need 3 hours, so 500000000 is minimal (boundary on large values).

Hints

The number of hours required is a monotonic function of the rate k: a larger k never increases the total hours. This monotonicity is exactly what enables binary search.
Search the integer rate over the range [1, max(vaults)]. For a candidate k, the total hours are sum(ceil(v/k)) over all vaults. Use ceil(v/k) = (v + k - 1) // k to avoid floating point.
Find the smallest k for which total hours <= h. The lower bound is 1 (at least 1 unit/hour) and the upper bound is max(vaults) (one vault per hour is always feasible since h >= number of vaults).

Subset Equals Target Sum

Given an array of integers `nums` and an integer `target`, determine whether some subset of the elements (possibly empty, possibly all) can be selected so that their sum equals `target`. Each element may be used at most once. Return `true` if such a subset exists, otherwise `false`. Example: nums = [2, 5, 3, 11], target = 10 -> true (2 + 3 + 5 = 10). This is the classic Subset Sum decision problem, solvable with dynamic programming over reachable sums. The inputs here are non-negative; the empty subset sums to 0, so target = 0 is always reachable.

Constraints

0 <= nums.length <= 200
1 <= nums[i] <= 1000 (non-negative integers)
0 <= target <= 200000
The empty subset is allowed, so target = 0 is always achievable.

Examples

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

Expected Output: True

Explanation: 2 + 5 + 3 = 10, so a valid subset exists.

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

Expected Output: False

Explanation: No subset of {2,5,3,11} sums to 4 (2+anything overshoots or undershoots; 3 alone is 3, 2 alone is 2).

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

Expected Output: True

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

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

Expected Output: True

Explanation: The single element 11 equals the target.

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

Expected Output: True

Explanation: The full set 2+5+3+11 = 21 is the maximum reachable sum.

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

Expected Output: False

Explanation: 22 exceeds the total of all elements (21), so it is unreachable.

Input: ([], 0)

Expected Output: True

Explanation: Empty input with target 0: the empty subset trivially works.

Input: ([], 7)

Expected Output: False

Explanation: Empty input cannot form any positive sum.

Input: ([7], 7)

Expected Output: True

Explanation: Single element equals the target.

Input: ([7], 3)

Expected Output: False

Explanation: Single element 7 cannot form 3.

Hints

Frame it as a reachability problem: track the set of sums you can form using a prefix of the elements. Start with {0} (the empty subset).
For each new number n, every previously reachable sum s gives a new reachable sum s + n. Discard sums that exceed target, since the values are non-negative and can never come back down.
The standard formulation is a boolean DP array dp[0..target] where dp[j] means sum j is reachable; iterate j downward when updating in place to ensure each element is used at most once. Return dp[target].

Quick Overview

This question evaluates algorithmic problem-solving skills by combining resource-rate scheduling for finishing workloads within a deadline and combinatorial subset-sum decision-making, while requiring formal time and space complexity analysis.