Maximum total weight of graph nodes with no two adjacent
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an undirected graph whose nodes carry positive weights. Choose a set of nodes such that no two chosen nodes are joined by an edge, and return the largest possible total weight of the chosen nodes.
The report says only "a graph", so this version accepts any undirected graph: it may contain cycles and may be disconnected. The graph is small (at most 20 nodes).
### Function Signature
```python
def max_independent_weight(weights: list[int], edges: list[list[int]]) -> int:
```
### Rules
- Nodes are numbered `0` to `n - 1`, where `n = len(weights)`, and node `i` has weight `weights[i]`.
- `edges[j] = [u, v]` joins nodes `u` and `v`. Edges are undirected.
- A set of nodes is valid when no edge has both of its endpoints in the set. The empty set is valid.
- Return the maximum total weight over all valid sets.
### Constraints
- `1 <= n <= 20`
- `1 <= weights[i] <= 10^6`
- `0 <= len(edges) <= n * (n - 1) / 2`
- For every edge `[u, v]`: `0 <= u, v < n` and `u != v`. Each pair of nodes appears in `edges` at most once, in either order.
- The answer is at most `2 * 10^7`, so it fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: weights = [5, 1, 2, 5], edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Output: 7
```
The four nodes form a cycle, and the edge `[3, 0]` makes the two heaviest nodes adjacent, so they cannot both be chosen. The best valid set is `{0, 2}`, with weight `5 + 2 = 7`; the other two-node set, `{1, 3}`, weighs `6`.
**Example 2**
```text
Input: weights = [6, 2, 3, 4, 2], edges = [[0, 1], [0, 2], [0, 3], [1, 2], [3, 4]]
Output: 8
```
Choosing node `0` (weight 6) rules out nodes `1`, `2` and `3` and leaves node `4`, for a total of `8`. Without node `0`, at most one of the adjacent nodes `1` and `2` and one of the adjacent nodes `3` and `4` can be chosen, which gives at best `3 + 4 = 7`.
**Example 3**
```text
Input: weights = [2, 9, 4], edges = [[0, 1]]
Output: 13
```
Node `2` has no edges, so it can always be added. Between the adjacent nodes `0` and `1`, node `1` is heavier: `9 + 4 = 13`.
Overview: Given an undirected graph with positive node weights, choose nodes so that no two chosen nodes share an edge and return the largest possible total weight. The graph may contain cycles and be disconnected and has at most 20 nodes. It tests graph reasoning, search over choices and careful handling of adjacency constraints.
Read the full ByteDance Software Engineer interview experience this question came from
You are given an undirected graph whose nodes carry positive weights. Nodes are numbered `0` to `n - 1`, where `n = len(weights)`, and node `i` has weight `weights[i]`. Each entry `edges[j] = [u, v]` joins nodes `u` and `v`. Edges are undirected, so an edge may appear as `[u, v]` or as `[v, u]` with the same meaning. The graph may contain cycles and may be disconnected.
A set of nodes is **valid** when no edge has both of its endpoints in the set. The empty set is valid. Return the maximum total weight over all valid sets.
Only the total is returned, so when several different valid sets reach the maximum, the answer is that shared total.
### Constraints
- `1 <= n <= 20`
- `1 <= weights[i] <= 10^6`
- `0 <= len(edges) <= n * (n - 1) / 2`
- For every edge `[u, v]`: `0 <= u, v < n` and `u != v`. Each pair of nodes appears in `edges` at most once, in either order.
- The answer is at most `2 * 10^7`, so it fits in a 32-bit signed integer: no value exceeds `2^31 - 1`, and `int` is enough in Java and C++.
### Example 1
```text
Input: weights = [5, 1, 2, 5], edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Output: 7
```
The four nodes form a cycle, and the edge `[3, 0]` makes the two heaviest nodes adjacent, so they cannot both be chosen. The best valid set is `{0, 2}`, with weight `5 + 2 = 7`; the other two-node valid set, `{1, 3}`, weighs `6`.
### Example 2
```text
Input: weights = [6, 2, 3, 4, 2], edges = [[0, 1], [0, 2], [0, 3], [1, 2], [3, 4]]
Output: 8
```
Choosing node `0` (weight 6) rules out nodes `1`, `2` and `3` and leaves node `4`, for a total of `8`. Without node `0`, at most one of the adjacent nodes `1` and `2` and one of the adjacent nodes `3` and `4` can be chosen, which gives at best `3 + 4 = 7`.
Constraints
- 1 <= n <= 20, where n = len(weights)
- 1 <= weights[i] <= 10^6
- 0 <= len(edges) <= n * (n - 1) / 2
- For every edge [u, v]: 0 <= u, v < n and u != v. Each pair of nodes appears in edges at most once, in either order.
- The answer is at most 2 * 10^7, so it fits in a 32-bit signed integer.
Examples
Input: ([7], [])
Expected Output: 7
Explanation: Minimum valid input: a single node with no edges is chosen on its own.
Input: ([5, 5], [[0, 1]])
Expected Output: 5
Explanation: Two adjacent nodes of equal weight: either one alone is optimal (a tie between two different sets), never both.
Hints
- Every weight is positive, so a node none of whose neighbours is chosen can always be added without lowering the total; a node with no edges belongs in every best set.
- Taking the heaviest available node first is not always optimal: a centre node can weigh less than its neighbours together, so compare whole totals rather than single weights.
- With at most 20 nodes an exact search is affordable; the work is in organising it so that only valid sets are ever considered.