Maximize Minimum Scaled Value
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
You are given two integer arrays `values` and `costs` of the same length `n`, and a non-negative integer `totalCost`.
For each index `i`, you may choose an integer multiplier `times[i] >= 1`.
- The final value at index `i` becomes `values[i] * times[i]`.
- Increasing index `i` from multiplier `1` to `times[i]` costs `costs[i] * (times[i] - 1)`.
Your total spending across all indices must satisfy:
`sum(costs[i] * (times[i] - 1)) <= totalCost`
Your goal is to maximize the minimum final value among all indices, that is, maximize:
`min(values[i] * times[i])`
Return the largest possible value of this minimum.
Quick Answer: This question evaluates algorithmic optimization and resource-allocation skills, focusing on integer scaling under a global budget to maximize the minimum final value across elements. It is asked in the Coding & Algorithms domain to probe trade-off reasoning and problem-solving under constraints, and the level of abstraction is practical application (algorithm design and implementation).
Choose integer multipliers under total cost to maximize the minimum final value.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([2,3], [1,10], 2)
Expected Output: 3
Explanation: Boost lower-cost value.
Input: ([5,5], [1,1], 0)
Expected Output: 5
Explanation: No spending.
Input: ([1,10,2], [1,2,3], 5)
Expected Output: 3
Explanation: Binary search target.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.