Solve minimum rate and subset sum
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.
Uber
Sep 6, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
0
0
- 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.
- 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.