Maximum Group of Pairwise Strangers in an Acquaintance Tree
Company: Two Sigma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a social network of `n` people, labeled `0` through `n - 1`. For some pairs of people, it is known that the two people in the pair know each other. The "knows" relation is symmetric: if person `a` knows person `b`, then person `b` knows person `a`.
You are guaranteed that the graph built from these acquaintance relationships is a **tree**: it has exactly `n - 1` relationship pairs, and every person is connected to every other person through some chain of acquaintances.
Select the **maximum** number of people such that **no two selected people know each other** (i.e., no selected pair is directly connected by an acquaintance edge). Return that maximum count.
Write a function that takes:
- `n` — the number of people, and
- `edges` — a list of `n - 1` pairs `[a, b]` (with `0 <= a, b < n`, `a != b`), where each pair means person `a` and person `b` know each other,
and returns a single integer: the maximum number of people you can select so that no two of them know each other.
**Example 1**
```
n = 3
edges = [[0, 1], [0, 2]]
```
Output: `2`
Person `0` knows both `1` and `2`, but `1` and `2` do not know each other. Selecting `{1, 2}` gives 2 people who are pairwise strangers. Any set of 3 would have to include person `0` together with a neighbor, which is not allowed.
**Example 2**
```
n = 7
edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [5, 6]]
```
Output: `4`
One optimal selection is `{0, 3, 4, 5}`. Person `0` knows only `1` and `2`; person `3` and person `4` know only `1`; person `5` knows only `2` and `6`. No pair among `{0, 3, 4, 5}` is directly connected, so all four are pairwise strangers, and no valid selection of 5 people exists.
**Example 3**
```
n = 1
edges = []
```
Output: `1`
A single person trivially satisfies the condition.
**Constraints**
- `1 <= n <= 10^5`
- `edges.length == n - 1`
- The relationship graph is a connected tree (no cycles, no duplicate edges, no self-loops).
Your solution should run in `O(n)` time. In addition to the provided examples, you are expected to design your own test cases covering edge cases such as a single person, a path-shaped network, and a star-shaped network.
Quick Answer: This question evaluates understanding of graph algorithms and combinatorial optimization, centering on the maximum independent set in a tree and the ability to reason about constraints on pairwise adjacency.
You are given a social network of `n` people, labeled `0` through `n - 1`. For some pairs of people it is known that the two people in the pair know each other. The "knows" relation is symmetric: if person `a` knows person `b`, then person `b` knows person `a`.
The graph built from these acquaintance relationships is guaranteed to be a **tree**: it has exactly `n - 1` relationship pairs, and every person is connected to every other person through some chain of acquaintances.
Select the **maximum** number of people such that **no two selected people know each other** (no selected pair is directly connected by an acquaintance edge). Return that maximum count.
Your function receives:
- `n` — the number of people, and
- `edges` — a list of `n - 1` pairs `[a, b]` (with `0 <= a, b < n`, `a != b`), where each pair means person `a` and person `b` know each other,
and returns a single integer: the maximum number of people you can select so that no two of them know each other.
**Example 1**
```
n = 3
edges = [[0, 1], [0, 2]]
```
Output: `2` — Person `0` knows both `1` and `2`, but `1` and `2` do not know each other. Selecting `{1, 2}` gives 2 pairwise strangers.
**Example 2**
```
n = 7
edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [5, 6]]
```
Output: `4` — e.g. `{0, 3, 4, 5}` are pairwise strangers, and no valid selection of 5 exists.
**Example 3**
```
n = 1
edges = []
```
Output: `1` — A single person trivially satisfies the condition.
**Constraints**
- `1 <= n <= 10^5`
- `edges.length == n - 1`
- The relationship graph is a connected tree (no cycles, no duplicate edges, no self-loops).
- Target time complexity: `O(n)`.
*Follow-up (discussion): if the graph were not guaranteed to be a tree, this becomes the general Maximum Independent Set problem, which is NP-hard.*
Constraints
- 1 <= n <= 10^5
- edges.length == n - 1
- 0 <= a, b < n and a != b for each edge
- The graph is a connected tree (no cycles, no duplicate edges, no self-loops)
Examples
Input: (3, [[0, 1], [0, 2]])
Expected Output: 2
Explanation: Star with center 0; picking the two leaves {1,2} gives 2 pairwise strangers.
Input: (7, [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [5, 6]])
Expected Output: 4
Explanation: One optimal set is {0,3,4,5}; no selection of 5 is possible.
Hints
- This is the Maximum Independent Set problem, which is NP-hard in general but solvable in linear time on a tree via dynamic programming.
- Root the tree anywhere. For each node keep two values: the best independent-set size in its subtree when the node IS chosen, and when it is NOT chosen.
- If a node is chosen, none of its children may be chosen (add each child's 'not chosen' value plus 1 for the node). If a node is not chosen, each child contributes the max of its two values.
- For n up to 10^5, recursion may overflow the default stack — use an explicit stack (iterative post-order) or raise the recursion limit.