Maximize total catch over K hours from ponds whose yield drops after each hour
Company: ByteDance
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
There are `N` fishing ponds. `M[i]` is the number of fish you catch if you spend the next hour fishing at pond `i`. You have `K` hours in total. Each hour you pick any one pond and fish there for the whole hour. Every hour you spend at a pond lowers that pond's hourly catch by 1 for the following hours; ponds you do not fish at keep their current catch.
Return the maximum total number of fish you can catch in the `K` hours.
The interviewer required a solution whose running time is asymptotically better than $O(K \log N)$, so simulating the hours one at a time is too slow when `K` is large.
### Function Signature
```python
def max_fish(M: list[int], K: int) -> int:
```
### Rules
- An hour at pond `i` catches its current hourly catch, then lowers that catch by 1.
- A pond's hourly catch never goes below 0: an hour at a pond whose catch is 0 catches nothing, and its catch stays 0.
- The order in which you visit ponds is free, and you may stay at the same pond for consecutive hours.
- Return only the maximum total, which is unique.
### Constraints
- `N == len(M)` and `1 <= N <= 10^5`
- `0 <= M[i] <= 10^6`
- `0 <= K <= 10^9`
- The answer is at most `10^15`, which exceeds `2^31 - 1`; Python integers handle this, but other languages need 64-bit integers.
### Examples
**Example 1**
```text
Input: M = [90, 100], K = 100
Output: 7075
```
One optimal plan spends 55 hours at the second pond (4015 fish) and 45 hours at the first pond (3060 fish).
**Example 2**
```text
Input: M = [3, 5], K = 4
Output: 15
```
For example: two hours at the second pond (5 + 4), after which both ponds yield 3, then one hour at each (3 + 3).
**Example 3**
```text
Input: M = [2], K = 5
Output: 3
```
The only pond yields 2, then 1, then 0 for each of the remaining three hours.
Overview: Given the current hourly catch of each fishing pond and a budget of K hours, where every hour fished at a pond lowers its catch by one, compute the maximum total number of fish. It tests modeling the declining yields, choosing an optimal schedule, and meeting a time bound better than O(K log N) when K is very large.
Read the full ByteDance Machine Learning Engineer interview experience this question came from
There are `N` fishing ponds. `M[i]` is the number of fish you catch if you spend the next hour fishing at pond `i`. You have `K` hours in total. Each hour you pick any one pond and fish there for the whole hour.
Rules:
- An hour at pond `i` catches its current hourly catch, then lowers that pond's hourly catch by 1 for the following hours. Ponds you do not fish at keep their current catch.
- A pond's hourly catch never goes below 0: an hour at a pond whose catch is 0 catches nothing, and its catch stays 0.
- The order in which you visit ponds is free, and you may stay at the same pond for consecutive hours.
Implement `max_fish(M, K)` to return the maximum total number of fish you can catch in the `K` hours. Return only this maximum total (it is unique), not a plan.
The interviewer required a running time asymptotically better than O(K log N), so simulating the hours one at a time is too slow when `K` is large.
The answer can be as large as 10^15, which exceeds 2^31 - 1: Python integers handle it, but Java must return `long` and C++ `long long`. Every `M[i]` and `K` fits in a 32-bit signed integer.
Example 1:
Input: M = [90, 100], K = 100
Output: 7075
One optimal plan spends 55 hours at the second pond (100 + 99 + ... + 46 = 4015 fish) and 45 hours at the first pond (90 + 89 + ... + 46 = 3060 fish).
Example 2:
Input: M = [3, 5], K = 4
Output: 15
For example: two hours at the second pond (5 + 4), after which both ponds yield 3, then one hour at each (3 + 3).
Constraints:
- N == len(M) and 1 <= N <= 10^5
- 0 <= M[i] <= 10^6
- 0 <= K <= 10^9
- The answer is at most 10^15, which exceeds 2^31 - 1; use 64-bit integers outside Python (Java long, C++ long long).
Constraints
- N == len(M) and 1 <= N <= 10^5
- 0 <= M[i] <= 10^6
- 0 <= K <= 10^9
- The answer is at most 10^15, which exceeds 2^31 - 1; use 64-bit integers outside Python (Java long, C++ long long)
- Required running time: asymptotically better than O(K log N)
Examples
Input: ([90, 100], 100)
Expected Output: 7075
Explanation: Source example 1: the taller pond is drained alone from 100 to 91, then both ponds share levels down to 46 (4015 + 3060).
Input: ([3, 5], 4)
Expected Output: 15
Explanation: Source example 2: 5 + 4 + 3 + 3; K exactly equals the number of catches >= 3.
Hints
- Only how many hours you spend at each pond matters, not the order: each pond contributes its first few hourly catches M[i], M[i] - 1, ..., stopping at 0.
- Treat every hour you could ever spend anywhere as a single value. Which K of those values does an optimal plan collect?
- K can reach 10^9, so look for a way to count and sum many hours at once instead of handling them one by one, and keep the total in 64 bits.