Maximize total bandwidth of data channel pairs
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
Overview: This question evaluates a candidate's ability to design efficient algorithms for combinatorial optimization and selection under constraints, testing understanding of array manipulation, ordered pair counting, and aggregation of bandwidth sums.
Constraints
- 1 <= n <= 10^5
- 1 <= bandwidth[i] <= 10^9
- 1 <= streamCount <= n^2
- (i, j) and (j, i) are distinct ordered pairs; i == j is allowed
- Every selected channel must use a distinct ordered pair
Examples
Input: (3, [4, 2, 7], 3)
Expected Output: 36
Explanation: Sorted desc [7,4,2]. Top 3 pair-sums: (7,7)=14, then (7,4)=11 and (4,7)=11. Total 14+11+11=36.
Input: (1, [5], 1)
Expected Output: 10
Explanation: Only one node, the single allowed pair is (0,0) with value 5+5=10.
Hints
- Sort the bandwidths in descending order. A pair's value is bandwidth[i] + bandwidth[j]; the best pairs combine the largest values, but there are up to n^2 of them so you cannot list them all.
- Binary search on a threshold T = the pair-sum cutoff. For a given T you can count, in O(n log n), how many ordered pairs have sum >= T (for each main node i, the secondaries are exactly those j with bandwidth[j] >= T - bandwidth[i]).
- Find the largest T with at least streamCount pairs of sum >= T. Take all pairs with sum >= T+1 in full (track their total with prefix sums), then top up with the leftover channels at value T.