Maximize total bandwidth of data channel pairs
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
You are optimizing how information flows through a network of processing nodes.
There are `n` processing nodes. The bandwidth capability of the *i*-th node is given by an integer array `bandwidth` of length `n`.
There are `streamCount` data channels that must each be connected to **two** processing nodes:
- one node acts as the **main** connection;
- the other acts as the **secondary** connection.
For a single data channel with main node index `i` and secondary node index `j`, its data flow is defined as:
> `dataFlow = bandwidth[i] + bandwidth[j]`
A ***pair of nodes*** `(i, j)` used for one channel must be **unique** among all channels, with the following rules:
- A pair is identified by the ordered indices `(main, secondary)`.
- `(i, j)` and `(j, i)` are considered **different** pairs.
- It is allowed to choose `i == j`, i.e., a channel may use the same node for both main and secondary.
- The same node index can appear in many different pairs (across different channels), as long as the ordered pair `(i, j)` itself is unique for each channel.
Your goal is to select exactly `streamCount` distinct ordered pairs `(main, secondary)` so that the **sum of dataFlow across all data channels is maximized**.
### Input
- An integer `n` (number of nodes).
- An integer array `bandwidth` of length `n`, where `bandwidth[i]` is the bandwidth of node `i`.
- An integer `streamCount` — the number of data channels.
You may assume:
- `1 <= n <= 10^5`.
- `1 <= bandwidth[i] <= 10^9`.
- `1 <= streamCount <= n^2` (since there are `n^2` possible ordered pairs `(i, j)` including `i == j`).
### Output
- Return a single integer: the **maximum possible total dataFlow**, i.e., the maximum possible sum of `bandwidth[main] + bandwidth[secondary]` over all `streamCount` channels.
### Complexity requirement
Design an algorithm that works efficiently for `n` and `streamCount` up to about `10^5` (much better than enumerating all `n^2` pairs explicitly when `n` is large).
Quick Answer: 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.
