AMAZON OA SDE-1 Questions

Data scientists at Amazon are working on a logistics optimization tool to arrange delivery routes based on existing route patterns.

A prototype algorithm takes two integers, size and target_sum, and generates a sequence of size size whose sum of elements equals target_sum, and the absolute values of the elements form a permutation of size size. The algorithm must produce the lexicographically smallest such sequence.

Given two integers, size and target_sum, return the lexicographically smallest sequence of integers such that:

1. The sum of its elements equals target_sum.
2. The absolute values of its elements form a permutation of size size.

Note

• A sequence of size size is a permutation if it contains all integers from 1 to size exactly once. For example:
  • [4, 1, 2, 5, 3] → valid permutation
  • [2, 3, 2, 4, 5] → not a permutation
• Given two permutations x and y, x is lexicographically smaller than y if at the first index where they differ, x[i] < y[i].
  • When comparing element by element from the start, the first unequal element determines the ordering.

Example

Suppose size = 5, target_sum = 9.

Some sequences of size 5 with sum = 9 are:

We can clearly see that:

• [-3, 1, 2, 4, 5] is lexicographically smaller than [-3, 2, 1, 4, 5] because 1 < 2 at the first index where they differ.

Thus, the lexicographically smallest sequence with the given sum is:

[-3, 1, 2, 4, 5]

Amazon developers are designing an algorithm to optimize segmentation of streaming data packets.

You are given an array of integers data_packets of size n. The algorithm repeatedly performs the following until data_packets becomes empty:

1. Choose an integer k such that 1 ≤ k ≤ length(data_packets).
2. Compute the MEX (Minimum EXcluded) of the first k elements.
   • The MEX of a set of non-negative integers is the smallest non-negative integer not present in the set.
   • Example:
     • MEX({1, 2, 3}) = 0
     • MEX({0, 1, 2, 4}) = 3
3. Append this MEX to an array result.
4. Remove the first k elements from data_packets.

Your task is to find the lexicographically maximum array result that can be obtained.

Note

• An array x is lexicographically greater than an array y if at the first index where they differ,
  • x[i] > y[i], or
  • y is a prefix of x.
• Example:
  • [2, 3, 1] > [1, 5]
  • [2, 3, 4] < [2, 3] since the latter is a prefix.

Example

Given n = 4, data_packets = [0, 1, 0], one way to achieve the lexicographically maximum result is:

• Take k = 2 → MEX of {0, 1} is 2 result = [2], remaining = [0]
• Take k = 1 → MEX of {0} is 1 result = [2, 1]

data_packets is now empty, and the answer is [2, 1].

Function Description

Complete the function getMaxArray:

def getMaxArray(data_packets: List[int]) -> List[int]:

Parameters

• data_packets: array of integers representing streaming data packets.

Returns

• List[int]: the lexicographically maximum result array obtainable following the algorithm.