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.

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

Hints

  1. 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.
  2. 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.
  3. 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).

Hints

  1. 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).
  2. 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.
  3. 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].

Loading coding console...