How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Build the Largest Available Sequence | Amazon Coding Question

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.

Input: ([9, 1, 8], "101", 3)

Expected Output: [8, 9, 8]

Explanation: Picking 9 first is impossible if you still need 3 total picks, because it would leave only one future pick. So the best valid first choice is 8, after which the best continuation is 9 then 8.

Input: ([4, 4, 2], "110", 3)

Expected Output: [4, 4, 4]

Explanation: Picking index 1 from state 110 removes it, but it is immediately restored by the update because index 0 is still available. So index 1 can be picked three times.

Input: ([-1, -5, 0], "011", 2)

Expected Output: [0, 0]

Explanation: Index 2 is the best available value, and picking it from 011 keeps the state unchanged. So the largest 2-length sequence is [0, 0].

Input: ([3, 1], "11", 0)

Expected Output: []

Explanation: No operations are required, so the answer is the empty sequence.

Input: ([8], "1", 1)

Expected Output: [8]

Explanation: There is only one available pick, so the sequence is [8].

Input: ([], "", 0)

Expected Output: []

Explanation: With no elements and zero required picks, the only valid answer is the empty sequence.

Hints

Treat the availability string as a bitmask. After removing index i, the simultaneous update is exactly: `next_mask = removed_mask | (removed_mask << 1)` with overflow bits discarded.
Because the answer is a lexicographically largest sequence, memoize the best suffix for each `(mask, picks_left)` state instead of only storing a numeric score.

Quick Overview

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.