Maximize Throughput and Count Trigger Components
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two independent coding problems.
### Problem 1: Maximize Pipeline Throughput
A production pipeline has `n` services connected in series. Service `i` initially has one instance. One instance of service `i` can process `throughput[i]` requests per second. You may buy additional identical instances for any service; each extra instance of service `i` costs `cost[i]`. You have a total budget `B`.
The capacity of service `i` after buying `k` extra instances is `(k + 1) * throughput[i]`. Because the services are connected in series, the overall pipeline throughput is the minimum capacity among all services.
Return the maximum integer overall throughput that can be achieved without exceeding the budget.
Clarifications:
- You may buy any nonnegative integer number of extra instances for each service.
- The total cost of all purchased instances must be at most `B`.
- `n`, `throughput`, `cost`, and `B` may be large enough that trying every allocation is not feasible.
### Problem 2: Minimum Triggers to Absorb All Balls
You are given `n` balls on a 2D integer grid. Ball `i` is located at `(x[i], y[i])`. You are also given an integer distance threshold `d`.
If you manually trigger one ball, it absorbs itself and may start a chain reaction:
- Two balls can directly absorb each other if they are in the same row and their horizontal distance is at most `d`, or if they are in the same column and their vertical distance is at most `d`.
- Absorption is transitive: if ball `A` can absorb ball `B`, and ball `B` can absorb ball `C`, then triggering `A` eventually absorbs `C` as well.
Return the minimum number of manual triggers required to absorb all balls.
Clarifications:
- A trigger can be applied only to a ball that has not already been absorbed.
- The answer is the number of connected components under the row/column distance relationship.
- The input size may be large, so comparing every pair of balls directly may be too slow.
Quick Answer: This question evaluates proficiency in algorithmic optimization under resource constraints (maximizing pipeline throughput within a budget) and in modeling spatial connectivity as graph components for minimizing manual triggers.
Part 1: Maximize Pipeline Throughput
You are given a production pipeline made of services connected in series. Service i initially has exactly one instance, and one instance can process throughput[i] requests per second. You may buy any number of additional identical instances for service i, and each extra instance costs cost[i]. You have a total budget B.
If you buy k extra instances for service i, then its capacity becomes (k + 1) * throughput[i]. Because the services are in series, the overall pipeline throughput is the minimum capacity among all services.
Return the maximum integer overall throughput that can be achieved without spending more than B.
Constraints
- 1 <= len(throughput) == len(cost) <= 200000
- 1 <= throughput[i] <= 10^9
- 1 <= cost[i] <= 10^9
- 0 <= B <= 10^18
Examples
Input: ([4, 2, 5], [5, 3, 10], 8)
Expected Output: 4
Explanation: Buy 1 extra instance for the second service for cost 3. Capacities become [4, 4, 5], so the pipeline throughput is 4. Reaching 5 would cost 11, which exceeds the budget.
Input: ([3], [7], 20)
Expected Output: 9
Explanation: With a single service, buy 2 extra instances for total cost 14. Its capacity becomes 3 * 3 = 9. Buying 3 extras would cost 21, which is too much.
Input: ([5, 5], [4, 6], 0)
Expected Output: 5
Explanation: This is a budget-zero edge case. No extra instances can be purchased, so the answer is the initial minimum throughput, 5.
Input: ([2, 3, 7], [2, 5, 4], 17)
Expected Output: 7
Explanation: To achieve 7, buy 3 extras for the first service and 2 extras for the second, costing 6 + 10 = 16. Achieving 8 would require one more extra for the third service and exceed the budget.
Hints
- If you fix a target overall throughput T, each service can be handled independently: compute how many extra instances are needed so that its capacity is at least T.
- The feasibility of T is monotonic: if you can afford throughput T, then you can also afford any smaller throughput. That suggests binary search.
Part 2: Minimum Triggers to Absorb All Balls
You are given n balls on a 2D integer grid. Ball i is at position (x[i], y[i]). You are also given an integer distance threshold d.
If you manually trigger one ball, it absorbs itself and may start a chain reaction. Two balls are directly connected if either:
- they are in the same row and their horizontal distance is at most d, or
- they are in the same column and their vertical distance is at most d.
Absorption is transitive: if A can reach B and B can reach C, then triggering A eventually absorbs C as well.
Return the minimum number of manual triggers required to absorb all balls. Equivalently, return the number of connected components formed by this row/column distance relationship.
Constraints
- 0 <= len(x) == len(y) <= 200000
- -10^9 <= x[i], y[i] <= 10^9
- 0 <= d <= 10^9
Examples
Input: ([0, 2, 5], [0, 0, 0], 2)
Expected Output: 2
Explanation: All balls are in the same row. The first two are 2 units apart and connect, but the gap from 2 to 5 is 3, so the last ball is separate.
Input: ([0, 0, 3, 3], [0, 2, 2, 5], 3)
Expected Output: 1
Explanation: This is a chain-reaction case: (0,0) connects to (0,2), which connects to (3,2), which connects to (3,5). One trigger is enough.
Input: ([1], [1], 10)
Expected Output: 1
Explanation: A single ball is already one connected component.
Input: ([], [], 5)
Expected Output: 0
Explanation: Empty input edge case: there are no balls to trigger.
Input: ([1, 1, 2], [1, 1, 1], 0)
Expected Output: 2
Explanation: With d = 0, only balls at exactly the same position in the same row or column connect. The two balls at (1,1) form one component, and (2,1) is another.
Hints
- Balls can only connect to others in the same row or the same column, so grouping by y and by x avoids comparing every pair.
- Within a single row or column, sort the balls by coordinate and only check adjacent pairs. If consecutive balls are within distance d, union them.