Build the Largest Available Sequence
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given an integer array `values`, a binary string `state` of the same length, and an integer `m` such that `0 <= m <= values.length`.
Build a sequence `s` of length `m` using exactly `m` operations. You may assume it is always possible to complete all `m` picks.
In each operation:
1. Choose any index `i` such that `state[i] = '1'`.
2. Append `values[i]` to `s`.
3. Mark that index as unavailable by setting `state[i] = '0'`.
4. Then perform one simultaneous availability update on this new state: for every index `j > 0`, if `state[j - 1] = '1'` and `state[j] = '0'`, flip `state[j]` to `1`.
Return the lexicographically largest possible sequence `s`. For integer sequences, lexicographic order compares elements from left to right.
Example:
- `values = [10, 5, 7, 6]`
- `state = "0101"`
- `m = 2`
One optimal answer is `[6, 7]`.
Write a function to compute the lexicographically largest sequence.
Quick Answer: This question evaluates algorithmic problem-solving skills in state simulation, constrained selection, and lexicographic sequence maximization, measuring the ability to reason about evolving availability when constructing sequences.
You are given an integer array `values`, a binary string `state` of the same length, and an integer `m` such that `0 <= m <= len(values)`.
Build a sequence `s` of length `m` using exactly `m` operations. You may assume it is always possible to complete all `m` picks.
In one operation:
1. Choose any index `i` with `state[i] == '1'`.
2. Append `values[i]` to `s`.
3. Set `state[i] = '0'`.
4. Then apply one simultaneous availability update on this new state: for every index `j > 0`, if `state[j - 1] == '1'` and `state[j] == '0'`, flip `state[j]` to `1`.
Return the lexicographically largest possible sequence `s`.
Notes:
- Lexicographic order compares sequences from left to right.
- An index may become available again after the update, so the same index can be picked more than once across different operations.
Constraints
- 0 <= n = len(values) <= 15
- -10^9 <= values[i] <= 10^9
- len(state) == n
- Each character of state is either '0' or '1'
- 0 <= m <= n
- The input is guaranteed to allow exactly m valid picks
Examples
Input: ([10, 5, 7, 6], "0101", 2)
Expected Output: [6, 7]
Explanation: Pick 6 at index 3 first. The state becomes 0110, which makes 7 available next. This gives [6, 7], which is better than any sequence starting with 5.