Amazon OA Question and Answer

Round 1

Questions: Your project team is collaborating with a group of software testers who have requested an array generator service to assist in testing software functionality.

Problem Statement

The service takes the following input parameters:

• arr: An array of n positive integers.
• state: A string of n characters, where:
  • \'1\' indicates that the corresponding arr[i] is available for selection.
  • \'0\' indicates that arr[i] is blocked initially.
• m: The number of operations to perform.

Operations

To generate an integer sequence S, perform exactly m operations as follows:

1. Choose any available arr[i] (where state[i] = \'1\'). The same element can be chosen multiple times.
2. Append the selected arr[i] to S.
3. Update the state:
   • Any state[i] = \'0\' where state[i-1] = \'1\' is changed to \'1\'.
   • This means that blocked elements adjacent to available ones become available.

Objective

Find the lexicographically largest sequence S that can be obtained after exactly m operations.

Example

Input

arr = [10, 5, 7, 6]
state = "0101"
m = 2

Operations

| Step | Available Elements | Chosen Element | Updated State | |------|--------------------|----------------|----------------| | 1 | {5, 6} | 6 | "0111" | | 2 | {5, 6, 7} | 7 | "0111" |

Output

S = [6, 7]

Since [6, 7] is lexicographically larger than [5, 6] or [5, 5], this is the optimal solution.

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ 10^9
• 1 ≤ m ≤ 10^5
• state is a binary string of length n.

Candidate's Approach

The candidate implemented a solution using a queue to manage available and blocked elements. The approach involves:

• Iterating through the state to identify available elements and their indices.
• Using two queues to track indices of available elements and those that can become available.
• Constructing the output sequence by selecting the maximum available element and updating the state accordingly.
• Filling the remaining operations with the maximum element chosen.

Interviewer's Feedback

The interviewer appreciated the candidate's approach to managing the state transitions and the use of queues for efficient tracking. They suggested ensuring edge cases are handled, particularly when all elements are blocked initially.

---