Choose k Non-Adjacent Servers to Minimize the Largest Chosen Value
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A row of `n` servers is numbered `0` to `n - 1` from left to right, and server `i` has an integer value `values[i]`. Choose exactly `k` servers such that no two chosen servers are next to each other in the row. Among all such choices, make the largest value of any chosen server as small as possible, and return that smallest possible largest value.
### Function Signature
```python
def min_largest_nonadjacent(values: list[int], k: int) -> int:
```
### Rules
- Servers `i` and `j` are adjacent when `abs(i - j) == 1`. A valid choice is a set of exactly `k` distinct servers that contains no adjacent pair.
- The cost of a valid choice is the maximum of `values[i]` over its chosen servers.
- Return the minimum cost over all valid choices. The constraints guarantee that at least one valid choice exists. Several choices may reach the minimum; the returned number is the same for all of them.
### Constraints
- `1 <= len(values) <= 10^5`
- `1 <= values[i] <= 10^9`
- `1 <= k <= (len(values) + 1) // 2`
### Examples
**Example 1**
```text
Input: values = [2, 3, 5, 9], k = 2
Output: 5
```
The valid choices are servers {0, 2}, {0, 3} and {1, 3}, with costs 5, 9 and 9.
**Example 2**
```text
Input: values = [5, 1, 1, 5, 2], k = 2
Output: 2
```
Servers 1 and 2 are the only ones with a value of at most 1, and they are adjacent, so a cost of 1 is impossible. Choosing servers 1 and 4 (values 1 and 2) gives a cost of 2.
**Example 3**
```text
Input: values = [7, 1, 8, 2, 9], k = 3
Output: 9
```
The only way to choose three non-adjacent servers out of five is {0, 2, 4}, whose largest value is 9.
Overview: A coding problem about choosing exactly k servers from a row so that no two chosen servers are neighbors, while making the largest value among the chosen servers as small as possible. It tests reasoning about a min-max objective under an adjacency restriction and finding an efficient solution for rows of up to 100,000 servers.
Read the full Microsoft Software Engineer interview experience this question came from
A row of `n` servers is numbered `0` to `n - 1` from left to right, and server `i` has the integer value `values[i]`. Choose exactly `k` servers so that no two chosen servers are next to each other in the row. Among all such choices, make the largest value of any chosen server as small as possible, and return that smallest possible largest value.
Implement `min_largest_nonadjacent(values, k)`, which returns a single integer.
**Rules**
- Servers `i` and `j` are adjacent when `abs(i - j) == 1`. A valid choice is a set of exactly `k` distinct servers that contains no adjacent pair.
- The cost of a valid choice is the maximum of `values[i]` over its chosen servers.
- Return the minimum cost over all valid choices. The constraints guarantee that at least one valid choice exists. Several choices may reach the minimum; the returned number is the same for all of them.
**Constraints**
- `1 <= len(values) <= 10^5`
- `1 <= values[i] <= 10^9`
- `1 <= k <= (len(values) + 1) // 2`
No value exceeds 2^31 - 1, so every value and the returned answer fit in a signed 32-bit integer.
**Example 1**
```text
Input: values = [2, 3, 5, 9], k = 2
Output: 5
```
The valid choices are servers {0, 2}, {0, 3} and {1, 3}, with costs 5, 9 and 9.
**Example 2**
```text
Input: values = [5, 1, 1, 5, 2], k = 2
Output: 2
```
Servers 1 and 2 are the only ones with a value of at most 1, and they are adjacent, so a cost of 1 is impossible. Choosing servers 1 and 4 (values 1 and 2) gives a cost of 2.
Constraints
- 1 <= len(values) <= 10^5
- 1 <= values[i] <= 10^9
- 1 <= k <= (len(values) + 1) // 2
Examples
Input: ([7], 1)
Expected Output: 7
Explanation: Minimum valid row: a single server with k = 1 must be chosen.
Input: ([2, 3, 5, 9], 2)
Expected Output: 5
Explanation: Source Example 1: {0, 2} costs 5 while {0, 3} and {1, 3} cost 9; the answer equals a limit value exactly (regression for a strict comparison).
Hints
- The returned number is always one of the values in the row, since it is the value of some chosen server.
- Choosing the k smallest values ignores adjacency: in Example 2 the two smallest values sit next to each other, so they cannot both be chosen.
- Within any stretch of consecutive servers, adjacency limits how many of them can be chosen together.