Maximize minimum value after k decrements
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given an integer array `vulnerabilities` of length `n`, where `vulnerabilities[i]` is the initial security score of server `i`.
You must perform exactly `k` operations. In each operation, choose any server `i` and decrease `vulnerabilities[i]` by `1`.
After all `k` operations, let the resulting array be `final`.
**Task**: Compute the maximum possible value of `min(final)` that you can achieve by choosing which servers to decrement each time.
### Input
- Integer array `vulnerabilities` (length `n`)
- Integer `k` (number of operations)
### Output
- An integer: the maximum achievable `min(final)`
### Notes / Constraints (reasonable interview assumptions)
- `1 ≤ n ≤ 2e5`
- `0 ≤ vulnerabilities[i] ≤ 1e9`
- `0 ≤ k ≤ 1e12`
- Decrements may make values negative.
### Example
- `vulnerabilities = [5, 1, 4]`, `k = 3`
- One optimal strategy is to decrement the `5` three times → `[2, 1, 4]`, so `min = 1`.
- Output: `1`
Quick Answer: This question evaluates array-based optimization skills, resource-allocation reasoning under a fixed decrement budget, and algorithmic complexity analysis for maximizing a minimum value after constrained operations.
Perform exactly k decrements while maximizing the final minimum value.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([5,1,4], 3)
Expected Output: 1
Explanation: All decrements can be spent above the current minimum.
Input: ([1,1], 1)
Expected Output: 0
Explanation: Once all values are at the minimum, any decrement lowers the minimum.
Input: ([3,3,3], 6)
Expected Output: 1
Explanation: Two full rounds lower the minimum by two.
Hints
- First spend decrements on values above the current minimum.
- Any remaining decrements must be spread across all minimum values.