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

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.

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

Expected Output: 30

Explanation: There are 5 vaults and 5 hours, so each vault must be emptied in exactly one hour. The rate must be at least the maximum vault size.

Input: ([], 5)

Expected Output: 0

Explanation: There are no vaults to empty.

Input: ([1, 1, 1, 1], 10)

Expected Output: 1

Explanation: A rate of 1 is enough because each vault already takes only one hour.

Solution

def solution(vaults, h):
    if not vaults:
        return 0

    left, right = 1, max(vaults)

    def can_finish(rate):
        hours = 0
        for amount in vaults:
            hours += (amount + rate - 1) // rate
            if hours > h:
                return False
        return True

    while left < right:
        mid = (left + right) // 2
        if can_finish(mid):
            right = mid
        else:
            left = mid + 1

    return left

Time complexity: O(n log M), where n is the number of vaults and M is the maximum vault amount. Space complexity: O(1) extra space.

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.

Input: ([4, 10], 0)

Expected Output: []

Explanation: Target 0 is achieved by taking the empty subset.

Input: ([7], 7)

Expected Output: [7]

Explanation: The single element itself matches the target.

Input: ([14, 9, 3, 2], 17)

Expected Output: [14, 3]

Explanation: The subset [14, 3] sums to 17.

Solution

def solution(nums, target):
    if target == 0:
        return []

    reachable = [False] * (target + 1)
    prev_sum = [-1] * (target + 1)
    chosen = [-1] * (target + 1)
    reachable[0] = True

    for num in nums:
        if num > target:
            continue
        for s in range(target, num - 1, -1):
            if not reachable[s] and reachable[s - num]:
                reachable[s] = True
                prev_sum[s] = s - num
                chosen[s] = num

    if not reachable[target]:
        return []

    subset = []
    s = target
    while s > 0:
        subset.append(chosen[s])
        s = prev_sum[s]

    subset.reverse()
    return subset

Time complexity: O(n * target), where n is the number of elements. Space complexity: O(target).

Hints

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

Quick Overview

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