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 vault rate and subset-sum | Uber Coding Question

Quick Overview

This question evaluates algorithmic problem-solving and complexity-analysis skills, focusing on optimization for rate-limited resource allocation and combinatorial subset selection.

Solve vault rate and subset-sum

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

1) Robber vaults rate: You are given an array vaults of positive integers where vaults[i] is the amount in the i-th vault, and an integer h (hours). In each hour you may steal from only one vault, removing up to k units from that single vault; you cannot split the hourly effort across multiple vaults. Find the minimum integer rate k such that all vaults are emptied within h hours. Describe your algorithm and its time complexity. 2) Subset sum: Given a set of distinct positive integers and a target, determine whether some subset sums exactly to the target. Outline an algorithm, analyze its complexity, and explain how to recover one valid subset if it exists.

Quick Answer: This question evaluates algorithmic problem-solving and complexity-analysis skills, focusing on optimization for rate-limited resource allocation and combinatorial subset selection.

Part 1: Minimum Robber Vault Rate

You are given an array vaults where vaults[i] is the amount of money in the i-th vault, and an integer h representing the number of hours available. In one hour, you may steal from only one vault, removing at most k units from that single vault. You cannot split an hour across multiple vaults. Find the minimum integer rate k such that all vaults can be emptied within h hours. If vaults is empty, return 0.

Constraints

0 <= len(vaults) <= 100000
1 <= vaults[i] <= 10^9 for each vault when vaults is non-empty
0 <= h <= 10^9
If vaults is non-empty, assume h >= len(vaults) so a solution exists
If vaults is empty, the answer is 0

Examples

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

Expected Output: 4

Explanation: At rate 4, the required hours are 1 + 2 + 2 + 3 = 8. Any smaller rate takes more than 8 hours.

Input: ([10], 1)

Expected Output: 10

Explanation: With only one hour and one vault of size 10, the rate must be 10.

Hints

For a fixed rate k, how many hours does one vault of size x require?
If a rate k works, then any rate larger than k also works. That suggests binary search.

Part 2: Recover a Subset With Exact Sum

You are given a list nums representing a set of distinct positive integers and a non-negative integer target. Return one subset whose elements sum exactly to target. Return the subset as a list in the same relative order as the chosen numbers appear in nums. If no such subset exists, return an empty list. If target is 0, the empty subset is valid, so return [].

Constraints

0 <= len(nums) <= 200
1 <= nums[i] <= 10^4
All numbers in nums are distinct
0 <= target <= 20000

Examples

Input: ([8, 6, 5, 1], 9)

Expected Output: [8, 1]

Explanation: The subset [8, 1] sums to 9.

Input: ([3, 34, 12, 5, 2], 9)

Expected Output: []

Explanation: No subset sums to exactly 9.

Hints

Think of dynamic programming on sums from 0 to target.
To reconstruct a subset, store how each reachable sum was first formed.

Loading coding console...